[Programmers] 완전 탐색 - 모의고사

 

문제를 읽으면서 가장 먼저 한 것은 1, 2, 3번 수포자가 정답을 찍는 방식에 있어서 패턴을 먼저 찾으려고 하였다.

먼저, 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라는 패턴이 반복되는 것을 확인할 수 있다.

 

코드를 작성하기 전에 파악한 이 패턴을 보기 쉽게 아래와 같이 정리하였고, 각각 몇 개의 수가 반복되는지 # 뒤에 적어 두었다.

def solution(answers):
    answer = []
    # 1 2 3 4 5 / 1 2 3 4 5 / ~ # 5
    # 2 1 2 3 2 4 2 5 / 2 1 2 3 2 4 2 5 / ~ # 8
    # 3 3 1 1 2 2 4 4 5 5 / 3 3 1 1 2 2 4 4 5 5 # 10

 

문제를 조금 더 읽다 보니 최대 10,000개의 문제로 구성되어 있다고 적혀 있었다.

처음에는 생각보다 적은 수여서 학생 1, 학생 2, 학생 3에 대해서 모든 경우의 수를 포함한 학생 리스트를 각각 만들려고 하였다.

귀찮기는 하지만 가장 편한 방법이라 이렇게 먼저 접근해 보았다.

st_1, st_2, st_3 = [], [], []
    
    for i in range(2000): # first student
        for j in range(5):
            st_1.append(j+1)
            
    for i in range(1250): # second student
        st_2.append(2)
        for j in range(4): # 1 3 4 5
            if j == 0:
                st_2.append(1)
            else:
                st_2.append(2)
                st_2.append(j+2)
    
    for i in range(1000): # third student
        for k in range(2):
            st_3.append(3)
        for k in range(2):
            st_3.append(1)
        for k in range(2):
            st_3.append(2)
        for k in range(2):
            st_3.append(4)
        for k in range(2):
            st_3.append(5)

 

세 번째 학생에 대한 코드를 적으면서 아무리 그래도 이건 좀 아닌 것 같다는 생각을 확실히 했다.

그리고 세 번째 학생까지 적고 나니 갑자기 리스트끼리 곱셈도 된다는 게 기억이 났다.

 

그래서 작성했던 모든 코드를 다 지우고 처음에 파악했던 패턴을 먼저 각 학생별로 부여하였다.

st_1 = [1, 2, 3, 4, 5] # 5
st_2 = [2, 1, 2, 3, 2, 4, 2, 5] # 8
st_3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5] # 10

 

그리고 문제에서 최대 10,000문제라고 적혀 있는 것이지, 모든 문제가 10,000개가 아니므로 미리 10,000개를 만들어 놓는 것은 너무 무의미하다.

그럼 '만약 정답이 13개라면, 미리 각 학생이 찍은 정답을 다 안만들어 두고 어떻게 알 수 있을까?'에 대한 생각을 할 수 있는데, 학부 시절에 이럴 때 많이 사용되는 연산자가 %라고 했던 것이 기억났다.

가령 첫번째 학생이 13번째에 찍은 정답이 궁금하다면 13%5를 하면 13을 5로 나눈 나머지인 3이 나올 것이고 첫 번째 학생이 4번째(파이썬은 0부터 시작하므로 3+1)로 찍은 값은 4라는 것을 알 수 있다. 마찬가지로 두 번째 학생의 경우 13%8을 하면 13을 8로 나눈 나머지는 5이므로, 실제 6번째 값인 4라는 것을 알 수 있다.

 

여기까지 생각하고 난 후, 이제 본격적인 채점 로직을 작성할 준비가 되었다.

먼저, 세 명의 학생에 대한 스코어를 저장할 리스트를 선언하고, 각 학생들의 스코어 초기값을 0으로 초기화해 준다.

scores = [0, 0, 0] # 순서대로 1번, 2번, 3번 학생에 대한 점수

 

이제 입력받은 정답의 수만큼 순회하면서 각 문항별로 실제 정답과 3명의 학생 각각이 찍은 정답이 일치하는지 조건문을 활용하여 비교하고, 일치한다면 각 학생의 스코어를 1점씩 올려주고 다음 문제를 채점하는 식으로 작성한다.

for i in range(len(answers)):
    if answers[i] == st_1[i%5]:
        scores[0] += 1
    if answers[i] == st_2[i%8]:
        scores[1] += 1
    if answers[i] == st_3[i%10]:
        scores[2] += 1

 

단, 여기서 주의해야 할 점은 1번 학생도, 2번 학생도, 3번 학생도 동일한 번호로 찍어서 다 맞을 수도 있기 때문에 첫 번째 조건문에 대해서 if 문을 쓰고, 그 후에 elif를 쓰지 않도록 주의해야 한다. elif의 경우, 만약 첫 번째 조건이 성립한다면 다음 조건을 비교하지 않고 바로 다음 반복문으로 넘어가기 때문이다.

 

이제 채점은 끝났다. 각 학생의 점수를 모두 알고 있으니 최고 득점자를 찾아야 한다. 이때는 max() 함수로 빠르게 찾을 수 있다.

max_score = max(scores)

 

이제 최종 출력 부분만 고려해서 마지막 코드를 작성하면 되는데, 가장 많은 문제를 맞힌 사람을 반환하면 된다. 단, 여러 명이 동일한 개수의 정답을 맞출 수도 있는데, 이 경우에는 오름차순으로 정렬된 상태로 반환을 해야 한다.

정렬까지 고려하기 위해서는 그냥 첫 번째 학생의 점수부터 비교하여 최대 점수와 일치하면 answer 리스트에 추가하도록만 작성해 주면 된다.

for i in range(len(scores)):
    if max_score == scores[i]:
        answer.append(i+1)

 

위와 같이 작성하게 되면, 첫 번째 학생이 최대 점수와 일치하면 정답 리스트에 추가되고, 그 다음으로 두 번째 학생이 최대 점수와 일치하면 정답 리스트에 추가되고 만약 일치하지 않는다면 그냥 pass 될 것이므로 오름차순을 고려하면서 가장 많은 정답을 맞춘 학생까지 포함할 수 있다.

 

문제 설명

수포자는 수학을 포기한 사람의 준말입니다.

수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다.

수포자는 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 함수를 작성해주세요.

 

제한 조건

시험은 최대 10,000 문제로 구성되어있습니다.

문제의 정답은 1, 2, 3, 4, 5중 하나입니다.

가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순 정렬해주세요.

 

입출력 예

answers       return

[1,2,3,4,5]    [1]

[1,3,2,4,2]    [1,2,3]

 

입출력 예 설명

입출력 예 #1

수포자 1은 모든 문제를 맞혔습니다.

수포자 2는 모든 문제를 틀렸습니다.

수포자 3은 모든 문제를 틀렸습니다.

따라서 가장 문제를 많이 맞힌 사람은 수포자 1입니다.

 

입출력 예 #2

모든 사람이 2문제씩을 맞췄습니다.

 

최종 코드

def solution(answers):
    answer = []
    # 1 2 3 4 5 / 1 2 3 4 5 / ~ # 5
    # 2 1 2 3 2 4 2 5 / 2 1 2 3 2 4 2 5 / ~ # 8
    # 3 3 1 1 2 2 4 4 5 5 / 3 3 1 1 2 2 4 4 5 5 # 10
    st_1 = [1, 2, 3, 4, 5] # 5
    st_2 = [2, 1, 2, 3, 2, 4, 2, 5] # 8
    st_3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5] # 10
    
    scores = [0, 0, 0]
    
    for i in range(len(answers)):
        if answers[i] == st_1[i%5]:
            scores[0] += 1
        if answers[i] == st_2[i%8]:
            scores[1] += 1
        if answers[i] == st_3[i%10]:
            scores[2] += 1
    
    max_score = max(scores)
    
    for i in range(len(scores)):
        if max_score == scores[i]:
            answer.append(i+1)
    
    return answer