프로그래머스] 숫자 짝꿍

문제 설명

두 정수 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

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

 

 

• 나의 틀린 풀이 (프로그래머스에 입력할때는 main을 일반으로 고쳐서 입력했음)

  처음 String으로만 풀었을때 시간초과가 나왔다. 

그래서 구글링해보니 StringBuilder가 추가,수정시에 성능이 좋다하여 StringBuilder를 사용했으나

 

또 시간초과.

 

(※ String은 불변의 속성을 가져서 값이 변하면(추가,수정등) 기존 값은 그대로 남아있고

     새로운 메모리 영역에 만들어진다. 그래서 힙메모리에 Garbage가 다수 생성되어 성능이 저하될수있다.

     반면 StringBuilder는 가변적이라 추가,수정을 하면 기존 메모리에있는것을 추가,수정한다.)

참고 티스토리 : https://ifuwanna.tistory.com/221

public class EX6_1127 {

	public static void main(String[] args) {
		StringBuilder answer = new StringBuilder();
		StringBuilder arr = new StringBuilder();
		StringBuilder Xb = new StringBuilder();
		StringBuilder Yb = new StringBuilder();
		
		String X = "000000000000000100000"; // 임의의 변수
		String Y = "0000000000000001111111111111100000"; // 임의의 변수
		String[] arrX = X.split(""); // 오름차순 정렬을 하려고 배열에 담아줌
		Arrays.sort(arrX); // 오름차순 정렬
		
		for(int i = 0; i < arrX.length; i++) {
			Xb.append(arrX[arrX.length-1-i]); // 내림차순으로 정렬하면서 StringBuilder에 담음
		}
		Yb.append(Y); // Y값은 정렬하지 않고 바로 담아줌.
		
		
		// match메소드도 for문이라 이중for문이됨 ==> 여기가 시간초과로 문제가 된 것같음.
			for(int i = 0; i < Xb.length(); i++) {// X값전부를 비교하기 위한 for문
				match(i, Xb, Yb, arr); // X 특정 값을 Y전부값과 비교하는 메소드 
			} 
			
			
			if(arr.length()==0) {// arr길이가 0이면 같은게 없으로 -1
				answer.append("-1");
			}else if(arr.charAt(0)==48 && arr.charAt(arr.length()-1)==48) {
				answer.append("0"); // 내림차순 정렬해둔뒤라 제일 처음수와 제일 끝수가 0이면 같은게 0밖에 없음. 
				
			} else { // arr배열에 넣어둔 같은 수들을 StringBuilder변수에 넣어줌 
				for(int i = 0; i < arr.length(); i++) {
					answer.append(arr.charAt(i));
				}
				
			}
			String answer1 = answer.toString(); // String으로 형변환
			System.out.println(answer1);// 답을 출력
		
	}
	public static StringBuilder match(int i,StringBuilder Xb,StringBuilder Yb, StringBuilder arr ) {
		for(int k = 0; k < Yb.length(); k++) {// X특정값을 Y값전부와 비교하여 
			if(Xb.charAt(i)==Yb.charAt(k)) {  // 두 값이 같다면
				arr.append(Yb.charAt(k));     // 임의의 배열에 담아둠 
				Yb.deleteCharAt(k);           // 그리고 반복 비교를 피하기 위해 비교한값은 삭제
				break; // 조건 만족시 break로 for문 빠져나옴.
			}
		}
		return arr;
	}// match괄호
	
}//main 괄호

 

 

• 나의 맞는 풀이

 

 프로그래머스 질문하기에 나와 같은 고민인 사람들이 있었고 

이중 for문은 되도록 사용하지말고 X,Y를 직접 비교하기 보다는 0~9숫자와 비교해보라는 힌트를 얻음.

그 힌트를 바탕으로 switch case로 0~9까지 비교하는 메소드를 만들고 

X와 Y가 0~9숫자가 몇개씩 포함되어 있는지 배열은 만듦. 

그리고 그 배열을 비교해서 공통으로 포함된 숫자를 추출해 내고 answer변수에 누적해줌. 

 

 

 

 

public String solution(String X, String Y) {
        StringBuilder answer = new StringBuilder();
        
		StringBuilder bX = new StringBuilder();
		StringBuilder bY = new StringBuilder();
		
		bX.append(X); // String X값을 StringBuilder에 넣기 
		bY.append(Y); // String Y값을 StringBuilder에 넣기 
		int numX[] = {0,0,0,0,0,0,0,0,0,0};
		int numY[] = {0,0,0,0,0,0,0,0,0,0};
		int numXY[] = {0,0,0,0,0,0,0,0,0,0};
		
		int count = 0;
		
		numX = num(numX, bX); // 0~9까지 숫자가 몇개씩 포함되어있는지 체크해줌.
		numY = num(numY, bY); // 0~9까지 숫자가 몇개씩 포함되어있는지 체크해줌.
		
       for(int i = 0 ; i <10; i++) {
    	   if(numX[i] == 0 || numY[i] == 0) { 
    		  count++; // X,Y에 포함된 숫자가 없을때 count해줌.
    		  if(numX[9]>0 && numY[9]>0 && count==9) {
    			  answer.append("0"); // 총 10개중 9개째 같은 숫자가 없고 마지막 0을 둘다 포함할때 
				  break;
    		  }
    		  if(count==10) {     // X,Y 둘다 같은 수가 하나도 없을때 
    			  answer.append("-1");
    			  break;
    		  }
    	  }
    	  
    	  if(numX[i] >0 && numY[i] > 0) { // X,Y 둘다 0~9중 숫자를 갖고있을때
    		  numXY[i] = Math.min(numX[i],numY[i]); // 같은수 최소 갯수를 배열에 넣어줌
        	  while(numXY[i]>0) { // 그 갯수가 0개 이상일때
        		  answer.append(9-i); // answer에 역순으로 넣어줌
        		  numXY[i]--; // 한번씩 넣어줄때 마다 갯수를 한개씩 빼줌.
        	  }
    	  }
    	  
       }
		
	return answer.toString(); // String으로 return하기 위해 toString사용
	}// solution 괄호
	
	// 0~9까지 숫자가 몇개있는지 체크하는 메소드
	public int[] num (int[] numArr,StringBuilder bCommon) {
		
		for(int i = 0; i <bCommon.length(); i++) { 
        	switch (bCommon.charAt(i)) { // 0~9숫자가 몇개씩 포함되어있는지 배열에 넣기.
    		case '0': // 출력시 큰수를 리턴해야해서 미리 내림차순으로 해둠.
    			numArr[9]++;
    			break;
    		case '1':
    			numArr[8]++;
    			break;
    		case '2':
    			numArr[7]++;
    			break;
    		case '3':
    			numArr[6]++;
    			break;
    		case '4':
    			numArr[5]++;
    			break;
    		case '5':
    			numArr[4]++;
    			break;
    		case '6':
    			numArr[3]++;
    			break;
    		case '7':
    			numArr[2]++;
    			break;
    		case '8':
    			numArr[1]++;
    			break;
    		case '9':
    			numArr[0]++;
    			break;
    		
    		}
        }
		return numArr;
	} // num메소드 괄호

 

3일 넘게 고민하다 겨우 풀었다.

아직 부족함이 많아 공부를 많이 해야겠다는 생각이 들었다. 

그래도 해결하고나니 정말 뿌듯했다.