프로그래머스 lv2 다음 큰 숫자

문제 링크

다음 큰 숫자

풀이

• 처음에 이렇게 풀고자 하였다.
  • 주어진 int를 binaryString 메서드를 사용해서 2진법 string으로 바꾼다.
  • 그 다음에 string을 char 리스트로 바꿔서, Collctions.frequecy 함수를 사용해서 1의 개수를 카운팅해준다.
  • 이 방법을 주어진 int + 1부터 해서 진행한다.
• 그 결과 나온 풀이는 다음과 같다.

import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

class Solution {
    public int solution(int n) {
        String binaryString = Integer.toBinaryString(n);
        List<Character> characters = binaryString.chars()
        										 .mapToObj(c -> (char) c)
                                                 .collect(Collectors.toList());
                                                 
        int frequency = Collections.frequency(characters, '1');

        for (int i = n + 1; ; i++) {
            List<Character> characterList = Integer.toBinaryString(i).chars()
            														 .mapToObj(c -> (char) c)
                                                                     .collect(Collectors.toList());
                                                                     
            int nextFrequency = Collections.frequency(characterList, '1');

            if(frequency == nextFrequency){
                return i;
            }
        }
    }
}

• 정확성 테스트까지는 통과하였으나, 효율성 테스트에서 시간초과로 전부 탈락.

• 다른 방법이 없는지 확인해보았다.
• Integer의 함수중에 bitcount()라는 함수가 있었다.
• 쉽게 말하면 이진수에서 1의 개수를 세어주는 함수이고, true bit를 찾아주는 함수이다.
• 이거 쓰면 더 빠르겠다 싶어서 적용해보았다.

class Solution {
    public int solution(int n) {
        int frequency = Integer.bitCount(n);

        for (int i = n + 1; ; i++) {
            if(frequency == Integer.bitCount(i)){
                return i;
            }
        }
    }
}

• 정확성, 효율성 모두 통과하였다.

매번 코테 풀때마다 드는 생각은...이걸 어떻게 다 알고있는건가..