문제

https://programmers.co.kr/learn/courses/30/lessons/42840

수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.

1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...
2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ...
3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...

1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성하시오.

---

권장 시간: 30분
권장 시간 복잡도: O(N)
출제: 완전 탐색

---

제약 조건

• 시험은 최대 10,000 문제
• 문제의 정답은 1, 2, 3, 4, 5 중 하나
• 가장 높은 점수를 받은 사람이 여럿이라면 반환하는 값을 오름차순으로 정렬

---

풀이

1. 패턴을 미리 리스트에 저장(특정 값이나 패턴이 주어지면 하드 코딩하는게 좋음)
2. 패턴과 답안을 비교해서 일치하는 개수를 지정하는 리스트를 선언
3. 각 정답지에 패턴을 매치하여 맞춘 정답 개수를 구해 score에 저장
4. 반복문에서 가장 높은 점수 저장
5. 가장 큰 점수를 갖는 수포자들을 찾아 리스트에 담아 반환

def solution(answers):
    patterns = [
        [1,2,3,4,5],
        [2,1,2,3,2,4,2,5],
        [3,3,1,1,2,2,4,4,5,5]
    ]
    # 점수 저장 리스트
    scores = [0] * 3
    
    # 패턴, 정답 일치 확인
    for i, answers in enumerate(answers):
        for j, patterns in enumerate(patterns):
        	# 정답 패턴 길이가 답안 길이보다 긴 경우 정답 처음 데이터와 다시 비교
            if answers == patterns[i % len(patterns)]:
                scores[j] += 1
                
    # 가장 높은 점수 저장
    max_score = max(scores)
    
    # 가장 높은 점수를 가진 수포자들의 번호를 찾아 리스트에 저장
    highest_scores = []
    for i, score in enumerate(scores):
        if score == max_score:
            highest_scores.append(i + 1)
    return highest_scores

enumerate() 함수
인자로 넘어온 목록을 기준으로 인덱스와 원소를 차례대로 접근하게 해주는 반복자(iterator) 객체를 반환해주는 함수

---

시간 복잡도

• N은 answers의 길이
• 각 수포자들의 패턴과 정답을 비교하는 부분은 O(N)
• 이 후 scores를 순회하며 가장 높은 수포자를 추가하는 연산은 O(1)
• 따라서 최종 시간 복잡도는 O(N)