[Java] 프로그래머스(level-1) - 숫자 짝꿍

문제 풀이

---

주어진 X와 Y 문자열에서 공통되는 문자들을 찾아 가장 큰 수로 만들어야 한다.

초기 아이디어 도출

• X와 Y를 각각 순회하며 동일한 값들을 별도로 저장한다. 이 때, 연속으로 같은 수가 올 수 있음을 염두해야 한다.
• 별도로 저장한 문자들을 가장 큰 수, 즉 내림차순으로 만들어 반환한다.

먼저 X와 Y에서 동일한 문자를 찾는 코드를 작성하였다.

ArrayList<Integer> list = new ArrayList<>();

for(int i=0; i<X.length(); i++) {
    for(int j=0; j<Y.length(); j++) {
        if(X.charAt(i) == Y.charAt(j)) {
            list.add(Integer.parseInt(X.substring(i, i+1)));
            Y = Y.substring(0, j) + "" + Y.substring(j+1, Y.length());
        }
    }
}

이중 for문을 순회하며 X와 Y의 각 문자 중 같은 문자를 list에 저장하는 코드를 작성하였는데, 이후 코드를 제출하니 시간초과가 발생하였다.

시간초과 발생

그런데 이중 for문으로 X와 Y를 기준으로 각 숫자들마다 같은 수(짝꿍)을 찾으니 시간초과가 발생한다.
다시 문제를 잘 읽어보니 X와 Y의 길이가 최대 3,000,000 까지 올 수 있음을 고려하지 않았기 때문임을 알 수 있었다.

최종 아이디어 도출

어떻게 시간초과를 해결할 수 있을까?
X와 Y 기준으로 숫자를 탐색하지 않고, X와 Y 각각 0~9까지의 카운트를 가지는 배열을 활용하면 이중 for문 없이 for문 하나로 해결할 수 있을 것이라 생각하였다.

• 0~9까지 순회하며 X와 Y의 숫자가 몇번 나왔는지를 카운트하여 별도의 배열에 저장한다.
• 카운팅된 X와 Y 배열에서 카운팅된 숫자 중 공통된 숫자가 있는지 확인한다.
• 가장 큰 수로 만들어야 하기에 9~0 순서로 순회하며 새로운 문자열에 내림차순 순서로 저장한다.

이제 최종 아이디어를 토대로 코드를 작성해보자.

StringBuilder sb = new StringBuilder();

// X와 Y가 0~9까지 몇개의 수를 가지고 있는지 배열에 카운트.
int[] X_arr = new int[10];
int[] Y_arr = new int[10];

최종적으로 반환할 문자열은 StringBuilder에 담아서 반환할 것이기에 StringBuilder를 하나 선언하자.
그리고 0~9까지 X와 Y에서 각각 카운트할 두 배열을 초기화한다.

// X와 Y에서 0~9 중 출몰한 숫자를 X_arr에 카운트
countArr(X, X_arr); 
countArr(Y, Y_arr);

그리고 X와 Y의 숫자들을 카운트하여 각각 X_arr와 Y_arr에 카운트한다.

public static void countArr(String str, int[] arr) {
    for(int i=0; i<str.length(); i++) {
        int idx = Integer.parseInt(String.valueOf(str.charAt(i)));
        arr[idx]++;
    }
}

countArr 함수 내용이다.
X와 Y를 순회하며 나온 숫자의 X_arr의 인덱스를 증가시킨다.

예들 들어 X=5525, Y=1255라면 X_arr=[0,0,1,0,3,0,0,0,0,0], Y_arr=[0,1,1,0,0,2,0,0,0,0]가 된다.

// 9~0까지 돌면서 X와 Y의 공통된 수를 StringBuilder에 저장
for(int i=9; i>=0; i--) {
    while(X_arr[i] >= 1 && Y_arr[i] >= 1) {
        X_arr[i]--;
        Y_arr[i]--;
        sb.append(i);
    }
}

X와 Y에서 어떤 수가 나왔는지를 알았으니, 두 문자열에서 공통된 문자를 찾는다.
이 때, 공통 된 수를 통해 가장 큰 수를 만들어야 하기에 0~9 순서가 아닌 9~0 순서로 내림차순으로 반복한다.

X_arr, Y_arr의 카운트가 1 이상인 문자는 공통된 수이기 때문에 해당 문자를 StringBuilder에 담으면 된다.
하지만 X와 Y에서 동일한 숫자가 연속으로 존재할 수 있기 때문에 카운트가 1 이상이어도 카운트횟수가 다를 수 있다.

그렇기에 별도로 while문을 순회하며 카운트가 1이 될 때까지 해당 문자에 대한 카운트를 X_arr, Y_arr에서 감소시키면서 StringBuilder에 저장하면 연속으로 존재하는 문자를 담을 수 있다.

if(sb.toString().length() == 0) return "-1";
else if(sb.toString().startsWith("0")) return "0";
else return sb.toString();

X와 Y의 공통된 문자를 찾아 내림차순으로 StringBuilder에 담는 것까지 성공하였다.
마지막으로 이 StringBuilder를 String으로 형변환하여 반환하면 된다.

그런데, 문제 요구사항을 살펴보면 숫자 짝꿍이 존재하지 않을 떄에는 “-1”을 반환해야 한다고 하며, 반환할 문자열은 0으로 시작하지 않는다고 한다.

• StringBuilder에는 공통된 문자를 담기 때문에 숫자 짝궁이 존재하지 않을 때는 sb에는 값이 없기 때문에 sb를 String으로 형변환후 길이가 0이라면 “-1”을 반환하면 된다.
• 반환할 문자열이 0으로 시작한다는 것은 X와 Y에서 공통된 문자를 조합해 가장 큰수를 만들어도 0으로 시작한다는 것이다. “00”이 올수도 “000…” 등 무수히 많은 0의 개수를 가진 문자열이 올 수 있기 때문에 결국 “0”만 반환하면 된다.

작성 코드

---

import java.util.*;

class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String X = sc.nextLine();
        String Y = sc.nextLine();

        long start = System.currentTimeMillis();
        solution(X, Y);
        long end = System.currentTimeMillis();
        System.out.println("\n수행시간 = " + (end-start));
    }
    
    public static String solution(String X, String Y) {
        StringBuilder sb = new StringBuilder();

        // X와 Y가 0~9까지 몇개의 수를 가지고 있는지 배열에 카운트.
        int[] X_arr = new int[10];
        int[] Y_arr = new int[10];
        
        countArr(X, X_arr);
        countArr(Y, Y_arr);

        // 9~0까지 돌면서 X와 Y의 공통된 수를 StringBuilder에 저장
        for(int i=9; i>=0; i--) {
            while(X_arr[i] >= 1 && Y_arr[i] >= 1) {
                X_arr[i]--;
                Y_arr[i]--;
                sb.append(i);
            }
        }

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

    public static void countArr(String str, int[] arr) {
        for(int i=0; i<str.length(); i++) {
            int idx = Integer.parseInt(String.valueOf(str.charAt(i)));
            arr[idx]++;
        }
    }
}

회고

• 시간초과를 해결하기 위한 아이디어를 새로 생각해내는게 어려웠다. 주어진 N의 범위가 클 경우를 항상 염두해두고 초기 아이디어를 잘 구상해야 시간이 덜 잡아먹을 것이다.
• 배열을 활용해 각 문자열들의 숫자들을 카운팅하는 방식에 대해서는 잘 숙지해두어야 겠다.