[프로그래머스] 10진수를 2진수로 변환하기

1. 문제

---

2. 풀이 과정

---

• 10진수 --> 2진수 변환과정
  • 10진수에서 2를 나누어 나머지를 맨 뒤에 적는다.
  • 그 몫을 다시 2로 나누어 나머지를 그 앞에 적는다. 
  • 위의 과정을 몫이 0이 될 때까지 반복한다.
  • ex: 10 --> 1010

• 여기서 주목해야할 점은 첫번째에 나온 나머지가 최종 결과의 맨 마지막에 나온다는 점이다. 
• 이러한 특징을 고려했을 때 우리는 스택을 떠올릴 수 있다.
  • 나머지를 연산 순서대로 스택에 넣은 다음 순서대로 스택에서 데이터를 꺼내면 쉽게 답을 구할 수 있음 

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();
    }

시간복잡도

• O(logN)

 

4. 다른 정답 코드와 비교

---

[『코딩 테스트 합격자 되기 - 자바편』 해설 코드]

public static String solution(int decimal) {
    Stack<Integer> stack = new Stack<>();
    while (decimal > 0) {
        int remainder = decimal % 2;
        stack.push(remainder);
        decimal /= 2;
    }

    // String 의 + 연산은 시간복잡도 측면에서 성능이 좋지 않습니다.
    // 따라서 StringBuilder 를 사용했습니다.
    StringBuilder sb = new StringBuilder();
    while (!stack.isEmpty()) {
        sb.append(stack.pop());
    }

    return sb.toString();
}

시간복잡도

• O(logN)

내 코드와 동일한 것을 알 수 있다.

5. 피드백

---

• 저장한 순서의 역순으로 데이터들이 필요하다면 스택을 떠올리자