[programmers/python] 모의고사 - 완전탐색

문제 설명

• url : https://school.programmers.co.kr/learn/courses/30/lessons/42840?language=python3

1번부터 N번까지 총 answers 배열만큼 문제가 주어진다.
세 명의 수포자가 각자 고정된 패턴으로 문제를 찍고 있으며, 정답과 비교했을 때 가장 많은 문제를 맞힌 수포자의 번호를 오름차순으로 리턴해야 한다.

수포자의 답안 패턴

1번	1, 2, 3, 4, 5 반복
2번	2, 1, 2, 3, 2, 4, 2, 5 반복
3번	3, 3, 1, 1, 2, 2, 4, 4, 5, 5 반복

---

해결 전략

모든 수포자에 대해, answers 리스트를 순회하며 정답을 한 문제씩 비교해본다.

• 수포자의 패턴은 주기적으로 반복되므로, **i % len(패턴)**을 통해 현재 수포자가 찍은 답을 구할 수 있다.
• 이를 정답과 비교하여 맞춘 개수를 각각 저장한다.
• 세 사람 중 가장 높은 점수를 받은 사람의 번호를 오름차순으로 반환한다.

---

구현 코드

def countAns(answers, pattern): 
    c = 0
    for i in range(len(answers)): 
        p = pattern[i % len(pattern)]
        a = answers[i]
        if p == a:
            c += 1
    return c
    
def solution(answers):
    p1 = [1, 2, 3, 4, 5]
    p2 = [2, 1, 2, 3, 2, 4, 2, 5]
    p3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]
    
    cp1 = countAns(answers, p1)
    cp2 = countAns(answers, p2)
    cp3 = countAns(answers, p3)
    
    _max = max(cp1, cp2, cp3)
    
    answer = []
    for i, score in enumerate([cp1, cp2, cp3]):
        if score == _max:
            answer.append(i + 1)  # 수포자 번호는 1부터 시작
    
    return answer

---

예시 실행

solution([1, 2, 3, 4, 5])  # 결과: [1]

• 1번 수포자: 5문제 맞춤
• 2번 수포자: 0문제
• 3번 수포자: 0문제
  → 결과: [1]

solution([1, 3, 2, 4, 2])  # 결과: [1, 2, 3]

• 세 수포자 모두 2문제씩 정답
  → 결과: [1, 2, 3]

---

시간 복잡도

• 수포자 3명 × answers의 길이만큼 비교 → O(n)
• 최대 10,000문제까지 비교해도 성능에 전혀 문제가 없다