19. 프로그래머스 - 로또의 최고 순위와 최저 순위 (해시)

문제: 로또 최고/최저 순위 구하기

설명

로또 6/45는 1~45 중 6개를 선택하는 복권입니다. 사용자가 구매한 번호 중 알아볼 수 없는 번호는 0으로 표시됩니다. 당첨 번호가 공개된 뒤, 주어진 로또 번호(lottos)와 당첨 번호(win_nums)를 바탕으로 가능한 최고 순위와 최저 순위를 구해 배열로 반환하세요.

• 번호의 순서는 상관없습니다.
• 0은 어떤 번호로도 해석될 수 있습니다(단, 1~45 범위, 중복 없이 가정).

순위 기준

• 6개 일치: 1등
• 5개 일치: 2등
• 4개 일치: 3등
• 3개 일치: 4등
• 2개 일치: 5등
• 그 외: 6등

요구사항

• 최고 순위: (실제 일치 개수 + 0의 개수)을 최대 일치로 본 순위
• 최저 순위: (실제 일치 개수)만 고려한 순위
• 결과는 [최고 순위, 최저 순위] 형태로 반환

매개변수

• int[] lottos (길이 6): 사용자가 구매한 번호(0은 미확정)
• int[] win_nums (길이 6): 당첨 번호

제약

• lottos의 원소: 0 이상 45 이하
• win_nums의 원소: 1 이상 45 이하
• lottos의 0을 제외한 숫자들은 중복 없음
• win_nums는 중복 없음
• 정렬 여부는 보장하지 않음

입출력 예

lottoswin_numsresult

[44, 1, 0, 0, 31, 25]	[31, 10, 45, 1, 6, 19]	[3, 5]
[0, 0, 0, 0, 0, 0]	[38, 19, 20, 40, 15, 25]	[1, 6]
[45, 4, 35, 20, 3, 9]	[20, 9, 3, 45, 4, 35]	[1, 1]

 

설명 예시

• 예시1: 0 두 개를 각각 10, 6으로 해석하면 4개 일치(3등) 가능. 최소는 2개 일치(5등).
• 예시2: 전부 0이면 최대 6개 일치(1등), 최소 0개 일치(6등).
• 예시3: 모두 일치이므로 최고·최저 모두 1등.

---

처음에는 정렬한 후에 비교해서 풀어야겠다는 생각을 해봤지만 아무리봐도 아닌 것 같아서 다시 생각해 보니

그냥 간단하게 HashSet에 담은 후에 lottos에 숫자가 win_nums에 있는 숫자와 몇 개나 맞았는지와 0의 개수를 구한 후에

최고 순위 : 맞춘 번호 개수 + 0의 개수

최저 순위 : 맞춘 번호 개수

를 이용해서 int[] rank = {6, 6, 5, 4, 3, 2, 1}를 생성해 해당 인덱스의 숫자를 각각 반환해 주면 되는 간단한 알고리즘이었다.

 

알고리즘 코드

import java.util.Set;
import java.util.HashSet;

class Solution {
    public int[] solution(int[] lottos, int[] win_nums) {
        Set<Integer> winSet = new HashSet<>();

        for (int num : win_nums) {
            winSet.add(num);
        }

        int zeroCount = 0; 
        int matchCount = 0; 

        for (int num : lottos) {
            if (num == 0) {
                zeroCount++;
            } else if (winSet.contains(num)) {
                matchCount++;
            }
        }
        
        int[] rank = {6, 6, 5, 4, 3, 2, 1}; 
        int best = rank[matchCount+zeroCount];
        int worst = rank[matchCount];
        return new int[]{best, wors};
        
    }
}

 

 

시간 복잡도 분석

for문만큼 순회하므로 총 시간 복잡도는 O(n)이다.