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의 길이가 짧고 많이 겹칠수록 앞에서 쓰였던 방법들이 더 효율적이라서 그런 것 같다! 다른 분들의 풀이도 좋았지만 시간을 계산해봤을 때 확실히 내가 빠른 편이어서 뭔가 기분이 좋았다!
클린코드로 또 한 걸음!
'STUDY > JAVA' 카테고리의 다른 글
[TIL] 프로그래머스 - 완주하지 못한 선수 (0) | 2023.05.26 |
---|---|
[TIL] 프로그래머스 - 체육복 (0) | 2023.05.23 |
[TIL] 약수의 개수 구하기 빠른 방법 (0) | 2023.05.14 |
230411 공부기록 (0) | 2023.04.12 |
230410 공부기록 (0) | 2023.04.11 |