[Algorithm]3진법 뒤집기(2.87ms -> 0.05ms)

01. 문제내용

https://school.programmers.co.kr/learn/courses/30/lessons/68935

프로그래머스

 

02. 문제풀이로 배운점

10진법으로 제공된 수를 3진법으로 바꾼 후 reverse하여 다시 10진법으로 반환하는 알고리즘이다. 초반 풀이에는 stack을 쓰면 유용할 것 같아 Java에서 제공하는 Stack을 사용하여 문제를 풀이하였다. 

 

다른 사람들의 풀이에 StringBuilder가 있어 코드를 개선해보았다. 최대 2.87ms -> 0.05ms 까지 runtime을 개선할 수 있었다. 기존 코드에서 사용한 stack보다 StringBuilder가 더 빠를 수 있었던 이유는 우선  반복문들이 제외되고 자바에서 제공하는 기본 메서드를 적용할 수 있어서 인 것 같다. 

StringBuilder는 StringBuffer의 쓰레드 동기화를 제외하고 있다. 따라서 멀티 쓰레드로 작성된 프로그램이 아닌 경우, StringBuilder를 사용해주는 것이좋다. StringBuilder와 StringBuffer를 사용할 때 주의할 점은 문자열의 길이를 고려 할 때 버퍼의 길이를 충분히 잡아야 한다는 것이다. 편집 중인 문자열이 버퍼의 길이를 넘어서게 되면 버퍼의 길이를 늘려주는 작업이 추가로 수행되어야 하기 때문에 작업 효율이 떨어진다.

그리고 Java에서 Stack을 사용하기 보다는 Deque를 사용하는 것이 더 좋다. 공식문서에서 권장하고 있기 때문에 다음부터는 Stack대신 Deque를 사용해야겠다.

 

https://tecoble.techcourse.co.kr/post/2021-05-10-stack-vs-deque/

Java 의 Stack 대신 Deque

 

03. 문제풀이 방법

 1) Stack사용

import java.util.Stack;

class Solution {
    public int solution(int n) {
        String result = "";
        String stringN = Integer.toString(n, 3);
        
        Stack<String> stack = new Stack<>();
        
        for(int i = 0; i < stringN.length(); i++){
            String temp = Character.toString(stringN.charAt(i));
            stack.push(temp);
        }
        
        for(int i = 0; i < stringN.length(); i++){
            result = result + stack.pop();
        }
        
    
        return Integer.parseInt(result,3);
    }
}

 

 

2) StringBuilder 사용

import java.util.Stack;

class Solution {
    public int solution(int n) {
        String stringN = Integer.toString(n, 3);
        StringBuilder sb = new StringBuilder(stringN);
        String temp = sb.reverse().toString();
        
        return Integer.parseInt(temp, 3);
    }
}