문제

[프로그래머스] 숫자 짝꿍
https://school.programmers.co.kr/learn/courses/30/lessons/131128

풀이

조건

• 두 정수 X, Y의 임의의 자리에서 공통으로 나타나는 정수 k(0 ≤ k ≤ 9)들을 이용하여 만들 수 있는 가장 큰 정수를 두 수의 짝꿍이라 합니다
  • 단, 공통으로 나타나는 정수 중 서로 짝지을 수 있는 숫자만 사용합니다
• X, Y의 짝꿍이 존재하지 않으면, 짝꿍은 -1입니다.
• X, Y의 짝꿍이 0으로만 구성되어 있다면, 짝꿍은 0입니다.
• 3 ≤ X, Y의 길이(자릿수) ≤ 3,000,000입니다.

풀이 순서

• X와 Y 각각 0 ~ 9 까지의 값을 몇 개 가지고 있는지 저장합니다.
  • 배열 xCheckCnt, yCheckCnt
• 9 ~ 0까지 x와 y가 가진 수 중 최솟값을 구해 StringBuilder에 최솟값만큼 해당 숫자를 넣습니다.
  • 시간 초과를 해결하기 위해 StringBuilder를 사용합니다.
  • 9 부터 0으로 가는 이유는 가장 큰 정수를 구해야 하기 때문입니다.
    • 추후에 정렬을 해주지 않아도 됩니다.
• -1, 0 을 반환해야 하는 조건을 체크합니다.

코드

Java

import java.util.*;

class Solution {
    public String solution(String X, String Y) {
        String answer = "";
        StringBuilder sb = new StringBuilder(); // 시간초과 해결을 위한 StringBuilder
        
        // char 배열로 변환
        char[] x = X.toCharArray();
        char[] y = Y.toCharArray();
        
        // 0 ~ 9 값들의 개수 저장할 배열
        int[] xCheckCnt = new int[10];
        int[] yCheckCnt = new int[10];
        
        // 개수 세기
        for(int i = 0; i < x.length; i++) {
            int tmp = x[i] - '0';
            xCheckCnt[tmp]++;
        }
        for(int i = 0; i < y.length; i++) {
            int tmp = y[i] - '0';
            yCheckCnt[tmp]++;
        }
        
        // 9 ~ 0까지 x와 y가 가진 수 중 최솟값을 구해 StringBuilder에 최솟값만큼 해당 숫자 넣기
        for(int i = 9; i >= 0; i--) {
            int cnt = Math.min(xCheckCnt[i], yCheckCnt[i]);
            for(int t = 0; t < cnt; t++) {
                sb.append(i); // StringBuilder에 입력
            }
        }
        
        // StringBuilder -> String 변환
        answer = sb.toString();
        
        // 일치하는 값이 없는 경우 -> -1 출력
        if(answer.length() == 0) {
            answer = "-1";
            return answer;
        }
        
        // 가장 큰 값이 0인 경우 -> 0 출력
        if(answer.charAt(0) == '0') {
            answer = "0";
        }

        return answer;
    }
}

정리

• String에 일일이 값을 추가했을 때 시간초과가 나서 StringBuilder를 사용해 해결했다.