프로그래머스 level 1 모의고사 (Python 파이썬)

💡문제 링크

소요시간 15분

이전에 풀었던 문제지만 '코딩 테스트 합격자 되기' 책을 공부하면서 책에서 나와 다시 풀어보았다.

프로그래머스

 

💡문제 분석 요약

수포자 학생 3명이 각자의 규칙을 가지고 문제를 찍는다. 찍은 답이 리스트에 담겨져 있다.

실제 시험의 답안이 answers 배열에 담겨있다.

가장 많은 답을 맞춘 학생이 누구인지 배열에 담아 오름차순으로 정렬해서 return하기

 

 

💡알고리즘 설계

일단 각 수포자가 각자의 규칙으로 낸 답안지 리스트를 만든다(s1, s2, s3)

답지 리스트랑 비교해서 맞춘 문제의 개수 정보를 담은 변수를 생성한다(a1, a2, a3)

맞춘 개수가 가장 많은 학생이 누구인지 배열에 나타낸다. 이 때 학생이 두 명 이상이면 오름차순으로 정렬해야 한다.

💡코드

def solution(answers):
    
    s1 = list(range(1, 6)) * (len(answers)//5 + 1)
    s2 = [2, 1, 2, 3, 2, 4, 2, 5] * (len(answers)//8 + 1)
    s3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5] * (len(answers)//10 + 1)

    a1 = sum([1 for i in range(len(answers)) if answers[i] == s1[i]])
    a2 = sum([1 for i in range(len(answers)) if answers[i] == s2[i]])
    a3 = sum([1 for i in range(len(answers)) if answers[i] == s3[i]])
    
    s = [0, a1, a2, a3]
    ans = []
    for i in range(1, 4):
        if s[i] == max(s):
            ans.append(i)
    return ans

 

💡 오답 풀이

맞춘 개수가 가장 많은 학생이 누구인지 배열에 나타낸다. 이 때 학생이 두 명 이상이면 오름차순으로 정렬해야 한다.

-> 이 부분이 꽤 까다로웠다. 학생의 수는 3명으로 정해져 있기 때문에, 처음에는 아래와 같이 적었다.

ans = [0, a1, a2, a3]
    c = ans.count(max(ans))
    # 가장 높은 점수가 1명일 때
    if c == 1:
        return [ans.index(max(ans))]
    # 가장 높은 점수가 2명일 때
    elif c == 2:
        [1, 2, 3].remove(ans.index(min(ans)))
    # 가장 높은 점수가 3명일 때 = 모두 점수가 같을 때
    else:
        return [1, 2, 3]

하지만 계속 런타임 에러가 떴다.

그래서 이 부분을 좀 더 간단하게 바꿔보았다.

    s = [0, a1, a2, a3]
    ans = []
    for i in range(1, 4):
        if s[i] == max(s):
            ans.append(i)

인덱스를 기준으로 반복문을 돌며 해당 인덱스의 원소가 최댓값과 동일하면 그 인덱스를 빈 리스트 ans에 넣는 방식을 바꾸었더니 정답이었다.

💡 다른 풀이

1. 책에 나온 코드

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, answer in enumerate(answers):
        for j, pattern in enumerate(patterns):
            if answer == pattern[i % len(pattern)]:
                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

책에 있던 코드. 내가 작성한 코드보다 효율성 측면에서 좋은 코드이다.

시간복잡도

    for i, answer in enumerate(answers): => 시간복잡도 O(N)
        for j, pattern in enumerate(patterns): => 시간복잡도 O(3)
            if answer == pattern[i % len(pattern)]:
                scores[j] += 1

시간 복잡도 측면에서 보면 책에서 나온 코드는 반복문에서 시간복잡도가 O(N*3) = O(N)이다.

메모리사용

    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

만들어지는 리스트는 patters와 scores, 두 개 뿐이다. patterns는 고정크기이며 scores도 길이가 3이라서 메모리 사용량이 적다.

 

2. 이전에 작성했던 코드

def solution(answers):
    answer = []
    s = [0, 0, 0, 0]
    st1 = [1, 2, 3, 4, 5] * (len(answers) // 5 + 1)
    st2 = [2, 1, 2, 3, 2, 4, 2, 5] * (len(answers) // 8 + 1)
    st3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5] * (len(answers) // 10 + 1)
    for i in range(len(answers)): # 0~4
        if answers[i] == st1[i]:
            s[1] += 1
        if answers[i] == st2[i]:
            s[2] += 1
        if answers[i] == st3[i]:
            s[3] += 1

    m = max(s)
    
    for j in range(len(s)):
        if s[j] == m:
            answer.append(j)
    return answer

 

시간 복잡도

    for i in range(len(answers)):  # O(N)
        if answers[i] == st1[i]:  # O(1)
            s[1] += 1
        if answers[i] == st2[i]:  # O(1)
            s[2] += 1
        if answers[i] == st3[i]:  # O(1)
            s[3] += 1

 

시간 복잡도는 반복문/조건문에서 계산하면 된다.

첫번째 for문은 answers의 길이(N)만큼 반복하므로 시간 복잡도가 O(N)이다.

나머지 조건문은 두 값이 같은지 확인만 하니까 시간 복잡도가  O(1)이다.

이 모든 시간복잡도를 고려하면 최종 시간 복잡도는 O(N)이다.

메모리 사용

    answer = []
    s = [0, 0, 0, 0]
    st1 = [1, 2, 3, 4, 5] * (len(answers) // 5 + 1)
    st2 = [2, 1, 2, 3, 2, 4, 2, 5] * (len(answers) // 8 + 1)
    st3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5] * (len(answers) // 10 + 1)

총 5개의 리스트를 새로 만들게 되고, 특히 str1, str2, str3은 길이가 길다(answers의 최대길이가 10000이니까 str1, str2, str3도 길이가 최대 10000)

💡 느낀점 or 기억할정보

결론적으로 두 번째 코드는 시간복잡도 측면에서는 첫 번째 코드와 별 차이가 없지만, 메모리 사용량이 많다.

첫 번째 코드는 불필요한 리스트 생성이 없어서 효율적이다. 저런 아이디어를 가지고 다른 문제를 풀 수 있도록 기억해두어야겠다.

최대한 간단하게 할 수 있는 방법을 계속 생각해보자!