[프로그래머스] 숫자 짝꿍(Lv.1) - Java/자바

문제

링크

코딩테스트 연습 > 연습문제 > 숫자 짝꿍 (Lv. 1)
정답률 55% (2023.05.18 기준)

 

문제 설명

두 정수 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의 짝꿍은 상당히 큰 정수일 수 있으므로, 문자열로 반환합니다.

 

입출력 예

X	Y	result
"100"	"2345"	"-1"
"100"	"203045"	"0"
"100"	"123450"	"10"
"12321"	"42531"	"321"
"5525"	"1255"	"552"

 

입출력 예 설명

입출력 예 #1

X, Y의 짝꿍은 존재하지 않습니다. 따라서 "-1"을 return합니다.

 

입출력 예 #2
X, Y의 공통된 숫자는 0으로만 구성되어 있기 때문에, 두 수의 짝꿍은 정수 0입니다. 따라서 "0"을 return합니다.

 

입출력 예 #3
X, Y의 짝꿍은 10이므로, "10"을 return합니다.

 

입출력 예 #4
X, Y의 짝꿍은 321입니다. 따라서 "321"을 return합니다.

 

입출력 예 #5
지문에 설명된 예시와 같습니다.

 

 

풀이

문자열 X, Y의 길이가 최대 300만이므로 단순히 2중 for문을 돌리거나, list에서 index를 찾는 방법으로는 시간초과가 발생하는 문제이다.

나도 처음엔 이렇게 작성했다가, 5개 테스트케이스에서 시간초과를 맛보고 다른 방식으로 문제를 다시 풀었다.

 

**실패 코드**

import java.util.*;
class Solution {
    public String solution(String X, String Y) {
        String answer = "";
    
        ArrayList<Integer> list1 = new ArrayList<>();
        ArrayList<Integer> list2 = new ArrayList<>();
        
        for(int i=0;i<X.length();i++) list1.add(Integer.parseInt(X.charAt(i)+""));
        for(int i=0;i<Y.length();i++) list2.add(Integer.parseInt(Y.charAt(i)+""));
            
        ArrayList<Integer> res = new ArrayList<>();
        for(int i=0;i<list1.size();i++){
            if(list2.contains(list1.get(i))){
                res.add(list1.get(i));
                list2.set(list2.indexOf(list1.get(i)), -1);
                list1.set(i, -1);
            }
        }
        
        Collections.sort(res, Collections.reverseOrder());
        for(int n : res) answer += n + "";
        
        return answer.startsWith("0") ? "0" : ("".equals(answer) ? "-1" : answer);
    }
}

 

answer String에 + 연산을 하는 대신 StringBuilder에 append하는 방식으로 하면 시간이 단축된다길래 시도해봤지만, list의 contains나 indexOf 함수 등이 내부적으로 소요 시간이 길어서 계속 시간초과로 100점이 뜨지 않았다.

단순히 두 문자를 비교할 방법이 없을까 생각하던 중 투 포인터 알고리즘이 생각났고, 문자열을 정수 배열로 바꿔서 각각 배열을 오름차순으로 정렬한 후, pos1, pos2 인덱스를 선언하여 두 배열의 원소를 비교하는 방식으로 문제를 해결했다.

 

 

코드

import java.util.*;
class Solution {
    public String solution(String X, String Y) {
        int[] arr1 = new int[X.length()];
        int[] arr2 = new int[Y.length()];
        for(int i=0;i<X.length();i++) arr1[i] = Integer.parseInt(X.charAt(i)+"");
        for(int i=0;i<Y.length();i++) arr2[i] = Integer.parseInt(Y.charAt(i)+"");
        Arrays.sort(arr1);
        Arrays.sort(arr2);
        
        int pos1 = 0;
        int pos2 = 0;

        ArrayList<Integer> res = new ArrayList<>();
        
        while(pos1 < arr1.length && pos2 < arr2.length) {
            int a = arr1[pos1];
            int b = arr2[pos2];
            
            if(a == b) {
                res.add(a);
                arr1[pos1] = -1;
                arr2[pos2] = -1;
                
                pos1++;
                pos2++;
            } else if(a < b) {
                pos1++;
            } else if(a > b) {
                pos2++;
            }
        }
        
        if(res.isEmpty()) return "-1";
        Collections.sort(res, Collections.reverseOrder());
        if(res.get(0) == 0) return "0";
        
        StringBuilder sb = new StringBuilder();
        for(int n : res) sb.append(n + "");
        
        return sb.toString();
    }
}

 

 

해결 과정

1. String으로 된 숫자 X, Y를 자릿수 별로 잘라서 int 배열 arr1, arr2에 각각 저장한다.
2. 투포인터 방식으로 배열 값을 비교하기 위해 arr1, arr2를 오름차순 정렬한다.
3. 각 배열의 0번 인덱스부터 마지막 인덱스까지 순회하며 각 인덱스 자리의 숫자값을 비교한다.
   1. 두 배열의 인덱스에 해당하는 값이 같다면 res 리스트에 값을 추가한 후, 비교 대상에서 제외되도록 두 배열의 값을 -1로 바꾼다.
   2. arr2의 값이 arr1의 값보다 크다면, 배열1의 pos1에 1을 더한다.
   3. arr1의 값이 arr2의 값보다 크다면, 배열2의 pos2에 1을 더한다.
4. 구해진 res 리스트가 비어 있다면 짝꿍이 존재하지 않으므로 "-1"을 리턴한다.
5. res 의 조합으로 가장 큰 숫자를 만들기 위해 리스트를 역순 정렬한다.
6. 정렬 결과 맨 앞 원소, 즉 res에서 가장 큰 수가 0이라면 "0", "00", "000" 등 결과가 0임을 나타내므로 "0"을 리턴한다.
7. 이 외의 경우 res의 원소를 순서대로 이어붙여 문자열 형태로 만들어 리턴한다.

 

 

실행 결과