[알고리즘] 프로그래머스 - 숫자짝꿍 Lv1 Java

https://school.programmers.co.kr/learn/courses/30/lessons/131128

프로그래머스

 

1. 실패 (시간초과) 11 ~ 15 시간초과 실패 코드

package Programmers;

import java.util.*;

public class 숫자짝꿍 {
    public static void main(String[] args){
        숫자짝꿍 T = new 숫자짝꿍();
        String X = "100";
        String Y = "203045";
        T.solution(X, Y);
    }
    public String solution(String X, String Y) {
        String answer = "";
        Map<Integer, Integer> mapX = new HashMap<>();
        Map<Integer, Integer> mapY = new TreeMap<>(Collections.reverseOrder());
        for (char s : X.toCharArray()) {
            mapX.put(Integer.parseInt(String.valueOf(s)), mapX.getOrDefault(Integer.parseInt(String.valueOf(s)),0)+1);
        }
        for (char s : Y.toCharArray()) {
            mapY.put(Integer.parseInt(String.valueOf(s)), mapY.getOrDefault(Integer.parseInt(String.valueOf(s)),0)+1);
        }

        for (int keyY: mapY.keySet()) {
            //keyY값이 mapX 에 없으면 건너뛴다.
            if(!mapX.containsKey(keyY)) continue;
            //mapY 의 value
            int yValCnt = mapY.get(keyY);
            //mapX 의 value
            int xValCnt = mapX.get(keyY);
            //반복 몇번할지 최소수를 구함
            int loopCnt = Math.min(xValCnt, yValCnt);
            while (loopCnt != 0){
                answer += keyY;
                loopCnt--;
            }
        }
        if(answer.length() == 0){
            answer = "-1";
        } else if (answer.charAt(0) == '0') {
            answer = "0";
        }
        return answer;
    }
}

 

 

2. 수정 코드 (통과)

package Programmers;

import java.util.*;
import java.util.stream.Collectors;

public class 숫자짝꿍 {
    public static void main(String[] args){
        숫자짝꿍 T = new 숫자짝꿍();
        String X = "12321";
        String Y = "42531";
        T.solution(X, Y);
    }
    public String solution(String X, String Y) {
        String answer = "";
        Map<String, Integer> mapX = new HashMap<>();
        Map<String, Integer> mapY = new HashMap<>();
        List<String> arrS = new ArrayList<>();

        for (String s : X.split("")) {
            mapX.put(s, mapX.getOrDefault(s,0)+1);
        }
        for (String s : Y.split("")) {
            mapY.put(s, mapY.getOrDefault(s,0)+1);;
        }

        for (String keyY: mapY.keySet()) {
            //keyY값이 mapX 에 없으면 건너뛴다.
            if(!mapX.containsKey(keyY)) continue;
            //mapY 의 value
            int yValCnt = mapY.get(keyY);
            //mapX 의 value
            int xValCnt = mapX.get(keyY);

            //반복 몇번할지 최소수를 구함
            int loopCnt = Math.min(xValCnt, yValCnt);
            while (loopCnt != 0){
                arrS.add(keyY);
                loopCnt--;
            }
        }
        answer = arrS.stream()
                .sorted(Collections.reverseOrder())
                .collect(Collectors.joining());
        if(answer.length() == 0){
            answer = "-1";
        } else if (answer.charAt(0) == '0') {
            answer = "0";
        }
        return answer;
    }
}

3. 풀이방법 

  - X, Y 각각 Map을 만들어준다. Value에는 몇개나 있는지 카운팅 해준다. 

  - MapY 의 키를 돌면서 Key값이 mapX 에 있는지 확인하고 없으면 건너뛴다.

  - 둘다 같은게 있으면 Value값중 최소값을 구해서 Loop문을 돌면서 KeyY값을 List에 추가한다.

  - 답이 구해진 List 를 역정렬 한후 answer에 대입해준다. 

  - answer 길이가 0 이면 일치하는게 없으므로 -1 처리

  - answer 첫번째 가 '0' 이면 0으로 넣어준다. (X [ 0, 0, 0, 0, 0, 0, 0 ] Y [ 0, 0, 0, 0, 0, 0, 0, ] 이런경우가 있기때문에) 

 

 

※ 시간을 줄이기 위해서 랩핑을 벗겨줌 String 으로만 계산함 

  Treemap으로 역정렬후에 while 돌때 바로 값을 때려박아줬는데도 시간초과남 

  map으로 해결할경우에 이거랑 똑같이 안하면 무조건 시간초과남 

 

answer = arrS.stream()
        .sorted(Collections.reverseOrder())
        .collect(Collectors.joining());

  알고리즘 풀때 Stream은 시간이 오래걸려서 잘 안쓰는데 이문제에서는 soted 와 collect 함수 안하고 두개 따로따로 연산하면 시간초과 남.