[코딩테스트] (Java) 십진수를 이진수로 변환하기 (스택)

📑 1. 문제설명

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

 

제약조건

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

입출력 예

decimal	return
10	1010
27	11011
12345	11000000111001

 

💡 2. 풀이 과정

10진수를 2진수로 표현하는 과정은 이미 수학적으로 증명된 것이기 때문에 간단하게 적는다.

1. 10진수 N을 2로 나눈 나머지, 즉 %2 연산을 한 값을 저장하고, N은 다시 2로 나눈다.
2. 몫이 0이 아니라면 나머지를 버리고 다시 1을 수행한다
3. 모든 과정이 끝나고 1에서 저장한 수를 뒤부터 순서대로 가져와 붙인다.

 

 

예를 들어 십진수 13을 위 과정대로 2진수로 변환하는 모습은 위 그림과 같다. 13을 2로 나누어가면서 나눈 나머지를 순서대로 저장한 후, 이 과정을 몫이 0이 될 때까지 반복한다. 몫이 0이 되면 저장한 값을 뒤에서부터 순서대로 읽으면 1101으로 이진수 변환이 완료된다.

 

이 문제는 전형적인 스택 문제이다. 나머지를 스택에 쌓고 하나씩 꺼내면 답이 나온다.

초기에는 13으로 시작한다. 13을 2로 나누고 나머지를 스택에 푸시한다. 13을 2로 나눈 나머지가 1이기 때문에 1을 스택에 Push 한다. 

화면 스크린샷 했더니 이렇게 됐오 ㅠㅠ

다음은 13을 2로 나눈 몫 6을 다시 2로 나눈다. 나머지가 0이기 때문에 0을 푸시하고, 3을 2로 나눈 나머지는 1이기 때문에 1을 푸시한다. 

 

마지막으로 십진수 13을 몫이 0이 될 때까지 나눈 결과로 스택에는 나머지인 1, 0, 1, 1 이 순서대로 쌓이게 된다.

 

연산을 다 긑낸 후에 스택 맨 위에 쌓인 값부터 stack.pop()으로 꺼내오면 13을 이진수로 변환한 1101이 된다. 

---

⭐ 3. 정답코드

public static String solution(int decimal) {
        Stack<Integer> stack = new Stack<>(); // 나머지를 저장할 스택
        
        while(decimal != 0) { // 몫이 0이 될 때 까지 반복
            stack.push(decimal % 2); // 나머지 스택에 넣기 
            decimal /= 2; // 2로 나누기
        }

        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty()) {
            sb.append(stack.pop()); // 스택에 있는 나머지 꺼내기
        }
        return sb.toString();
    }