[programmers lv.1 python] '로또의 최저 순위와 최고 순위' 풀이

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

프로그래머스

문제

 

흥미로운 문제였다. 처음엔 for문으로 lottos를 순회하면서 win_nums와 겹치는 숫자를 구분하려고 했는데, lottos의 원소 중 0이 나오면 처리를 어떻게 해야할지 막혀서 고민을 오래 했다.

고민을 오래 한 이유 중에는 0이 모두 당첨 번호일때와 모두 틀릴 때, 몇개는 당첨 번호이고 몇 개는 틀린 경우일 때도 생각해줘야 한다고 생각해서도 있었다.

 

하지만 문제의 제목이 '최저 순위와 최고 순위' 이듯, 0이 모두 당첨 번호일 때와 모두 아닐 때만 생각해주면 됐었는데 문제 이해를 제대로 못해서 오버프로그래밍 하고 있었다가 아차 싶어서 처음부터 다시 짰다 ㅠ

 

전략 

• 최고 순위: 0이 모두 당첨 번호에 해당한다고 가정하고, 맞춘 숫자의 개수에 0의 개수를 더하여 계산
• 최저 순위: 0을 모두 제외하고, lottos와 win_nums에서 겹치는 숫자를 세서 계산

원래는 맞춘 숫자의 갯수를 세려면 for문을 순회해야 한다고 생각해서 코드를 짰다.

correct = 0 # correct: 맞춘 숫자의 갯수
for lotto in lottos:
    if lotto in win_nums:
        correct += 1

이렇게 짜면 시간 복잡도가 O(n * m) (n은 lottos 리스트의 크기, m은 win_nums 리스트의 크기)가 되서 거의 2중 for문처럼 동작할 거라고 생각했는데, 리스트 크기가 고정되어 있어서 큰 무리는 아닐 것 같았지만 더 효율적으로 correct를 찾을 수 있는 방법이 set이라고 생각해 코드를 수정했다.

correct = len(set(lottos) & set(win_nums))

 

set과 교집합 연산자 &를 써서 시간복잡도를 O(1)로 줄였다!

 

count로 0의 개수를 세 준 다음, 최고 순위와 최저 순위를 계산했다.

zeros = lottos.count(0)

# 최고 순위: 0이 모두 맞췄다고 가정 (현재 맞춘 개수 + 0의 개수)
max_rank = min(7 - (correct + zeros), 6)  # 최고 순위

 

• correct + zeros:
  • 이 둘을 더한 값은 "0을 모두 당첨 번호라고 가정했을 때" 맞출 수 있는 최대 숫자의 개수
• 7 - (correct + zeros):
  • 로또 순위는 맞춘 숫자에 반비례해서 순위를 매김. 즉, 6개를 맞추면 1등, 5개면 2등 등으로, 맞춘 숫자가 클수록 순위는 낮아짐
  • 따라서 7 - (correct + zeros)로 로또에서 맞춘 숫자에 따른 순위를 계산함
    • ex) 6개를 맞추면 7 - 6 = 1등, 5개면 7 - 5 = 2등
• min(7 - (correct + zeros), 6):
  • 로또 순위는 최대 6위(낙첨)까지 있음. 0개에서 1개 맞춘 경우는 모두 6위로 처리되도록 구현
  • 따라서 계산된 순위가 6보다 크면 6위로 제한하기 위해 min 함수를 사용

# 최저 순위: 0이 모두 틀렸다고 가정 (현재 맞춘 개수)
min_rank = min(7 - correct, 6)  # 최저 순위

• correct:
  
  • 최저 순위는 0이 모두 틀렸다고 가정하므로, correct만으로 순위를 계산
• 7 - correct:
  • 최고 순위 계산과 동일하게, 맞춘 번호에 따른 순위를 계산함
• min(7 - correct, 6):
  • 최저 순위도 6위(낙첨)으로 제한하기 위해 min 함수를 사용해서 순위가 6보다 크면 6위로 처리

 

정답 코드

def solution(lottos, win_nums):
    zeros = lottos.count(0)
    correct = len(set(lottos) & set(win_nums))

    max_rank = min(7 - (correct + zeros), 6)
    min_rank = min(7 - correct, 6)
    
    return [max_rank, min_rank]

 

구한 최고 순위와 최저 순위 자체를 리스트에 넣어 반환하면서 마무리!

속도 매우 빠르다! 편ㅡ안

오래 걸렸지만 재밌는 문제였다 ..