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

24년 12월 27일
해결한 문제 갯수: 1

 

문제 설명

 

문제 분석

• 로또 6/45는 1부터 45까지의 숫자 중 6개를 찍어 맞히는 대표적인 복권입니다. 알아볼 수 없는 번호(0)를 포함하여 민우가 구매한 로또 번호와 당첨 번호가 주어질 때, 당첨 가능한 최고 순위와 최저 순위를 리턴하는 문제입니다.
• 제한사항 
  • lottos는 길이 6인 정수 배열입니다.
  • lottos의 모든 원소는 0 이상 45 이하인 정수입니다.
  • 0은 알아볼 수 없는 숫자를 의미합니다.
  • win_nums는 길이 6인 정수 배열입니다.

 

첫 번째 접근: filter, includes O(n²)

function solution(lottos, win_nums) {
    const correct = lottos.filter(el => win_nums.includes(el)).length
    const posibility = lottos.filter(el => !el).length
    
    const min = 7 - correct
    const max = 7 - correct - posibility
    
    return [max > 6 ? 6 : max , min > 6 ? 6 : min]
}

• correct: 현재 맞은 번호 개수 계산
• posibility: 알아볼 수 없는 번호(0) 개수 계산
• 순위 계산
  • min: 최저 순위 (7 - 맞은 개수)
  • max: 최고 순위 (7 - 맞은 개수 - 가능성 있는 개수)
• 6등 처리: 순위가 6보다 크면 6으로 조정

 

두 번째 접근: filter, includes O(n²)

function solution(lottos, win_nums) {
    const rank = [6, 6, 5, 4, 3, 2, 1]
    
    const correct = lottos.filter(el => win_nums.includes(el)).length
    const posibility = lottos.filter(el => !el).length
    
    return [rank[correct + posibility], rank[correct]]
}

개선된 점

1. rank 배열 활용
   • 맞은 개수를 인덱스로 사용하여 순위 계산
   • 0, 1개 맞았을 때 모두 6등 처리가 자동으로 됨
2. 조건문 제거
   • 삼항 연산자 대신 배열 인덱싱 사용

시간 복잡도

• filter와 includes 사용: O(n²)
• 하지만 입력 크기가 항상 6으로 고정되어 있어 실제로는 상수 시간

 

세 번째 접근: Set O(n)

function solution(lottos, win_nums) {
    const rank = count => count > 1 ? 7 - count : 6;
    const winSet = new Set(win_nums);
    
    const zero = lottos.filter(n => !n).length;
    const match = lottos.filter(n => winSet.has(n)).length;
    
    return [rank(match + zero), rank(match)];
}

개선된 점

 

• rank 계산 로직을 함수로 분리
• 시간 복잡도 개선