[프로그래머스] 로또의 최고 순위와 최저 순위(java)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/77484

프로그래머스

---

나의 풀이

class Solution {
    public int[] solution(int[] lottos, int[] win_nums) {
        int[] answer = new int[2];

        int zeroCount = 0;
        int sameCount = 0;
        for (int i = 0; i < lottos.length; i++) {
            if (lottos[i] == 0) {
                zeroCount++;
            } else {
                for (int j = 0; j < win_nums.length; j++) {
                    if (lottos[i] == win_nums[j]) {
                        sameCount++;
                        break;
                    }
                }
            }
        }

        if (zeroCount == 0 && sameCount == 0) {
            sameCount = 1;
        }
        answer[0] = 7 - (sameCount + zeroCount);

        if (zeroCount == 6 && sameCount == 0) {
            sameCount = 1;
        }
        answer[1] = 7 - sameCount;
        return answer;
    }
}

0의 개수를 세고, 0이 아니라면 로또 번호가 일치한지 확인하는 중첩 반복문을 사용하였다. 시간 복잡도가 O(n²)이고 증가 차수가 이차이다. 

 

하지만, 최악의 경우에 이차가 되고 0이 많을수록, 일치하는 번호가 win_nums 배열 앞쪽 인덱스에 있을수록 선형에 가까운 풀이가 될 수 있다.