Lv.2 : 다음 큰 숫자

👉 문제링크

프로그래머스

---

---

🔸 문제 분석 🔸

• 자연수 n의 다음 큰 숫자를 구한다.
• 다음 큰 숫자는 3가지로 정의한다.
  • n보다 큰 자연수
  • 2진수로 변환했을 때 n과 다음 큰 숫자의 1의 개수가 같다.
  • 다른 두 조건을 만족하는 가장 작은 수

🔸 문제 풀이 🔸

• n을 2진수 변환 후 1의 개수를 세서 저장한다.
• n을 1씩 증가해가며 다음 큰 숫자의 정의를 만족하는지 확인한다.
  
  • 2진수 문자열의 1의 개수를 세는 부분에서 최적화가 필요하다.

---

🔸 코드 🔸

class Solution {
    public int solution(int n) {
        int one_cnt = count_bit(Integer.toBinaryString(n));
        
        while(true) {
            int next_num_one_cnt = count_bit(Integer.toBinaryString(++n));
            if(one_cnt == next_num_one_cnt) break;
        }
        
        return n;
    }
    
    private int count_bit(String binaryString) {
        int count = 0;
        int binary = Integer.parseInt(binaryString, 2);

        while (binary != 0) {
            count += (binary & 1); // 오른쪽에서부터 한 비트씩 확인
            binary >>>= 1; // 오른쪽으로 비트 이동
        }
    
        return count;
    }
}

🔸 코드 해석 🔸

• 다음 큰 수가 만족 할 때까지 n을 +1하며 계산을 반복한다.
• 2진수 문자열에서 비트연산을 통해 1의 개수를 카운트한다.

---

🔸 오답 코드 1 🔸

class Solution {
    public int solution(int n) {
                   
        int one_cnt = Integer.toBinaryString(n).replaceAll("0","").length();
        
        while(true) {
            int next_num_one_cnt = Integer.toBinaryString(++n).replaceAll("0","").length();
            if(one_cnt == next_num_one_cnt) break;
        }
        
        return n;
    }
}

 

• 2진수 문자열에서 0을 제거하구 길이를 세서 1의 개수를 구한다.
• replaceAll과 length 모두 문자열을 전체 순회해서 확인하기 때문에 시간복잡도가 너무 커져 효율성 테스트에서 시간초과가 난다.

🔸 오답 코드 2 🔸

class Solution {
    public int solution(int n) {
        
        String binary = Integer.toBinaryString(n);
        
        char[] bc = binary.toCharArray();
        int last_idx = binary.lastIndexOf('1');

        String plus_ones = ""; // 추가해야 될 1들
        
        while(true) {
            if(last_idx == 0) {
                bc[0] = '0';
                binary = "1" + String.valueOf(bc);
                break;
            } else if (bc[last_idx-1] == '1') {
                bc[last_idx] = '0';
                last_idx--;
                plus_ones += "1";
            } else {
                bc[last_idx] = '0';
                bc[last_idx-1] = '1';
                binary = String.valueOf(bc);
                break;
            }
        }
        
        int answer = Integer.parseInt(binary, 2);
        
        if(plus_ones.length() > 0) {
            answer += Integer.parseInt(plus_ones, 2);
        }
        
        return answer;        
    }
}

• 오답 1번에서 다른쪽을 시도해보고자 1의 개수를 세는게 아닌, 가장 오른쪽 1의 인덱스를 찾아 계산하는 방식을 사용했다.
  • 1의 개수가 같아야 하므로, 가장 오른쪽 1의 인덱스에서 1을 더해서 2진수를 계산한다.
  • 사라진 1만큼 더해주면 다음 큰 수를 구할 수 있다.
• 효율성 테스트에서 절반정도는 시간초과가 뜨게 된다.

---

🔸 end 🔸

• 간단한 문제라고 생각했는데, replaceAll()과 length()의 위험성을 알게 되었다.
• 다른 풀이를 봤는데 배울 점이 많았다.
  • 단순하게 2진법 패턴으로 비트연산을 통해 구하는 코드가 한 줄 풀이로 가장 짧고 효율적으로 보였는데 이해하지 못했다. 계산을 따라가보면 비트 연산을 구현한게 보이는데 원리까진 알지 못했다.
  • 나는 1을 비트연산으로 구하기 위해 직접 반복문을 돌렸는데, Integer.bitCount()라는 메서드가 있었다. 다음부터는 활용해야겠다.