[프로그래머스] 완전탐색 - 모의고사 (feat. cycle 함수)

문제링크

 

나의 풀이

1. 1,2,3번의 답변자는 규칙적인 답변을 찍음 --> 미리 답변 list를 구성
2. 1,2,3번의 답변자는 각각 a,b,c의 변수로 저장하여 사용할 것임
3. input되는 answers의 길이는 10000까지 확장될 수 있음.
   • 1번 답변자가 5개만으로 이루어진 규칙을 형성하므로, 가장 적은 길이인 1번 답변자를 기준으로 len(answers)와 길이를 맞춰주었음.
4. for 반복문을 활용해서 answers 의 정답과 비교
5. 정답들의 max값을 구하고 동점자가 존재할 수 있으니, for문을 활용하여 max값과 동일한 답변자를 index로 추출 (abc로 지정했기 때문에 원하는 답변을 얻으려면 인덱스로 추출해야함)
6. 오름차순으로 정렬하여 return

def solution(answers):
    
    a = [1, 2, 3, 4, 5]
    b = [2,1,2,3,2,4,2,5]
    c = [3,3,1,1,2,2,4,4,5,5]
    
    i = 1
    while len(a)*i < len(answers):
        i+=1
    a *= i
    b *= i
    c *= i
    
    # 점수 계산
    a_score, b_score, c_score = 0,0,0
    for j in range(0, len(answers)):
        if answers[j] == a[j] :
            a_score +=1
        if answers[j] == b[j]:
            b_score +=1
        if answers[j] == c[j]:
            c_score +=1
    
    score = []
    score.append(a_score)
    score.append(b_score)
    score.append(c_score)
    
    # a,b,c score 중 max값들의 인덱스를 넣어준 결과값을 출력
    result = []
    for i in range(0,3):
        if max(score) == score[i]:
            result.append(i+1)
    result.sort()
    return result

 

나의 풀이 문제점

1. while문을 넣음으로써 시간 복잡도 증가
2. 전체적으로 모든 과정을 풀어서 쓴듯한 풀이기 때문에 시간복잡도가 증가할 수밖에 없다.

 

다른사람풀이

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

프로그래머스

    score = [0, 0, 0]
    result = []

    for idx, answer in enumerate(answers):
        if answer == pattern1[idx%len(pattern1)]:
            score[0] += 1
        if answer == pattern2[idx%len(pattern2)]:
            score[1] += 1
        if answer == pattern3[idx%len(pattern3)]:
            score[2] += 1

    for idx, s in enumerate(score):
        if s == max(score):
            result.append(idx+1)

• 나의 풀이 처럼 append 하는 과정을 거치지 않고 바로 score 안에서 +=1 로 처리
• idx와 리스트의 튜플형태로 반환되는 enumerate를 이용해서 idx, answer에 적합한 수를 넣어주고, 나머지값을 이용해서 pattern1 (내 풀이에선 a) 의 인덱스를 넣어주었다. 

이 외에도 cycle 함수를 사용한 풀이도 인상적이었다. 내가 찾던 풀이다! 
문제에서 보면, abc의 답변자는 같은 답을 반복하게 되는데 이럴때 사용하면된다.

👉 cycle 이란

from itertools import cycle

a = cycle([1,2,3,4,5])

next(a)
# 결과 : 1

next(a)
# 결과 : 2

• 이렇게 a라는 리스트는 무한루프를 돌게 되고, next로 호출하면 1,2,3,4,5 가 순서대로 출력된다. 5 이후에는 다시 1이 출력되면서 무한으로 계속해서 불러와 지게 된다.

👉 cycle 을 이용한 풀이

from itertools import cycle
answers = [1,3,2,4,2]

def solution(answers):
    
    student = [
        cycle([1,2,3,4,5]),
        cycle([2,1,2,3,2,4,2,5]),
        cycle([3,3,1,1,2,2,4,4,5,5]),
    ]

    scores = [0,0,0]

    for num in answers: # answers 만큼 순회
        for i in range(3): # student 1,2,3 순회
            if next(student[i]) == num:
                scores[i] +=1
    
    result = []
    for i in range(0,3):
        if max(scores) == scores[i]:
            result.append(i+1)
    result.sort()
    return result