Level 1 모의고사 Python3

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

코딩테스트 연습 - 모의고사

 

최종 코드

• GitHub https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level1_모의고사.py

hwayeon351/Programmers-Algorithms

def solution(answers):
    answer = []
    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]
    cnt = [0,0,0]
    
    for i, a in enumerate(answers):
        if p1[i%5]==a: cnt[0]+=1
        if p2[i%8]==a: cnt[1]+=1
        if p3[i%10]==a: cnt[2]+=1

    for i in range(3):
        if max(cnt)==cnt[i]:
            answer.append(i+1)
            
    return answer

---

풀이 과정

풀이 시간 11분

먼저 문제를 정리해보면,

1. 수포자는 총 3명으로 찍는 패턴이 정해져 있다.

2. 배열 answers에 문제의 정답이 순서대로 주어진다.

3. 가장 많은 문제를 맞힌 수포자를 배열에 담아 return하고, 동점자인 경우 오름차순으로 정렬하여 return한다.

 

수포자 세 명은 일정한 패턴으로 문제를 찍고 있다는 것에 중점을 두었다. 수포자 1은 1, 2, 3, 4, 5 패턴으로 반복적으로 문제를 찍고 있기 때문에 (문항 번호 % 5)를 하여 수포자 1이 해당 문제를 몇번으로 찍었는지를 구할 수 있다. 이를 활용해서 answers에 담긴 각 문항의 정답을 순서대로 수포자의 답과 비교하여 카운팅을 해주었다. 결국 이 문제는 for문을 사용하여 모든 문항을 비교하기 때문에 완전 탐색 알고리즘 중 Brute-Force Search 알고리즘을 사용하는 문제이다. answers의 최대 길이는 10,000문제로 제한되어 있기 때문에 완전 탐색으로 진행해도 무리가 없다.

 

def solution(answers):
    answer = []
    #1. 수포자별 찍는 방식 배열로 나타내기, 정답수 초기화
    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]
    cnt = [0,0,0]
    
    #2. 정답 체크 | 시간 복잡도 = O(n) 
    for i, a in enumerate(answers):
        if p1[i%5]==a: cnt[0]+=1
        if p2[i%8]==a: cnt[1]+=1
        if p3[i%10]==a: cnt[2]+=1

    #3. 가장 많이 맞힌 사람 answer에 추가하기 | 시간 복잡도 = 3
    for i in range(3):
        if max(cnt)==cnt[i]:
            answer.append(i+1)
            
    return answer
#Brute-Force Search
#시간복잡도 = O(N), 공간복잡도 = O(1)