[프로그래머스] 숫자 짝꿍

fsm12·2023년 7월 1일

프로그래머스

목록 보기

26/57

문제링크

문제 이해

[ 입력형태 / 조건 ]

X, Y
두 정수 X, Y | "100", "2345" | 3 ≤ X, Y의 길이(자릿수) ≤ 3,000,000, 0으로 시작하지 않음

[ 문제 ]

=> X, Y의 짝꿍을 return
(짝꿍은 두 정수 X, Y의 임의의 자리에서 공통으로 나타나는 정수 k(0 ≤ k ≤ 9)들을 이용하여 만들 수 있는 가장 큰 정수)

[ 풀이 ]

Map에 첫번째 문자열에서의 각 문자별 개수를 저장
두번째 문자열과 map에 저장된 값을 비교하면서 같은 문자가 있다면 최대힙에 저장
최대힙에 넣은 값을 순차적으로 빼면 가장 큰 값이 나오게 됨

코드

> [성공] 1차 시도 : Map, PriorityQueue, 정수 계산 이용

생각한 풀이 그대로 구현

import java.util.*;

class Solution {
    public String solution(String X, String Y) {
        Map<Integer, Integer> map = new HashMap<>();
        
        int stoi = Integer.parseInt(X);
        while(stoi != 0){
            int res = stoi%10;
            map.put(res, map.getOrDefault(res, 0)+1);
            stoi/=10;
        }
        
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        stoi = Integer.parseInt(Y);
        while(stoi != 0){
            int res = stoi%10;
            Integer val = map.get(res);
            if(val != null && 0 < val){
                pq.add(res);
                map.put(res, val-1);
            }
            stoi/=10;
        }
        long ans = 0;
        boolean flag = false;
        while(!pq.isEmpty()){
            flag = true;
            ans = ans*10 + pq.poll();
        }
        return flag?String.valueOf(ans):"-1";
    }
}

=> 두 정수 X,Y의 길이가 3,000,000이하이므로, 정수형으로는 계산할 수 없는 길이였음..

> [성공] 2차 시도 : Map, PriorityQueue, 정수 계산 이용

생각한 풀이 그대로 구현

import java.util.*;

class Solution {
    public String solution(String X, String Y) {
        Map<Character, Integer> map = new HashMap<>();
        
        for(char c : X.toCharArray()){
            map.put(c, map.getOrDefault(c, 0)+1);
        }
        
        PriorityQueue<Character> pq = new PriorityQueue<>(Collections.reverseOrder());
        int zero_cnt = 0;
        for(char c : Y.toCharArray()){
            Integer cnt = map.get(c);
            if(cnt != null && 0 < cnt){
                map.put(c, cnt-1);
                if(c == '0'){
                    zero_cnt++;
                    continue;
                }
                pq.add(c);
            }
        }
        
        if(pq.size() == 0 && zero_cnt > 0)
            return "0";
        
        StringBuilder sb = new StringBuilder();
        boolean flag = false;
        while(!pq.isEmpty()){
            flag = true;
            sb.append(pq.poll());
        }
        
        while(0 < zero_cnt){
            sb.append("0");
            zero_cnt--;
        }
        
        return flag?sb.toString():"-1";
    }
}

=> 테케 11~15의 실행속도가 굉장히 느렸음

> [성공] 3차 시도 : int[] 이용

생각한 풀이 그대로 구현

import java.util.*;

class Solution {
    public String solution(String X, String Y) {
        int[] numX = new int[10];
        for(int i=0; i<X.length(); i++) {
            numX[X.charAt(i)-'0']++;
        }
        
        int[] numY = new int[10];
        for(int i=0; i<Y.length(); i++) {
            numY[Y.charAt(i)-'0']++;
        }
        
        StringBuilder answer = new StringBuilder();
        for(int i=9; i>=0; i--) {
            if(numY[i]>0 && numX[i]>0) {
                answer.append(i);
                numY[i]--;
                numX[i]--;
                i++;
            }
        }
        
        String ans = answer.toString();
        if("".equals(ans))
           return "-1";
        else if(ans.charAt(0)=='0')
           return "0";
        else
            return ans;
    }
}