[2021 Dev-Matching] 로또의 최고 순위와 최저 순위 (JAVA)

문제

---

풀이

문제에서 주어지는 배열의 길이가 6밖에 되지 않아서 O(N^2)로 풀어도 시간초과가 나지 않는 문제다. 하지만 다른 방법으로 풀어보려고 노력했고 인덱스 두 개를 사용해서 O(N)으로 풀었다.

최솟값은 일치하는 값의 개수고, 최댓값은 일치하는 값의 개수 + 0의 개수다.

1. 우선 주어진 배열들을 오름차순으로 정렬한다.
2. lottos를 탐색하며 zeroCount에 0의 개수를 저장한다.
3. lottos와 win_nums를 각각의 인덱스를 두고 탐색하며 일치하는 값이 있으면 lowerBound를 증가시킨다.
   • 이 때 lottosIndex는 0이 아닌 수부터 시작하기 위해 zeroCount를 초기값으로 준다.
4. count들을 순위로 변환해서 리턴한다.

코드

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;
    }
}