[ 프로그래머스 / JAVA / Level 2 ] 다음 큰 숫자

제출한 코드

 

1차 제출 코드 - 정확성 70점 , 효율성 0점 ( 시간 초과 0 )

import java.util.*;
class Solution {
    public int solution(int n) {
        int answer = 0;
        // 이진법 String으로 변환된 정수 n
        String binaryN = Integer.toBinaryString(n);
        
        int startIdx = -1;
        int finIdx = -1;
        
        // 1이 연속되는 index 찾기
        for(int i = binaryN.length()-1 ; i >= 0; i --){
            if(finIdx == -1 && binaryN.charAt(i) == '1'){
                finIdx = 0;
                startIdx = i;
            }
            
            if(finIdx == 0 && binaryN.charAt(i) == '0'){    
                finIdx = i;
            }
        }
        
        // 다음 큰 숫자를 2진법 기준 자리 마다 int[]에 저장
        int[] arr;
        
        // 연속 되는 경우가 0번 인덱스까지인 경우
        if(finIdx == 0){
            arr = new int[binaryN.length()+1];
            arr[0] = 1;
            arr[1] = 0;
            
            for(int i = arr.length-1; i > arr.length-1 - (startIdx-finIdx); i--){
                arr[i] = 1;
            }
        }
        // 아닌 경우
        else{
            arr = new int[binaryN.length()];
            for(int i = 0 ; i < finIdx ; i++){
                arr[i] = binaryN.charAt(i) - '0';
            }
            arr[finIdx] = 1;
            for(int i = arr.length-1; i > arr.length-1 - (startIdx-finIdx) +1 ; i--){
                arr[i] = 1;
            }
        }
        
        // 정답 구하기
        for(int i = 0 ; i < arr.length;i++){
            if(arr[i] == 1){
                answer += Math.pow(2, arr.length - (i+1));
            }
        }
        
        return answer;
    }
}

 

 

2차 제출 코드 - 정확성 70점 , 효율성 30점

import java.util.*;

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        String binaryN = Integer.toBinaryString(n);
        int startIdx = -1;
        int finIdx = -1;

        for(int i = binaryN.length()-1 ; i >= 0; i --){
            if(finIdx == -1 && binaryN.charAt(i) == '1'){
                finIdx = 0;
                startIdx = i;
            }
            
            if(finIdx == 0 && binaryN.charAt(i) == '0'){
                finIdx = i;
            }
        }
        
        if(finIdx == 0){
            int size = binaryN.length();
            
            answer += Math.pow(2, size);
            for(int i = size; i > size - (startIdx-finIdx); i--){
                answer += Math.pow(2, (size-i));
            }
        }else{
            int size = binaryN.length()-1;
            
            for(int i = 0 ; i < finIdx ; i++){
                if(binaryN.charAt(i) == '1'){
                    answer += Math.pow(2, size-i);
                }   
            }
            
            answer += Math.pow(2, size-finIdx);
            
            for(int i = size; i > size - (startIdx-finIdx) +1 ; i--){
                answer += Math.pow(2, size-i);    
            }
        }
        
        return answer;
    }
}

---

생각한 로직

 

1. 십진수로 입력받은 n을 이진수로 변환한다.

2. 뒤에서 부터 반복하면서 1이 제일 먼저 연속되는 구간을 찾는다.

3 - 1 0번 index까지 연속 되는 경우 전체 길이를 1 증가시킨다.

3 - 2 0번 index전에 종료되는 경우 길이는 그대로 가져간다.

4. ex ) 1111 -> 10111과 같이 연속되는 구간의 맨 처음 1을 1자리 증가시키고 나머지 연속된 1의 개수만큼 뒤에서부터 채운다.

5. Math.pow()를 이용해서 십진수 값을 계산한다.

 

---

틀렸던 이유

 

int [] arr에 저장하고 answer를 계산하는 작업이 불필요했다.

arr저장하는 로직에서 바로 연산을 진행하면 시간 초과를 해결할 수 있다.