[코딩테스트합격자되기-자바편] 문제09. 10진수를 2진수로 변환하기

💡 해당 풀이는 코딩 테스트 합격자되기 - 자바편 에서 발췌된 내용을 바탕으로 작성되었습니다.

 

문제

내용

10진수를 입력받아 2진수로 변환해 반환하는 solution() 함수를 구현하세요.

 

 

제약 조건

• decimal은 1이상 10억 미만의 자연수

 

 

기록하기

💡 어디까지 생각해봤는지 단계적으로 기록해봅니다.

 

풀이

풀이 시간

 

시작 시각	종료 시각	총 소요 시간
14:09	14:16	7분

 

 

문제 분석

 

제약 사항 파악 & 테스트 케이스 작성

 

• decimal은 1이상 10억 미만의 자연수

 

입력값 분석

💡 입력값을 분석하면 문제에서 요구하는 알고리즘의 시간 복잡도를 간접적으로 파악할 수 있습니다.

decimal	반환값
10	1010
27	11011
12345	11000000111001

 

의사 코드 작성

💡 의사 코드는 동작 중심으로 작성하는 것이 중요합니다.

💡 의사 코드는 문제 해결 순서로 작성합니다.

💡 의사 코드를 충분히 테스트해봅니다.

 

 

1. Long이 제공해주는 메소드 활용

solution(int decimal) {
	// 10진수를 2진수로 변환 (Long 이 제공해주는 메소드 활용)
}

 

 

2. Stack 활용

solution(int decimal) {
	// 1. 몫을 저장할 스택 생성
	// 2. decimal이 0이 될때까지 while 문
	while (decimal > 0) {
		// 3. decimal 을 2로 나누기
		// 4. 1을 stack 에 넣기
		// 5. 나머지를 decimal 에 치환
	}
}

 

 

구현

// Long 이 제공해주는 메소드 활용하기  
public static String solution(int decimal) {  
    return Long.toBinaryString(decimal);  
}

public static String solution(int decimal) {  
    Stack<Integer> stack = new Stack<>();  
    while (decimal > 0) {  
        int div = decimal / 2;  
        int mod = decimal % 2;  
        stack.push(mod);  
        decimal = div;  
    }
    StringBuilder sb = new StringBuilder();  
    while (!stack.isEmpty()) {  
        sb.append(stack.pop());  
    }
    return sb.toString();  
}

 

 

 

복기하기

 

저자 권장 시간	권장 시간 복잡도
30분	O(logN)

 

 

답안과 나의 풀이를 비교해보세요

public static String solution(int decimal) {  
    Stack<Integer> stack = new Stack<>();  
    while (decimal > 0) {  
        int remainder = decimal % 2;  
        stack.push(remainder);  
        decimal /= 2;  
    }
    StringBuilder sb = new StringBuilder();  
    while (!stack.isEmpty()) {  
        sb.append(stack.pop());  
    }
    return sb.toString();  
}

 

 

 

요약하기

• N이 1이 될 때 까지 2로 계속 나누는 연산횟수는 O(logN)
• StringBuilder를 사용한 코드의 시간 복잡도는 O(logN)