프로그래머스 - 숫자 짝꿍 JAVA :: 131128

문제링크

숫자 짝꿍 | 프로그래머스 스쿨 (programmers.co.kr)

---

문제 이해하기

• 3 ≤ X, Y의 길이(자릿수) ≤ 3,000,000입니다.
  • 나름 신경 쓴다고 썼는데 이것 때문에 시간을 많이 날렸다. 단순히 삼백만이 아니라 자릿수 삼백만이다… 어마어마한 숫자가 올 수 있다는 뜻
• 같은 수가 중복될 수 있다.
  • X = "5255", Y = "1255"일 중복되는 수는 2, 5, 5이다.
  • 주의할 점은 X의 5는 3개이지만 Y에는 2개만 있으므로 5는 2개만 짝꿍이다.
• 짝꿍이 없다면 "-1"을 반환한다.
• 기본적으로 숫자 개념이므로 "000..."같은 수는 없으므로 0으로 시작하면 0을 반환한다.

---

문제풀이

1번 풀이 (시간초과)

import java.util.Arrays;

public String solution(String X, String Y) {
    char[] chars = X.length() <= Y.length() ? X.toCharArray() : Y.toCharArray();
    StringBuilder sbStandard = X.length() > Y.length() ? new StringBuilder(X) : new StringBuilder(Y);
    StringBuilder sbAnswer = new StringBuilder();

    for(char ch : chars) {
        for(int j=0; j<sbStandard.length(); j++) {
            if(ch == sbStandard.charAt(j)) {
                sbAnswer.append(ch);
                sbStandard.deleteCharAt(j);
                break;
            }
        }
    }

    char[] answers = sbAnswer.toString().toCharArray();
    Arrays.sort(answers);
    sbAnswer = new StringBuilder(String.valueOf(answers)).reverse();

    if(sbAnswer.length() == 0) return "-1";
    else if(sbAnswer.charAt(0) == '0') return "0";
    else return sbAnswer.toString();
}

X든 Y든 어차피 중복되는 짝꿍만 구하는 개념이니까, 길이가 더 작은 문자열을 기준으로 삼고 짝꿍이 되는 수를 sbAnswer에 담아서 정렬 후 반환하려고 했다.
통과한 테스트는 속도도 꽤 준수했지만 11~15번 테스트는 시간초과가 나왔다.
비슷하게 이런저런 시도를 했지만 계속 시간초과가 나왔다.

• 문제가 되는 코드

    for(char ch : chars) {
        for(int j=0; j<sbStandard.length(); j++) {
            if(ch == sbStandard.charAt(j)) {
                sbAnswer.append(ch);
                sbStandard.deleteCharAt(j);
                break;
            }
        }
    }

  자릿수가 길어질수록 append하고 delete하는 처리시간이 너무 많이 소요된다.
  생각의 전환이 필요했다.

2번 풀이 (통과)

public String solution(String X, String Y) {
    int[][] numbers = new int[2][10];
    int lenX = X.length(), lenY = Y.length();
    StringBuilder sb = new StringBuilder();

    for(int i=0; i<Math.max(lenX, lenY); i++) {
        if(i < lenX) numbers[0][X.charAt(i)-'0']++;
        if(i < lenY) numbers[1][Y.charAt(i)-'0']++;
    }

    for(int i=9; i>=0; i--) {
        int partner = Math.min(numbers[0][i], numbers[1][i]);
        while(partner-- > 0) sb.append(i);
    }

    if(sb.length() == 0) return "-1";
    else if(sb.charAt(0) == '0') return "0";        
    return sb.toString();
}

어차피 숫자는 0~9범위에서 벗어나지 않고, 짝꿍이 되는 숫자와 그 개수만 구하면 되니까 int형 배열 numbers를 만들었다.

• 핵심코드

    for(int i=0; i<Math.max(lenX, lenY); i++) {
        if(i < lenX) numbers[0][X.charAt(i)-'0']++;
        if(i < lenY) numbers[1][Y.charAt(i)-'0']++;
    }

  테스트 코드는 "5525", "1255"로 가정한다면 배열 nubmers는 아래와 같은 값을 가지게 된다.

    num:    [0][1][2][3][4][5][6][7][8][9]
    ------------------------------------
    X:        [0][0][1][0][0][3][0][0][0][0]
    Y:        [0][1][1][0][0][2][0][0][0][0]

  각 배열의 인덱스 위치가 숫자범위 0~9의 개념이 되어 값을 넣는다.

---