[TIL] 프로그래머스 - 숫자 짝꿍

5일이 걸려서 드디어 문제를 푸는 데 성공했다. 이번 주는 시간이 없어 매일 30분 정도밖에 투자하지 못한것 같다. 하지만 풀어낸 과정이 괜찮았던 거 같아서 기록해본다.

---

문제 설명(from. Programmers '숫자 짝꿍')

두 정수 X, Y가 있을 때 겹치는 숫자를 찾아 가장 큰 수를 만드는 것.
ex. X = 3403, Y = 13203 : 공통으로 나타나는 3, 0, 3으로 만들 수 있는 가장 큰 정수인 330
ex. X = 5525, Y = 1255 : 공통으로 나타나는 2, 5, 5로 만들 수 있는 가장 큰 정수인 552
겹치는 수가 없으면 "-1" return.

X와 Y는 String으로 주어지며, 자릿수는 3,000,000이하이다.
X와 Y는 0으로 시작하지 않는다.
String으로 return할 것.

보통 프로그래머스 문제를 풀 때 저런식으로 숫자가 크게 나오면 잘못 풀면 시간 초과로 통과하지 못하기 때문에 효율성을 잘 생각해야 한다. 하지만 대략적인 시간 느낌을 익히려고 처음에는 아무렇게나 풀었다.

일단 풀고 계속 런타임 에러가 나보면 여길 뜯어볼까? 여길 바꿀까? 문제를 다시 생각해볼까? 방법을 바꿔볼까? 하는 식으로 생각이 들기 때문이다.

---

첫번째 방법

X와 Y를 toCharArray 메서드를 이용해 char배열을 두 개 만든 다음, 역순 정렬하고, 겹치는 것을 for문 안에 for문으로 찾아서 answer라는 String에 붙여서 리턴. 

>> 6, 7, 8, 9, 10 실패 / 11, 12, 13, 14, 15 시간 초과

이미 for문 안에 for문을 넣은 순간 잘못하면 3백만*3백만이 돌아간다. 어떻게 하면 시간을 줄일 수 있을까?

---

두 번째 방법

String이라서 늦은 것일까? StringBuilder로 바꿔 append를 해보자.

>> 6, 7, 8, 9, 10 실패 / 11, 12, 13, 14, 15 시간 초과

일단 6, 7, 8, 9, 10이 시간초과가 아니고 그냥 실패라는 점에서 방법이 잘못 되었나 보다.

---

세 번째 방법

방법도 잘못 된건데, 일단 느리다. 혹시 정렬을 하고 찾아서 그런 것일까? 겹치는 것을 먼저 찾고 정렬한다면? for문(for문)을 돌려서 먼저 겹치는 걸 찾고 StringBuilder의 deleteCharAt 메서드와 append 메서드를 이용해 겹치는 걸 하나씩 삭제해 가면서 찾으면 더 빨라질 수도 있다.

테스트 1은 0.30ms로 성공. 6, 7, 8, 9, 10번도 다 정답처리. 하지만 11, 12, 13, 14, 15가 그대로 시간 초과였다!

---

네 번째 방법

아무리 생각해도 for문 안에 for문 때문에 시간이 안 되는 것 같다. 두 개가 만약 겹치는 게 없고 두 정수의 길이가 3백만이면 3백만 * 3백만으로 돌아간다. 계속 생각을 해보다가 예전에 index를 이용하여 문제를 풀었던 것이 기억났다. 

길이가 10인 int 배열 두 개를 만든다.

int[] xnum = new int[10];
int[] ynum = new int[10];

for문을 X의 길이만큼 돌리는데, 각 자리의 숫자의 인덱스에 ++시켜준다. 이렇게 하면 X가 가지고 있는 숫자들의 개수를 알 수 있다. 마찬가지로 Y도 같이 해 준다.

for ( int i = 0 ; i < X.length() ; i++ ) {
	xnum[X.charAt( i ) - '0']++;
}

for ( int i = 0 ; i < Y.length() ; i++ ) {
	ynum[Y.charAt( i ) - '0']++;
}

X와 Y로 만든 int배열을 각각 비교한 뒤, 값이 더 작은 쪽으로 다시 배열 하나를 맞춘다.

for ( int i = 0 ; i <= 9 ; i++ ) {
	xnum[i] = Math.min( xnum[i], ynum[i] );
}

이렇게 하면 겹치는 숫자가 무엇이고, 몇 개인지 알 수 있게 된다. 최대치로 돌려도 3백만+3백만+10이다!

여기서 겹치는 숫자가 아예 없으면 "-1"을 리턴하고 그게 아닌데 1에서 9까지 겹치는 게 없으면 "0"을 리턴한다.(0이 여러번 나오는 경우가 있으므로)

int sum = 0;
int zerocount = 0;
for ( int i = 0 ; i <= 9 ; i++ ) {
	sum += xnum[i];
	if ( i >= 1 ) {
		zerocount += xnum[i];
	}
}

if ( sum == 0 ) {
	return "-1";
} else if ( zerocount == 0 ) {
	return "0";
}

이제 드디어 끝이다...!  StringBuilder를 하나 선언해 주고 배열에 있는 갯수만큼 index를 붙여주면 된다.

StringBuilder sb = new StringBuilder();
for ( int i = 9 ; i >= 0 ; i-- ) {
	String plus = "";
	if ( xnum[i] != 0 ) {
		plus += i;
		sb.append( plus.repeat( xnum[i] ) );
	}
}

return sb.toString();

우와!! 드디어 11, 12, 13, 14, 15 통과!!! 근데 test01의 결과는 9.90ms로 오히려 늘었다..? 아마 X와 Y의 길이가 짧고 많이 겹칠수록 앞에서 쓰였던 방법들이 더 효율적이라서 그런 것 같다! 다른 분들의 풀이도 좋았지만 시간을 계산해봤을 때 확실히 내가 빠른 편이어서 뭔가 기분이 좋았다!

---

클린코드로 또 한 걸음!