숫자 짝꿍 - Java [코딩테스트 연습]

 

 

❤️ Problem

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

 

• 입출력 예 & 설명

no	X	Y	result
1	"100"	"2345"	"-1"
2	"100"	"203045"	"0"
3	"100"	"123450"	"10"
4	"12321"	"42531"	"321"
5	"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. 지문에 설명된 예시와 같습니다.

---

 

💛 Solution

풀이

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
class Solution {
    public String solution(String X, String Y) {
        String[] partX = X.split("");
        String[] partY = Y.split("");
        Arrays.sort(partX);
        Arrays.sort(partY);

        ArrayList<String> arr = new ArrayList<>();
        int start = 0;
        for(int i=0; i<partX.length; i++) {
        	int tmp = Integer.parseInt(partX[i])+1;
            for(int j=start; j<partY.length; j++){
                if(partX[i].equals(partY[j])) {
                    arr.add(partX[i]);
                    start = j+1;
                    break;
                } else if(Integer.parseInt(partY[j]) >= tmp) {
                	break;
                }
            }
        }

        StringBuilder answer = new StringBuilder();
        if(arr.isEmpty()) {
            answer.append("-1");
        } else {
            if(arr.lastIndexOf("0") == arr.size()-1) {
               	answer.append(0);
            } else {
                Collections.sort(arr, Collections.reverseOrder());
                for(int i=0; i<arr.size(); i++) {
                    answer.append(arr.get(i));
                }
            }
        }

        return answer.toString();
    }
}

 

처리속도가 현재로서는 최선이다.

 

---

 

💜 Comment

와 이 문제는 통과가 딱 떴을 때 소리지를 뻔했던 문제이다. 계속해서 테스트 케이스 11, 12, 13, 14 ,15번이 시간초과가 났기 때문에 푸는 내내 골머리를 앓았다. 시간초과가 난 이유는 이중 for문을 사용했기 때문이다. 이중 for문을 사용하게 되면 시간복잡도가 N의 제곱이 되는 건 알고 있지만 내 머리로는 도저히 이중 for문을 사용하지 않는 방법을 도출하기 어려웠다. 그래서 끝끝내 썼고 통과한 문제...😂 효율을 위해서는 다른 방법을 찾아야할 것 같다.

먼저 String X, Y를 각각 .split("");를 사용해서 String[] partX, partY에 분할하였다. 그 다음 Arrays.sort();를 사용해서 정렬하였다. 정렬한 이유는 아래에서 이중for문은 사용할 때 최대한 시간복잡도를 낮추기 위함이었다. "0"부터 "9"까지 오름차순으로 정렬되므로, 동일한 String을 가졌을 때 비교 후 바로 break;로 내부 for문을 탈출하려 했기 때문에 이 방법을 사용했다.

그 다음, 동일한 요소(숫자 짝꿍)를 담을 ArrayList<String>를 준비했다. 처음 문제를 제출했을 때는 ArrayList<Integer>를 준비했는데, 굳이 형변환을 할 필요가 없다는 것을 깨달아서 String으로 선언했다. int Start=0;를 선언한 뒤, 이중 for문을 생성해서 partX[i]와 partY[j]를 비교하는 코드를 준비했다. int Start는 j의 한계점이다. 동일한 요소가 있는 경우 start = j+1;로 바뀌게 되는데, 그 이유는 partY[j]까지는 이미 partX[i]와 비교를 했기 때문에 그 다음 partX[i+1]과 비교할 필요가 없기 때문에 시작지점을 바꾸도록 구현했다.

이중 for문의 바깥 부분에서는 int tmp=Integer.parseInt(partX[i])+1;을 선언했다. partX[i]와 동일한지만을 비교하면 되므로 partX[i]보다 1 커지는 부분부터는 비교할 필요가 없기 때문에 안쪽 for문을 탈출하기 위해(break;) 이렇게 변수를 미리 준비했다. 그 다음, if-else if를 사용해서 만약 partX[i].equals(partY[j])인 경우에는 동일한 요소라는 의미이므로 ArrayList에 해당 요소를 삽입하고, 앞서 말한대로 start를 j+1로 바꾼 뒤 break;하였다. 하지만 Integer.parseInt(partY[j]) >= tmp인 경우에는 더 이상 비교할 필요가 없기 때문에 역시 break;를 실행하도록 하였다. 이 모든 것은 앞서 배열을 Arrays.sort();로 정렬했기 때문에 가능한 코드이다.

그 다음으로 정답을 담을 StringBuilder를 준비했다. StringBuilder를 사용한 이유는 문자열의 추가 또는 변경이 String보다 성능에 영향을 덜 주기 때문이다. 그 다음 if-else 를 사용해서 arr.isEmpty()라면 "-1"을, 그렇지 않다면 그 안에 if-else를 사용해서 arr.lastIndexOf("0") == arr.size()-1;이면 "0"을, 그렇지 않다면 ArrayList의 값 순서를 Collections.sort(arr, Collections.reversOrder());를 사용해서 내림차순으로 변경하여 하나씩 StringBuilder에 삽입하도록 하였다.

arr.lastIndexOf("0") == arr.size()-1;이라는 의미는 "0"의 마지막 인덱스가 배열의 크기보다 1 작을 때라는 뜻이다. 그 말은 곧, "0"이 배열의 끝에 들어있다면이라는 의미가 된다. 그 이유는 "0"만이 들어 있는 경우 있는 그대로를 반환할 수 없고 "0"으로 치환해기 때문에 이러한 코드를 작성하게 되었다.

그리고 Collections.sort(arr, Collections.reversOrder());을 사용한 이유는 공통된 숫자들 중에서 가장 큰 수를 반환해야했기 때문에 큰 수부터 배열하여 그걸 순차적으로 Stringbuilder에 넣기 위함이었다.

마지막으로 Stringbuilder를 .toString()을 사용해서 반환하면 끝!

 

 

 

6점!!!!! 7866위다😁😁😁