lango

찍먹? 부먹?
난 부먹 개발자.

2 minute read



입출력 예시

Input-1
5
Output-1
2

Input-2
6
Output-2
2

Input-3
5000
Output-3
5


문제 풀이

이 문제는 N의 범위가 최대 10억이기에 효율성을 잘 고려해야 한다.
n을 2로 나눠가며 건전지 카운트를 세는 방식과 n을 2진수로 변환한 후 1의 개수를 세는 두가지 방식으로 풀어보았다.

먼저 문제에서 순간이동하고 K번 점프하는 패턴을 살펴보자.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

n=1, 0->1
    건전지 1 사용
n=2, 0->1, 1*2=2
    건전지 1 사용
n=3, 0->1, 1*2=2, 2->3
    건전지 2 사용
n=4, 0->1, 1*2=2, 2*2=4
    건전지 1 사용
n=5, 0->1, 1*2=2, 2*2=4, 4->5
    건전지 2 사용
n=6, 0->1, 1*2=2, 2->3, 3*2=6
    건전지 2 사용
n=7, 0->1, 1*2=2, 2->3, 3*2=6, 6->7
    건전지 3 사용
n=8, 0->1, 1*2=2, 2*2=4, 4*2=8
    건전지 1 사용
n=9, 0->1, 1*2=2, 2*2=4, 4*2=8, 8->9
    건전지 2 사용
n=10, 0->1, 1*2=2, 2*2=4, 4->5, 5*2=10
    건전지 2 사용

2로 나눠떨어지는 수의 경우 건전지 사용수가 1이고, 아니라면 건전지를 1 추가로 사용해야 함을 알 수 있다.



2로 나눠가며 2로 나눠 떨어지는지 검증하기

주어진 n까지 반복하며 카운트를 세는 방식은 시간이 오래 걸리기에 거꾸로 n에서부터 0이 될 때까지 나누는 방식으로 풀어보니 정답이었다.
만약 n이 2로 나눠 떨어진다면 건전지를 사용하지 않아도 된다. 그런데 2로 나눠 떨어지지 않는 수라면 (2로 나눠떨어지는 수)+1 로 구성됨을 알 수 있다.
그렇다면 결국 2로 나눠 떨어지지 않을 때 건전지를 1씩 사용할 수 밖에 없고, 다음 n-1을 하여 2로 나눠떨어지는 수로 검증하면 된다.

1
2
3
4
5
6
7

15 -> 15%2!=0 -> 14+1 
14 -> 14%2==0
7 -> 7%2!=0 -> 6+1
6 -> 6%2==0
3 -> 3%2!=0 -> 2+1
2 -> 2%2==0
1 -> 1%2!=0 -> 0+1


위 아이디어를 코드로 작성해보자.

1
2
3
4
5
6
7

while(n > 0) {
    if(n%2 == 0) n = n/2;
    else {
        n = (n-1) / 2;
        ans++;
    }
}

2로 나눠떨어지는 수라면 n을 n/2 값으로 변경하고 다시 반복한다.
2로 나눠떨어지지 않는 수라면 n을 (n-1)/2 값으로 변경하고 건전지 사용 수를 1 증가시킨다.
n이 0이 될 때까지 위 과정을 반복하면 건전지를 최소로 사용할 수 있다.



2진수 변환후 1의 개수 세기

문제를 보고 2를 곱하는 것으로 보아 n을 2진수로 변환한 후의 1의 개수인가 살펴보았고, 예상한 대로였다.
1의 개수를 셀 때 반복문으로 세면 시간초과가 발생하기에 본 2진수 문자열 길이에서 1을 제외한 2진수 문자열 길이를 빼줌으로 1의 개수를 셀 수 있었다.

작성한 코드는 다음과 같다.

1
2

String binary = Integer.toBinaryString(n);
return binary.length() - binary.replace(String.valueOf(1), "").length();


작성 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        long start = System.currentTimeMillis();
        solution(n);
        long end = System.currentTimeMillis();
        System.out.println("\n수행시간 = " + (end-start));
    }

    public static int solution(int n) { // 2로 나눠떨어지는지 검증
        int ans = 0;

        while(n > 0) {
            if(n%2 == 0) n = n/2;
            else {
                n = (n-1) / 2;
                ans++;
            }
        }

        return ans;
    }

    public static int solution2(int n) { // 2진수 변환하고 1의 개수 세기
        String binary = Integer.toBinaryString(n);
        return binary.length() - binary.replace(String.valueOf(1), "").length();
    }
}

회고

  • 2와 연관지어 문제에 접근해야 하기 때문에 나눗셈연산, 나머지연산 등 여러 방식을 고민해볼 수 있었고, 2진수 변환후 1의 개수을 통해서도 정답을 낼 수 있었다.
  • 특정 문자의 개수를 셀 때, String의 replace() 메서드를 통해 본 문자열 길이에서 특정 문자가 제거된 문자열 길이를 빼 구할 수 있었다.

You may also enjoy