[1일 3알고리즘] Day5

1. 모의고사

이 문제는 원래 아래와 같이 시도했었다.

def solution(answers):
    ans = []
    scoreDic = {}
    scoreDic.update({1: math1(answers)})
    scoreDic.update({2: math2(answers)})
    scoreDic.update({3: math3(answers)})

    scoreDic = sorted(scoreDic.items(), key=lambda item: item[1], reverse=True)

    highest_score = scoreDic[0][1]

    for key, value in scoreDic:
        if value == highest_score:
            ans.append(key)
        else:
            break

    return ans


def math1(ans):
    cnt = 0
    i = 0
    for j in range(1, len(ans)):
        if ans[i] == j:
            cnt += 1
        i += 1
    return cnt


def math2(ans):
    cnt = 0
    mathAns = []
    for i in range(len(ans)):
        if i % 2 == 0:
            mathAns.append(2)
        else:
            mathAns.append((i // 2) + 1)

    for i in range(len(ans)):
        if ans[i] == mathAns[i]:
            cnt += 1
    return cnt


def math3(ans):
    cnt = 0
    mathAns = []
    for i in range(len(ans)):
        if i < 2:  
            mathAns.append(3)
        else:
            mathAns.append((i - 2) // 2 + 1)

    for j in range(len(ans)):
        if ans[j] == mathAns[j]:
            cnt += 1
    return cnt

그런데 채점을 돌려보니, 몇개의 tc가 제대로 동작하지 않았다. 아마 1 2 3학생의 답안을 만드는 과정에서 문제가 있었을 것 같다.

def solution(answers):
    ans = []
    scoreDic = {}
    scoreDic.update({1: math1(answers)})
    scoreDic.update({2: math2(answers)})
    scoreDic.update({3: math3(answers)})

    # 점수를 내림차순으로 정렬
    scoreDic = sorted(scoreDic.items(), key=lambda item: item[1], reverse=True)

    # 가장 높은 점수
    highest_score = scoreDic[0][1]

    # 가장 높은 점수를 얻은 사람 찾기
    for key, value in scoreDic:
        if value == highest_score:
            ans.append(key)
        else:
            break

    return ans

def math1(answers):
    pattern = [1, 2, 3, 4, 5]
    return sum(1 for i, ans in enumerate(answers) if ans == pattern[i % len(pattern)])

def math2(answers):
    pattern = [2, 1, 2, 3, 2, 4, 2, 5]
    return sum(1 for i, ans in enumerate(answers) if ans == pattern[i % len(pattern)])

def math3(answers):
    pattern = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]
    return sum(1 for i, ans in enumerate(answers) if ans == pattern[i % len(pattern)])

위 풀이는 도저히 해결 방법을 모르겠어서 지피티의 도움을 받은 부분인데, 지피티가 제안해 준 방식이 원래 내가 원하던 방식(= 배열을 만들고 문제 수 많큼 답을 만드는 것)과도 유사해서 이를 더 공부해야겠다.

 

2. 소수 만들기 (RE)

이 문제는 나중에 다시 풀 계획이다. 아래는 솔루션 중 combination을 사용한 사례이고, 나는 이 문제가 BFS인줄 알았다...  라이브러리를 쓸 생각도 못해서, 꼭 다시 풀 예정이다.

def solution(nums):
    from itertools import combinations as cb
    answer = 0
    for a in cb(nums, 3):
        cand = sum(a)
        for j in range(2, cand):
            if cand%j==0:
                break
        else:
            answer += 1
    return answer

 

 

3. 실패율

https://school.programmers.co.kr/learn/courses/30/lessons/42889

프로그래머스

def solution(N, stages):

    persent = []
    ans = []
    for num in range(1, N+1):
        fail = 0
        success = 0
        for i in range(len(stages)):
            if stages[i] == num:
                fail += 1
            elif stages[i] > num:
                success += 1
        if fail == 0:
            persent.append((num, 0))
        else:
            persent.append((num, fail / (fail + success), 2))

    persent = sorted(persent, key=lambda x:x[1], reverse=True)
    for i in range(len(persent)):
        ans.append(persent[i][0])
    return ans

처음엔 위와 같이 시도했는데, 3개의 tc에서 시간초과가 났다.

def solution(N, stages):
    cnt = [0 for i in range(600)]
    persent = []
    ans = []
    challenger = len(stages)

    for i in range(len(stages)):
        cnt[stages[i]] += 1

    for i in range(1, N + 1):
        if challenger != 0:
            fail = cnt[i]
            persent.append((i, fail / challenger))
            challenger -= fail
        else:
            persent.append((i, 0))

    persent = sorted(persent, key=lambda x:x[1], reverse=True)
    for i in range(len(persent)):
        ans.append(persent[i][0])
    return ans

다음과 같이 이중 for문을 없애는 방안으로 변경하여 해결!