[코테연습] 650. 2 Keys Keyboard

- 반복문 문제

 

https://leetcode.com/problems/2-keys-keyboard/description/?envType=daily-question&envId=2024-08-19

 

- 문제분석

 

1. int n 이 주어지고, 글자 'A' 가 있다고 한다.

2. 이때 n 이 특정 숫자 일 경우 2가지 액션을 취할 수 있다.

3. 첫번째는 'A' 를 copy 한다. 

4. 두번째는 'A' 를 paste 한다.

5. 이 경우 n 에 충족하는 글자수를 만족할 수 있도록 가장 최소한의 copy , paste 숫자를 구하라.

 

- 문제풀이

 

1. 문제를 단순하게 반복하면 다음과 같다.

        n = 3 // A, A, A

        n = 4 // A, AA, AAAA

        n = 5 // A, AA, AAA, AAAA, AAAAA

        n = 6 // A, AA, AAA, AAAAAA

        n = 7 // A, AA, AAA, AAAA, AAAAA, AAAAAA, AAAAAAAA

        n = 8 // A, AA, AAAA, AAAAAAAAA

 

2. 마지막 글자가 'A' 가 연속된 n 의 글자 수라고 했을때, 이전 글자는 n 을 2~n 까지 나눈 숫자 중에 하나일 것이다.

3. 예를 들면 'A' 의 이전 글자를 구하고 싶다면

 

if ( n % 2 == 0 ) {

   n/=2;

} else if (n%3 ==0) {

   n/=3;

} else ... 

 

로 반복될 것이다.

 

4. 반복된 횟수가 int count = 0 으로 초기화 했을때, while(n!=1) 일때까지 나눈 값을 count에 더하면 된다.

4-1. 나눈 값을 count 에 더한다면, n = 8 일때, n/=2 ==> n=4; count+=2;

4-2. n=4 n/=2; ==> n=2; count+=2;

4-3. n=2 n/=2; ==> n=1; count+=2;

4-4. count = 6이다.

4-4. copy 할때 한번, paste 할떄 1번씩 더해야하기 때문에 count 에 해당 행동을 더해준다.

5. 발화식은 다음과 같다. 

 

 n/=i;

 count+=i;

 

 

class Solution {
    /**
        n = 3 // A, A, A
        n = 4 // A, AA, AAAA
        n = 5 // A, AA, AAA, AAAA, AAAAA
        n = 6 // A, AA, AAA, AAAAAA
        n = 7 // A, AA, AAA, AAAA, AAAAA, AAAAAA, AAAAAAAA
        n = 8 // A, AA, AAAA, AAAAAAAAA
     */
    public int minSteps(int n) {
        int count = 0;
        
        while( n != 1) {
            for (int i = 2; i <= n; i++) {
                if ( n % i == 0) {
                    n/=i;
                    count+=i;
                    break;
                }
            }
        }

        return count;
    }
}