프로그래머스 - 숫자 짝꿍 / JAVA (자바) 코딩 알고리즘 연습

• 숫자 짝꿍

문제 설명

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

---

입출력 예XYresult

"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

• 지문에 설명된 예시와 같습니다.

반응형

단순하게 각 자리수 별로 ArrayList에 담아서 비교한 후에,

StringBuilder로 출력하면 될 것이라고 생각했지만 시간 초과...!

 

이거는 실패한 코드ㅜㅜ

일일이 비교하다가 시간 초과로 대실패...

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

class Solution {
    public String solution(String X, String Y) {
        String answer = "";
		
		ArrayList<Character> arr1 = new ArrayList<>(); //X를 담을 ArrayList
		ArrayList<Character> arr2 = new ArrayList<>(); //Y를 담을 ArrayList
		ArrayList<Character> arr3 = new ArrayList<>(); //공통된 숫자
		
		for (int i = 0; i < X.length(); i++) {
			arr1.add(X.charAt(i));
		}
		
		for (int i = 0; i < Y.length(); i++) {
			arr2.add(Y.charAt(i));
		}
		
		for (int i = 0; i < X.length(); i++) {
			if(arr2.contains(arr1.get(i))) {
				arr3.add(arr1.get(i));
				arr2.remove(arr1.get(i));
			}
		}
		
		String[] arr = {};
		if(arr3.size() != 0) {
			arr = new String[arr3.size()];
		}else if(arr3.size() == 0) {
			return "-1";
		}
		
		for (int i = 0; i < arr3.size(); i++) {
			arr[i] = String.valueOf(arr3.get(i));
		}
		
		Arrays.sort(arr, Collections.reverseOrder());
		
		StringBuilder sb = new StringBuilder();
		for (String str : arr) {
			sb.append(str);
		}
		
		answer = sb.toString();
		
		if(Long.parseLong(answer.substring(0,1)) == 0) {
			answer = "0";
		}
        
        return answer;
    }
}

아래 코드는 구글링으로 찾은 코드인데

정말 깔끔하다...

X와 Y를 split 메소드를 사용해서 각 자리수 별로 나누어서 카운트를 하고,

숫자 9부터 시작해서 while 문으로 돌려주고 x,y 카운트를 한 배열이 둘다 0 이상인 경우에만

StringBuilder를 통해서 추가해준다!

 

이런 방법은 생각도 못했는데 깔끔 그 자체,,,, 

 

이제 프로그래머스 랭킹이 11,xxx위 대로 진입했으니 10,000위를 목표로 가보자~~!

class Solution {
    public String solution(String X, String Y) {
        int[] a = new int[10]; // X 숫자 카운트할 배열
		int[] b = new int[10]; // Y 숫자 카운트할 배열

		for (String str : X.split("")) {
			a[Integer.parseInt(str)]++;
		}

		for (String str : Y.split("")) {
			b[Integer.parseInt(str)]++;
		}

		StringBuilder sb = new StringBuilder();

		for (int i = 9; i >= 0; i--) {
			while (a[i] > 0 && b[i] > 0) {
				sb.append(i);
				a[i]--;
				b[i]--;
			}
		}

		String answer = "";

		if (answer.equals(sb.toString())) {
			answer = "-1";
		} else if (sb.toString().substring(0,1).equals("0")) {
			answer = "0";
		} else {
			answer = sb.toString();
		}
        
        return answer;
    }
}