[Java]숫자 짝꿍

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

프로그래머스

📚문제

두 정수 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 함수를 완성해주세요.

 

✏️ 내 풀이 

import java.util.ArrayList;
import java.util.List;
import java.util.stream.*;
import java.util.Collections;

class Solution {
    public String solution(String X, String Y) {
        String[] xlist = X.split("");
        String[] ylist = Y.split("");
        List<Integer> sameList = new ArrayList<>();

        boolean[] visited = new boolean[ylist.length];

        for (int i = 0; i < xlist.length; i++) {
            for (int j = 0; j < ylist.length; j++) {
                if (xlist[i].equals(ylist[j]) && !visited[j]) {
                    sameList.add(Integer.valueOf(xlist[i]));
                    visited[j] = true;
                    break;
                }
            }
        }

        if (sameList.isEmpty()) {
            return "-1";
        }

        Collections.sort(sameList, Collections.reverseOrder());
        String result = sameList.stream()
                .map(String::valueOf)
                .collect(Collectors.joining());

        if (result.replaceAll("0", "").isEmpty()) {
            return "0";
        }

        return result;
    }
}

 

입력받은 문장들을 split() 을 통해 리스트 형태로 저장시키고 리스트를 반복하여 x와 y 리스트가 동일하면 ArrayList 에 저장을 시켰다.그리고 중복 체크를 제거하기 위해 boolean 을 이용하여 인덱스 별로 체크를 해주었다. 

다음,리스트가 비어있다면 -1 을 반환한다.만약 리스트가 존재한다면 Collections 함수를 통해 역순으로 정렬하고 해당리스트를 Stream() 을활용하여 문자열을 합쳐준다.

만약 0을 다제외했는데 결과가 빈다면 0만 존재한다는 것이므로 0을 반환시킨다.

 

💢 그런데,일부 테스트에서 시간초과가 발생했다.

 

왜냐하면 제한사항에 3 ≤ X, Y의 길이(자릿수) ≤ 3,000,000 였기 때문에 리스트로 정렬하여 반복문을 실행하면 10만개 이상의 값이 반복된다. 지금은 코드만 실행되면 코드풀이를 마치지만 , 추후엔 성능과 가독성을 향상시키기위해 코드를 리팩토링을 해야할 것이다.

그래서 다른분이 푼 코드를 참조하여 다시 풀어보았다.

✏️ 좋은 풀이

class Solution {
    public String solution(String X, String Y) {
        int[] xCount = new int[10];
        int[] yCount = new int[10];

        for (char ch : X.toCharArray()) {
            xCount[ch - '0']++;
        }

        for (char ch : Y.toCharArray()) {
            yCount[ch - '0']++;
        }

        StringBuilder sb = new StringBuilder();

        for (int i = 9; i >= 0; i--) {
            int minCount = Math.min(xCount[i], yCount[i]);
            for (int j = 0; j < minCount; j++) {
                sb.append(i);
            }
        }

        if (sb.length() == 0) return "-1";          
        if (sb.charAt(0) == '0') return "0";       
        
        return sb.toString();
    }
}

 

X와 Y를 toCharArray() 메소드를 활용하여 char 로 분리시키고 해당 아스키 코드를 추출하여 해당 숫자의 인덱스의 숫자를 올려준다. StringBuilder 를 생성하고 동일한 인덱스 숫자의 숫자중 낮은 숫자를 선택 후 숫자만큼 Stringbuilder에 append 시킨다.

그리고 아무것도 추가되지않으면 -1,인덱스 0 이 0이라면 가장 높은 숫자가 0 이기때문에 0 으로 리턴된다.

 

🔢 ch - '0'의 의미

• 이 표현은 문자 '0'의 아스키코드 값을 기준점으로 삼아, 문자 숫자를 실제 정수로 변환하는 방식이다.

예를 들어, ch = '3'일 경우:

'3' - '0' = 51 - 48 = 3

이렇게 하면 문자 '3'을 정수 3으로 변환할 수 있게 된다. 이 값은 배열 인덱스로 사용하기에 적합하다.

 

✒️ 회고

- 아스키코드를 통으로 외우는 건 불가능하겠지만 어느정도 사용되는 대표적인 숫자나 문자들은 기억하는게 코딩테스트를 푸는데 도움이 될거 같다.

- 데이터가 너무 많을시엔 리스트를 무작정 반복하는게 아니라 다른 방법이 있는지 생각해보는 것이 좋겠다.