[프로그래머스] 모의고사(python) + 반례

문제

수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 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하는 값을 오름차순 정렬해주세요.

풀이

이 문제는 일정하게 반복되는 패턴으로 답을 찍는 수포자 3명이 존재하고, 답안이 존재할 때 해당 답안에서 각 수포자가 몇문제씩을 맞추었는지를 알아낸 후 누가 가장 많이 맞추었는지를 리턴하는 문제입니다. 정리하면 다음과 같습니다.

1. 반복되는 패턴으로 찍는 3가지 경우가 존재하고, 하나의 답안이 존재
2. 해당 답안과 반복되는 패턴을 비교하여, 각각 몇 문제를 맞추었는지를 알아냄
3. 그 중에서 누가 가장 많이 맞추었는지를 리턴 (맞춘 문제의 수가 같은 경우 다 리턴)

이렇게 조건을 정리 후 풀이를 해보면 먼저 1번부터 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]

패턴을 모두 찾았으니 이제는 답안지의 답과 반복되는 패턴이 있는 리스트를 비교하면 되는데, 비교를 위해서 반복되는 값을 각 리스트에 10000개를 모두 넣을 수도 있겠지만, % 연산자를 이용해서도 비교를 할 수 있습니다. 예를 들면 1번의 경우 5개가 반복되기 때문에 i%5로 계산을 하면 비교가 가능합니다. 예시는 다음과 같습니다.

    for i in range(len(answers)):    # 답안지의 답이랑 찍은 답이랑 비교해서 같으면 +1
        if(answers[i] == a1[i%5]):
            countans[0] += 1

그 후에 답안지와의 비교가 끝이 났으면 0번째부터 카운트 된 리스트 countans의 값 중에서 가장 많이 맞춘 사람이 누구인지를 리턴하고, 맞춘 정답의 수가 같은 경우 동점자 모두를 리턴해주면 됩니다. 소스코드는 아래와 같습니다.

def solution(answers):
    answer = []
    countans = [0,0,0]            # 정답이 몇개인지 카운트하는
    max =0                         # 최대값이 얼마인지
    a1 = [1,2,3,4,5]               # 1번부터 3번까지 반복되는 찍는 방식을 미리 리스트로 만듦
    a2 = [2,1,2,3,2,4,2,5]
    a3 = [3,3,1,1,2,2,4,4,5,5]
    
    for i in range(len(answers)):    # 답안지의 답이랑 찍은 답이랑 비교해서 같으면 +1
        if(answers[i] == a1[i%5]):
            countans[0] += 1
        if(answers[i] == a2[i%8]):
            countans[1] += 1
        if(answers[i] == a3[i%10]):
            countans[2] += 1
    
    for i in range(len(countans)):   # 몇개 맞추었는지 비교
        if(i == 0):                  # 첫번째일 경우 일단 append하고 max
            answer.append(i+1) 
            max = countans[i]
        elif(countans[i] == max):    # max 값이랑 같으면 append
            answer.append(i+1)
        elif(countans[i] > max):     # max 값이랑 다르면 앞에 넣은 값 빼고 append
            answer.pop()         
            answer.append(i+1)
            max = countans[i]         # 이것은 예외의 경우가 생길 수 있을 것 같음(?) 
    
    return answer

 

이렇게 풀이를 하면 모든 테스트케이스를 정상적으로 통과하는 것을 확인할 수 있습니다.

 

+ 내 풀이에 대한 반례

이 문제의 풀이를 하고나니 '만약 1번 수포자와 2번 수포자가 맞춘 문제의 개수가 같고, 3번 수포자가 가장 많은 문제를 맞추었을 때 위의 풀이와 비교하였을때 답이 맞는가?' 라는 의문점이 생겼습니다. 그래서 생각을 충분히 해본 후 반례를 하나 찾아냈습니다. 반례를 포함하여 조건을 한번 정리해보았습니다.

• 만약 answer의 값이 [3,3,1,1,3,3] 인 경우
• 수포자 1과 2는 모든 문제를 틀리게 됩니다. 그리고 수포자 3은 4문제를 맞추게 됩니다.
• 여기서 맞춘 개수를 카운트하고 난 후 countans를 기준으로 비교

 

    for i in range(len(countans)):   # 몇개 맞추었는지 비교
        if(i == 0):                  # 첫번째일 경우 일단 append하고 max
            answer.append(i+1) 
            max = countans[i]
        elif(countans[i] == max):    # max 값이랑 같으면 append
            answer.append(i+1)
        elif(countans[i] > max):     # max 값이랑 다르면 앞에 넣은 값 빼고 append
            answer.pop()         
            answer.append(i+1)
            max = countans[i]         # 이것은 예외의 경우가 생길 수 있을 것 같음(?)

여기서 이 for문을 통과할 때 countans의 값은 [0,0,4] 가 됩니다. 그리고 원래대로라면 제일 많이 맞춘 수포자 3만 정답이 되어야 합니다. 그러나 위의 코드에서는 다음과 같은 과정을 거치게 됩니다.

1. contans[0] 에서 if 문을 지나면 countans = [1] , max = 0 이 됩니다.
2. contans[1] 에서 if 문을 지나면 countans = [1,2] , max = 0 이 됩니다.
3. contans[0] 에서 if 문을 지나면 countans = [1,3] , max = 4 이 됩니다.

이렇게 되면 최종적으로 [1,3]이 리턴되나, 원래는 [3]이 리턴되어야 합니다. 여기서 for문을 다음과 같이 변경하면 문제가 생기지 않게 됩니다.

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

이렇게 되면 위의 경우에도 [3]이 정상적으로 리턴됩니다. 위와 같이 풀면 이러한 문제없이 풀이가 가능하나 뭔가에 꽂히면 파고드는 성격 때문에 해결하다보니 여기까지 온 것 같습니다.  알고리즘 문제를 해결하다보면 이런 재미있는(?) 요소도 가끔 존재하는 것 같습니다.