문제에서 주어지는 배열의 길이가 6밖에 되지 않아서 O(N^2)
로 풀어도 시간초과가 나지 않는 문제다. 하지만 다른 방법으로 풀어보려고 노력했고 인덱스 두 개를 사용해서 O(N)
으로 풀었다.
최솟값은 일치하는 값의 개수고, 최댓값은 일치하는 값의 개수 + 0의 개수다.
lottos
를 탐색하며 zeroCount
에 0의 개수를 저장한다.lottos
와 win_nums
를 각각의 인덱스를 두고 탐색하며 일치하는 값이 있으면 lowerBound
를 증가시킨다.lottosIndex
는 0이 아닌 수부터 시작하기 위해 zeroCount
를 초기값으로 준다.import java.util.Arrays;
class Solution {
private static final int UNKNOWN = 0;
private static final int SIZE = 6;
public int[] solution(int[] lottos, int[] win_nums) {
Arrays.sort(lottos);
Arrays.sort(win_nums);
int zeroCount = 0;
for (int lotto : lottos) {
if (lotto != UNKNOWN) break;
zeroCount++;
}
int lowerBound = 0;
int lottosIndex = zeroCount, winNumsIndex = 0;
while (lottosIndex < SIZE && winNumsIndex < SIZE) {
if (lottos[lottosIndex] == win_nums[winNumsIndex]) {
lowerBound++;
lottosIndex++;
winNumsIndex++;
} else if (lottos[lottosIndex] > win_nums[winNumsIndex]) {
winNumsIndex++;
} else {
lottosIndex++;
}
}
return parseAnswer(lowerBound, lowerBound + zeroCount);
}
private int[] parseAnswer(int lowerBound, int upperBound) {
int[] result = new int[2];
result[0] = Math.min(6, 7 - upperBound);
result[1] = Math.min(6, 7 - lowerBound);
return result;
}
}