프로그래머스 스쿨 Lv.1 - 숫자 짝꿍(string 시간복잡도)

문제

 

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

프로그래머스

 

 

정답

 

class Solution {
    public String solution(String X, String Y) {
        String[] xSplit = X.split("");
        String[] ySplit = Y.split("");
        int[] xCount = new int[10];
        int[] yCount = new int[10];
        
        for(String check : xSplit){
            xCount[Integer.parseInt(check)]++;
        }
        for(String check : ySplit){
            yCount[Integer.parseInt(check)]++;
        }
        
        StringBuilder answerBuilder = new StringBuilder();
        
        for(int i=9;i>=0;i--){
            if(xCount[i]==0||yCount[i]==0) continue;
            int plusCounter = xCount[i]>yCount[i]?yCount[i]:xCount[i];
            String tempString = String.valueOf(i);
            while(plusCounter>0){
                answerBuilder.append(tempString);
                plusCounter--;
            }
        }
        String answer = answerBuilder.toString();
        
        if(answer.equals("")) return "-1";
        if((answer.split("")[0]).equals("0")) return "0";
        return answer;
    }
}

 

String을 split으로 나누어 각 숫자의 등장횟수를 센다.

 

그리고 횟수를 비교하여 둘다 0보다 큰 경우 작은 횟수만큼 더해준다.

 

 

 

 

오답과 고찰

 

class Solution {
    public String solution(String X, String Y) {
        String[] xSplit = X.split("");
        String[] ySplit = Y.split("");
        int[] xCount = new int[10];
        int[] yCount = new int[10];

        for(String check : xSplit){
            xCount[Integer.parseInt(check)]++;
        }
        for(String check : ySplit){
            yCount[Integer.parseInt(check)]++;
        }

        String answer = "";

        for(int i=9;i>=0;i--){
            if(xCount[i]==0||yCount[i]==0) continue;
            int plusCounter = xCount[i]>yCount[i]?yCount[i]:xCount[i];
            String tempString = String.valueOf(i);
            while(plusCounter>0){
                answer+=tempString;
                plusCounter--;
            }
        }
        if(answer.equals("")) return "-1";
        if((answer.split("")[0]).equals("0")) return "0";
        return answer;
    }
}

 

기존의 String을 처리하던대로 숫자의 적은쪽 개수만큼 String에 + 를 하려고했다.

 

그랬더니 일부 유형에서 시간초과가 발생하여 쓴맛을 보았다.

 

 

 

이해를 위해 알아야할것

 

자바에서 String 클래스는 불변(immutable)하다.

 

이를 생각했을때, 자바에서 "A"+"B"를 한다는 것은 단순히 한글자를 추가를 하는것이 아닌 새로운 문자열을 만든다는 것이 알아야할 정보였다.

 

매번 새로운 문자열을 만들기때문에 성능과 시간상으로 StringBuilder를 이용하여 문자열을 모두 조립 후  String으로 변환하는것과 큰 차이를 가지게 된다.

 

따라서 String을 붙이거나 변형하는 경우 StringBuilder를 이용하여 처리하는 것이 효율적이다.

 

 

 

이 문제의 의도 또한 그렇게 만들어 진 것으로 생각하게되었다.