숫자 짝꿍

알파로그·2023년 3월 12일
0

✏️ 문제 설명

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

예를 들어, X = 3403이고 Y = 13203이라면,
X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 3, 0, 3으로 만들 수 있는 가장 큰 정수인 330입니다.
다른 예시로 X = 5525이고 Y = 1255이면
X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 2, 5, 5로 만들 수 있는 가장 큰 정수인 552입니다
(X에는 5가 3개, Y에는 5가 2개 나타나므로 남는 5 한 개는 짝 지을 수 없습니다.)
두 정수 X, Y가 주어졌을 때, X, Y의 짝꿍을 return하는 solution 함수를 완성해주세요.

✏️ 제한 사항

  • 3 ≤ X, Y의 길이(자릿수) ≤ 3,000,000입니다.
  • X, Y는 0으로 시작하지 않습니다.
  • X, Y의 짝꿍은 상당히 큰 정수일 수 있으므로, 문자열로 반환합니다.

✏️ 문제 풀이

📍 첫번째 풀이 - 실패

문제를 보자 마자 들은 생각은
parameter 의 최댓값이 3만이라 for 문을 사용한다면
최대 3만 x 3만 번을 반복해야되기 때문에
효율이 너무 안좋을것 같아서 배열을 비교하는 식으로 해야겠다고 생각했다.

index 자리가 픽스되있지 않은 array list 를 사용해
0 번 요소만 비교하는 방법이 떠올랐다.

public static void main(String[] args) {

        String X = "5525";
        String Y = "1255";
        String answer = "";
    //--------------------------------------------//
            // 주어진 변수를 char 배열로 변경
        char[] x1 = X.toCharArray();
        char [] y1 = Y.toCharArray();
            // 배열을 정렬해줌
        Arrays.sort(x1);
        Arrays.sort(y1);
            // 배열을 array list 에 넣어줌
        ArrayList <Character> x2 = new ArrayList<>();
        ArrayList <Character> y2 = new ArrayList<>();
        for (char i : x1){ x2.add(i); }
        for (char i : y1){ y2.add(i); }
            // array list 를 오름차순으로 바꿔줌
        Collections.reverse(x2);
        Collections.reverse(y2);
            // 0번 요소가 동일할경우 answer 에 값 넣고
            // 0번 요소 삭제
        while (x2.size() >0 && y2.size() > 0){
            if (x2.get(0)==y2.get(0)){
                answer += x2.get(0);
                x2.remove(0);
                y2.remove(0);
                    // 0번 요소가 다를 경우 큰쪽을 삭제
            }else if(x2.get(0) > y2.get(0)){
                x2.remove(0);
            }else {
                y2.remove(0);
            }
        }
            // answer 값이 없거나 0 일경우 값 변경
        if (answer == ""){
            answer = "-1";
        } else if (answer.charAt(0)=='0') {
            answer = "0";
        }

        System.out.println(answer);

처음 생각했던 대로 계산하는데 걸리는 시간이 문제였다...
나름 고려해서 최대한 효율적으로 만든다고 했는데 아직 많이 비효율 적인가보다 ㅜㅜ

📍 두번째 풀이 - 실패

이전 코드를 다시 리뷰해보니
변수 -> 배열 -> array list
배열이 쓰잘때기 없이 껴있었다.

배열 없이 바로 array list 에서 값을 추출하게 코드를 수정했다.

//--------------------------------------------//
            // 주어진 변수를 바로 array list 변경
        ArrayList <Character> x = new ArrayList<>();
        ArrayList <Character> y = new ArrayList<>();

        for(int i=0 ; i<X.length() || i<Y.length() ; i++){
            if(i < X.length()) x.add(X.charAt(i));
            if(i < Y.length()) y.add(Y.charAt(i));
        }
            // 내림 차순으로 
        Collections.sort(x,Collections.reverseOrder());
        Collections.sort(y,Collections.reverseOrder());

        // 0번 요소가 동일할경우 answer 에 값 넣고
        // 0번 요소 삭제
        while (x.size() >0 && y.size() > 0){
            if (x.get(0)==y.get(0)){
                answer += x.get(0);
                x.remove(0);
                y.remove(0);
                // 0번 요소가 다를 경우 큰쪽을 삭제
            }else if(x.get(0) > y.get(0)){
                x.remove(0);
            }else {
                y.remove(0);
            }
        }
        // answer 값이 없거나 0 일경우 값 변경
        if (answer == ""){
            answer = "-1";
        } else if (answer.charAt(0)=='0') {
            answer = "0";
        }
        System.out.println(answer);

뭔가 더 빨라진것같은 느낌이 있긴한데 똑같이 시간 초과가 난다 ㅜㅜ
아무래도 코드에 근본적인 문제가 있는것같다..

📍 세번째 풀이 - 실패

더 근본적인 해결책을 찾기위해 고민하다 도저히 아이디어가 떠오르지 않아서
다른사람들이 질문한걸 슬쩍봤다.

해결한 사람들의 힌트를 보니 배열 정렬을 통한 풀이는 통과하기 어렵다고 한다.
사람들의 흰트를 참고해 이번엔 Parameter 의 숫자가 0~9 중 한가지라는 점을 이용해서 풀어봤다.

먼저 배열에 0~9 까지 들어갈 수 있는 index 를 생성해주고
Parameter 값의 숫자에 해당하는 배열의 index 에 1씩 추가한후 두 배열의 값을 비교하는식으로 접근했다.

public static void main(String[] args) {

        String X = "5525";
        String Y = "1255";
        String answer = "";
    //--------------------------------------------//
            // parameter 값의 하나 하나가 0~9 까지의 수 라는걸 이용해
            // 0~9 에 해당하는 10개의 index 배열 생성
        int[] x1 = new int[10];
        int[] y1 = new int[10];
            // parameter 값을 쪼개 해당하는 숫자의 index에 1씩 추가해줌
        for (String i : X.split("")) x1[Integer.parseInt(i)] ++;
        for (String i : Y.split("")) y1[Integer.parseInt(i)] ++;
            // 두 배열을 마지막칸 (큰 수) 부터 비교해 더 적은 값을 anser 에 추가해줌
            // 겹치는 만큼 추가해야되기 때문에 for 문으로 겹치는 만큼 반복
        for (int i =9 ; i>=0 ; i--){
            if (x1[i] != 0 && y1[i] != 0){
                if (x1[i] <= y1[i]) for (int j=0; j<x1[i]; j++) answer += i;
                if (x1[i] > y1[i]) for (int j=0; j<y1[i]; j++) answer += i;
            }
        }
        if (answer == ""){
            answer = "-1";
        } else if (answer.charAt(0)=='0') {
            answer = "0";
        }

        System.out.println(answer);

코드가 눈부시게 줄어들었지만 여전히 시간초과로 실패..

📍 네번째 풀이 - 실패

이번엔 map 을 사용해서 풀어봤다..
결과는 똑같았다..
도대체 어느 부분이 잘못된걸까??ㅜㅜ

        HashMap <String,Integer> x1 = new HashMap<>();
        HashMap <String,Integer> y1 = new HashMap<>();
        StringBuilder build = new StringBuilder();

        for (String key : X.split(""))
            x1.put(key,x1.getOrDefault(key,0)+1);

        for (String key : Y.split(""))
            y1.put(key,y1.getOrDefault(key,0)+1);

        for (String key : x1.keySet()){
            if (!y1.containsKey(key)) continue;
            for (int i = 0; i < Math.min(y1.get(key), x1.get(key)); i++) {
                build.insert(0, key);
            }
        }
        answer = build.toString();answer = build.toString();

        if (answer.equals("")) answer = "-1";
        if (answer.charAt(0) == '0') answer = "0";

        System.out.println(answer);

지금 내 실력으로는 이게 최선인것같다..
문제를 해결한 사람들의 코드 2가지를 찾아봣다.

솔직히 내 코드와 작동 원리가 어느 부분에서 다른지 잘 모르겠다.
나중에 실력을 더 쌓은 후에 리뷰해봐야겟다..

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


class Solution {
    public String solution(String X, String Y) {
        Map<String, Integer> xMap = new HashMap<>();
        Map<String, Integer> yMap = new HashMap<>();
        
        List<String> list = new ArrayList<>();
        
        for(String key: X.split("")) {
            xMap.put(key, xMap.getOrDefault(key, 0)+1);
        }
        
        for(String key: Y.split("")) {
            yMap.put(key, yMap.getOrDefault(key, 0)+1);
        }
        
        for(String key: xMap.keySet()) {
            if(!yMap.containsKey(key)) continue;
            
            int length = Math.min(xMap.get(key), yMap.get(key));
            for(int i = 0; i < length; i++) {
                list.add(key);
            }
        }
        
        String result = list.stream()
            .sorted(Collections.reverseOrder())
            .collect(Collectors.joining());
        
        if(result.isEmpty()) return "-1";
        if(result.replaceAll("0", "").isEmpty()) return "0";
        return result;
    }
}
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();
        }
    }
}

✏️ 사용된 method

📍 String 을 char[] 로 바꾸기

String x = "12345";
char [] y = x.toCharArray();

📍 배열을 array list 로 바꾸기

ArrayList <Character> x = new ArrayList<>();
for (char i : x1) { x.add(i); }

📍 array list 정렬하기

 Collections.sort(x);   // 오름차순 정렬 
 Collections.sort(x,Collections.reverseOrder());  // 내림차순 정렬

📍 String 쪼개서 배열로 만들기

String x = "010-1234-5678;
String [] y = x.split("-");
//   -> [0] : 010
//   -> [1] : 1234
//   -> [2] : 5678

String [] z = x.split("-",2); //-를 기준으로 index 두개만 만들라는 뜻
//   -> [0] : 010
//   -> [1] : 1234-5678

String x = "Hello World";
String [] y = x.split(" ");
// -> [0] : Hello
// -> [1] : World

🔗 Map 기본적인 사용 방법
🔗 코드 출처
🔗 문제 원본

profile
잘못된 내용 PR 환영

0개의 댓글