[홀로 하는 코딩 공부] 퍼즐 게임 챌린지 (Python)

프로그래머스

사용 언어: Python

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/340212

프로그래머스

 

*** 본 문제를 푸는 과정을 공유하려 한다.

---

▶ 문제 자체가 단순하였기에 풀이 방향도 바로 잡혔다.

▶ 우선 시간 계산식부터 코드로 작성하였다. 그 다음, 어떤 level을 선택하냐에 따라 계산 시간 값이 달라지고, limit 내에 계산 시간 값이 속하는 것들 중에 최소 level을 선택해야한다. diffs 배열이 작으면 그냥 1부터 시작하려했는데, diffs 배열이 꽤나 큰 것을 보고 무작위는 시간초과가 날 것이라고 판단했다. 그래서 바로 binary search가 떠올랐기에 구현을 하였다.

def solution(diffs, times, limit):
    right_level, left_level = min(diffs), max(diffs)
    max_level = left_level
    answers = max_level + 1

    while right_level < left_level:
        cur_level = (right_level + left_level) // 2
        if answers != max_level + 1 and cur_level == answers:
            break

        myTime = 0
        time_prev = 0
        for diff, time_cur in zip(diffs, times):
            if diff <= cur_level:
                myTime += time_cur
            else:
                n = diff - cur_level
                total_time = time_cur + time_prev
                myTime += n * total_time + time_cur
            time_prev = time_cur

        if myTime <= limit:
            answers = min(answers, cur_level)

        if myTime > limit:
            right_level = cur_level
        else:
            left_level = cur_level + 1

    return answers

 

 

 

▶ 실패다.시간초과 2개와 오답 1개이다.

▶ 시간초과부터 해결하고자 한다. 이를 해결하기 위해, 이분 탐색 내에서 diffs와 times에 대해서 for문으로 시간 계산 하는 중 limit보다 크면 더 계산할 것 없이 반복문을 빠져나오는 코드를 추가하였다.

def solution(diffs, times, limit):
    right_level, left_level = min(diffs), max(diffs)
    max_level = left_level
    answers = max_level + 1

    while right_level < left_level:
        cur_level = (right_level + left_level) // 2
        if answers != max_level + 1 and cur_level == answers:
            break

        myTime = 0
        time_prev = 0
        for diff, time_cur in zip(diffs, times):
            if diff <= cur_level:
                myTime += time_cur
            else:
                n = diff - cur_level
                total_time = time_cur + time_prev
                myTime += n * total_time + time_cur
            time_prev = time_cur
            if myTime > limit:
                break

        if myTime <= limit:
            answers = min(answers, cur_level)

        if myTime > limit:
            right_level = cur_level
        else:
            left_level = cur_level + 1

    return answers

 

 

▶ 역시 실패다. 기타 테스트 케이스에 대해서는 소요 시간이 많이 줄어들었지만, 여전히 테스트케이스 7,20은 시간초과다.

▶ 시간초과부터 해결해야하기에 놓친 부분이 있는지 문제를 다시 보았다. diffs 배열의 값은 100,000 이하이다. cur_level은 diffs 배열 내 최대 최소가 범위이다.diffs 배열 최대 길이가 300,000이다. 위 코드에서 right_level과 left_level을 정의할 때, 초기 값을 min(diffs), max(diffs)로 설정하였다. diffs 배열이 최대 길이가 된다면으로 가정하면 이 부분이 시간 초과의 원인일 것이라고 생각하였다.

def solution(diffs, times, limit):
    right_level, left_level = 0, 100001
    answers = 100002

    while right_level <= left_level:
        cur_level = (right_level + left_level) // 2
        if answers == cur_level:
            break

        myTime = 0
        time_prev = 0
        for diff, time_cur in zip(diffs, times):
            if diff <= cur_level:
                myTime += time_cur
            else:
                n = diff - cur_level
                total_time = time_cur + time_prev
                myTime += (n * total_time + time_cur)
            time_prev = time_cur
            if myTime >= limit:
                break

        if myTime <= limit:
            answers = min(answers, cur_level)

        if myTime > limit:
            right_level = cur_level
        else:
            left_level = cur_level + 1

    return answers

 

 

▶ 성공이다! min, max함수가 긴 시간의 제일 큰 원인인걸 알면서 해당 부분부터 체크했어야했었다. 앞으로는 이렇게 배열이 길거나 하는 문제에서는 min, max함수를 섣불리 사용하지 말아야 겠다.

---

>> 위 내용은 필자가 코딩테스트 문제를 푼 코드입니다.

>> 부족한 점이 많을 수 있기에 잘못된 내용이나 궁금한 사항이 있으면 댓글 달아주시기 바랍니다.

>> 긴 글 읽어주셔서 감사합니다.