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

 

 

문제분석:

 

이 문제는  제한사항만 아니면 쉽게 풀수있다.

 

예를들자면,    for( X배열) , for(Y배열) 2중반복문으로 짝꿍 숫자를 찾는것이 가능하다.

 

하지만  길이가  300만이기때문에    300만*300만  연산은 말이안되기때문에..   효율적인 코드를 짜야한다.

 

 

1. 목표!   데이터 배열은 1번만 돌리자

 

즉,  최소 O(n) + O(n2) ,   300만+300만  = 600만 연산만 사용하자를 목표로두었다.

 

 

Map을 사용하였다.  첫번째  Map은  X의 배열을 입력받아  Y배열과의 짝궁여부를 확인하는 용도.

두번째 Map인 couple맵은  짝궁여부가 가능하다면,  Couple 정보를 입력받는다.

 

 

남은건 Couple 맵에 저장된 정보를 바탕으로 문자열을 작성한다.

 

예외처리로  커플이없으면 -1 ,  0으로 시작하는 문자는 0으로 반환해준다.

 

문제풀이

import java.util.*;
class Solution {
    public String solution(String X, String Y) {
        String answer = "";
        Map<Character,Integer> map = new TreeMap<>(Collections.reverseOrder());
        Map<Character,Integer> couple = new TreeMap<>(Collections.reverseOrder());
 
        for(int i=0;i<X.length();i++){
            map.put(X.charAt(i),map.getOrDefault(X.charAt(i),0)+1);
        }
        for(int i=0;i<Y.length();i++){
            int amount =map.getOrDefault(Y.charAt(i),0);
            if(amount!=0){
                map.put(Y.charAt(i),map.get(Y.charAt(i))-1);
                couple.put(Y.charAt(i),couple.getOrDefault(Y.charAt(i),0)+1);
            }        
        }
 
        StringBuilder sb = new StringBuilder();
 
 
        for(char key: couple.keySet()){
            for(int i=0;i<couple.get(key);i++){
                sb.append(key);
            }
        }
 
        answer=sb.toString();
 
        if(answer.equals("")) return "-1";
        if(answer.startsWith("0")) return "0";
 
 
        return answer;
    }
}

 

 

 

다른 사람의 더 좋은 풀이:

class Solution {
    public String solution(String X, String Y) {
        StringBuilder answer = new StringBuilder();
        int[] x = {0,0,0,0,0,0,0,0,0,0};
        int[] y = {0,0,0,0,0,0,0,0,0,0};
        for(int i=0; i<X.length();i++){
           x[X.charAt(i)-48] += 1;
        }
        for(int i=0; i<Y.length();i++){
           y[Y.charAt(i)-48] += 1;
        }
 
        for(int i=9; i >= 0; i--){
            for(int j=0; j<Math.min(x[i],y[i]); j++){
                answer.append(i);
            }
        }
        if("".equals(answer.toString())){
           return "-1";
        }else if(answer.toString().charAt(0)==48){
           return "0";
        }else {
            return answer.toString();
        }
    }
}