프로그래머스 - 숫자 짝꿍

 

---

 

import java.util.*;

class Solution {
    public String solution(String X, String Y) {
        List<Character> listX = new ArrayList<>();
        List<Character> listY = new ArrayList<>();
        List<Integer> couple = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        
        for(char c : X.toCharArray()) listX.add(c);
        for(char c : Y.toCharArray()) listY.add(c);
        
        for(int i = 0; i < listX.size(); i++) {
            for(int j = 0; j < listY.size(); j++) {
                if(listX.get(i) == listY.get(j)) {
                    couple.add(listY.get(j) - '0');     // 같은 짝꿍이 있다면, 짝궁 리스트에 추가
                    listY.remove(j);                    // 비교 리스트에서 삭제
                }
            }
        }
        
        // 겹치는 수가 없을 때
        if(couple.size() == 0) return "-1";
        
        Collections.sort(couple);  
        Collections.reverse(couple); // 내림차순으로 정렬
         
        // 내림차순 정렬 후, 처음으로 오는 수가 0 일 때 -> 모든 수가 0
        if(couple.get(0) == 0) return "0";
        
        for(int c : couple) sb.append(c);
        
        return sb.toString();
    }
}

 

문제를 처음 시도했을 때의 코드입니다.

3,000,000 까지의 자리수가 있지만 생각없이 2중 for문을 사용하여.. 시간 초과가 났었습니다.

 

개선 전 시간

---

 

import java.util.*;

class Solution {
    public String solution(String X, String Y) {
        HashMap<Integer, Integer> mapX = new HashMap<>();
        HashMap<Integer, Integer> mapY = new HashMap<>();
        StringBuilder couple = new StringBuilder();
        
        // 0 ~ 9 초기화
        for(int i = 0; i < 10; i++) {
            mapX.put(i, -1);
            mapY.put(i, -1);
        }
        
        // X, Y가 갖고 있는 수 체크
        for(char c : X.toCharArray()) mapX.put(c - '0', mapX.getOrDefault(c - '0', 0) + 1);
        for(char c : Y.toCharArray()) mapY.put(c - '0', mapY.getOrDefault(c - '0', 0) + 1);
          
        // X, Y 비교하여 List 추가
        for(int i = 0; i < 10; i++) {
            for(int j = 0; j <= (Math.min(mapX.get(i), mapY.get(i))); j++) {
                couple.append(i);
            }
        }
        
        if(couple.toString().equals("")) return "-1";
        if(couple.toString().endsWith("0")) return "0";
        return couple.reverse().toString();
    }
}

코드를 개선하여 map을 사용해 X, Y에서 각각 0 ~ 9 가 몇 개 있는지 갯수를 구하고, 둘 중 비교하여 작은 수만큼 같은 숫자를 공유하는 것이기 때문에 작은 숫자를 구해 StringBuilder를 이용해 0부터 시작하는 문자열을 만들었고, 뒤집어서 가장 큰 수로 만들어주었습니다.

각 조건에 맞춰 겹치는 숫자가 없으면 -1, 또한 겹치는 숫자가 0으로만 이루어져 있다면 00000 이 있을 수 있는데 만약 9120 처럼 마지막이 0으로 끝날 수 있기 때문에 뒤집기 전에 마지막이 0으로 끝나는지 확인하여 0으로 시작하는 문자열인 경우 0을 반환하도록 했습니다.

 

개선 후 시간

 

시간 초과 이외에도 전체적인 시간 소요가 절반정도 줄었습니다.