Question

[문제해설 + 정답코드] 퍼즐 게임 챌린지 해설

오랜만에 프로그래머스 문제를 풀어보았습니다.
요즘 따라 문제의 지문이 너무 많아진 것 같은거는 기분탓일까요..?

허허.. 점점 코딩테스트가 아닌 국어독해 테스트를 보는 것 같은 느낌이 듭니다.

저도 국어는 어려워하기에, 이번 문제 사실 좀 어지러웠습니다.
각설하고 해설시작하겠습니당

문제에서 요구하는 것

레벨이 낮은 만큼 이 문제는 많이 친절합니다.
그래서, 문제 유형만 알았다면, 문제를 푸는 건 그리 어렵지 않습니다.
왜냐하면, 문제에 대한 설명 중에 여러 조건을 조합해서 다른 조건을 추출해야하는 지문이 없습니다.
명시적으로 다 나와 있으며, 이를 제대로 이해하고 코드로 구현하면 문제를 풀 수 있습니다.

문제에서는 총 3개의 변수를 주게 됩니다.

diffs => 문제를 풀기 위해 필요한 숙련도 배열
times => 문제를 풀기 위해 필요한 시간 배열 (diffs와 길이가 동일하고 같은 인덱스와 맵핑됨.)
limit => 문제를 풀기 위한 제한시간

diffs와 times는 현재 풀어야 할 문제 순서대로 배열 형태로 값이 들어있습니다.
무작위로 섞여 있지 않냐고 할 수 있지만,

퍼즐의 난이도를 순서대로 담은 1차원 정수 배열 diffs, 퍼즐의 소요 시간을 순서대로 담은 1차원 정수 배열 times

이 지문에 의해, 주어진 문제는 순서대로 담겨있기에, 순서대로 풀어야 함을 알 수 있습니다.

순서대로 주어지는 diffs와 times 배열은 서로 길이도 같고, 순서도 같습니다.
i가 0부터 diffs의 길이까지 순회한다고 하면,

diffs[i]에 대한 문제를 푸는데 times[i]만큼의 소요시간이 발생하구요,
이전 문제에 대한 퍼즐 풀이 시간은 times[i-1]이 됩니다.
물론 여기서 이전 문제에 대한 퍼즐 풀이 시간이 음수가 되지 않도록 조심해야 합니다.

그럼, 이런 의문이 발생할 수 있겠습니다.
아니, 1번 문제부터 풀지 못하면, 이전 시간은 어디서 가져와야 해요?
저도, 당연히 생각했구요, 좋은 질문 입니다.
문제의 제한 사항에,

diffs[0] = 1

이렇게, 1번 문제는 반드시 숙련도가 1로 들어온다고 명시되어있습니다.

그리고, 문제의 지문에서

난이도, 소요 시간은 모두 양의 정수며, 숙련도도 양의 정수여야 합니다.

숙련도는 양의 정수 여야 한다고, 명시하였습니다.
이런 관점에서, 숙련도는 항상 1부터 시작하게 되며, 1번 문제를 못 푸는 경우는 없습니다.
그런 고민은 안해도 되겠습니다.

이 정도면 의문은 풀렸구요, 결국 문제에서 원하는 것은,
제한시간 limit 내에서, 퍼즐을 아슬아슬 하게 풀 수 있는 최소의 숙련도를 구하라는 것입니다.

문제 유형

해당 문제는 아주 정석적인 '이분탐색' 유형의 문제입니다.

최소와 최대에 대한 범위가 아주 명확히 정해져 있고,
어떤 한 변수에 대해서 어떤 행위를 수행 하고, 그에 따라 결과가 변하고,
정답으로 원하는 값이 특정 행위를 경계선에서 수행할 수 있는 값을 도출하라고 했기 때문입니다.

2번에 대한 건 이분탐색에 대해서 선택사항입니다. 있을 수도 있고 없을 수도 있습니다.
보통 1번과 3번이 가장 기본적인 규칙이며, 문제를 더욱더 어렵기 하기 위해서 2번을 끼워넣는 방식으로
진행합니다.

해당 문제는 1, 2, 3번 에 대한 조건을 모두 만족하는 정석적인 이분탐색 문제입니다.
그리고, 알고리즘도 이분탐색 하나만 필요합니다.

보통 레벨3이상을 풀게 되면, 이분탐색을 검색의 효율성을 위해 도구 정도로 사용하는 문제도 많습니다.
메인이 아닌 것이죠.

이 문제는 메인으로 사용되는 문제이니, 문제의 난이도는 그렇게 어렵지 않습니다.

문제에 대한 풀이 흐름

이 문제를 쉽게 풀기 위해서는 함수를 적절히 나누는 것이 중요합니다.

왜냐하면, 문제 유형에서, 2번에 대한 조건이 추가된 이분탐색은, 값을 정하기 위해서,
어떤 행위라는 것을 좀 길게 해야 하는 경우가 존재합니다.

그래서 이 어떤 행위라는 것을 외부 함수로 빼놓는 것이 이 문제를 깔끔하게 풀 수 있습니다.
그래야 본질적인 이분 탐색을 적용하는 것이 편해집니다.

이 문제는 퍼즐에 관한 변수와, 현재 지정할 숙련도를 추가로 입력을 받아서,
현재 숙련도에서 문제를 풀 수 있는지 시뮬레이션을 수행하는 함수를 작성하면 좋습니다.

그리고, 메인인 solution함수에서는
이분탐색을 진행해주면 됩니다.

최소값은 문제에서 제시된 대로, 1로 지정하게 됩니다.
최대값은 diffs중 최댓값과 같게 되면, 모든 문제를 프리패스로 풀게 되므로 max(diffs)가 됩니다.

그리고, 전형적인 이분탐색 조건을 걸어서,
중간값을 구해주고,

시뮬레이션을 돌려 나온 결과를 확인해서,
high 또는 low를 업데이트하고,

최종적으로 low를 리턴합니다.

시뮬레이션을 돌려 나온 결과가 성공이면, 현재 위치보다 큰 값들은 어차피 전부 성공일겁니다.
그래서 high값을 현재 위치로 조정하여, high값을 제한합니다.

시뮬레이션을 돌려 나온 결과가 실패이면, 현재 위치보다 작은 값들은 어차피 전부 실패입니다.
그래서 low값을 현재 위치로 조정하여, low값을 제한합니다.

마무리

저는 이렇게, 문제를 분리해서 생각하는 걸 좋아합니다.
인간의 뇌를 너무 복잡한 것들이 머리에 들어오게 되면, 정리하기가 매우 어렵습니다.

하지만, 문제를 작은 단위로 쪼개고, 이를 각각 구현하고, 나중에 하나로 합칠 수 있다면,
복잡한 문제라도, 쉽게 풀 수 있습니다.
코드가 좀 길어지기는 하는데, 나중에 이상하게 작성하여 디버깅도 못하고, 원인도 몰라서 소요하는 시간보다
훨씬 낫습니다.

읽어주셔서 감사합니다.

코드도 첨부합니다.

작성중인 코드―solution.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
# 퍼즐을 주어진 level로 limit만큼의 제한시간 안에 풀 수 있는지 검증.
def solve_simulation(diffs, times, limit, level):

    # 퍼즐의 길이
    n = len(diffs)

    # 퍼즐을 푸는데 소비한 시간
    consumed_time = 0

    # 퍼즐을 순차적으로 순회하여, 문제를 풀고 있음.
    for i in range(n):

        diff = diffs[i]
        time_cur = times[i]
        time_prev = times[i-1]

        # 퍼즐을 틀리지 않은 경우
        if level >= diff:

            # 퍼즐은 푸는데 걸린 시간을 더해준다.
            consumed_time += time_cur

        else: # 퍼즐을 틀린 경우

            # 실패한 횟수 계산
            failed_solve = diff - level

            # 퍼즐을 푸는데 걸린 시간을 계산한다.
            solved_time = time_cur * failed_solve # 현재 문제를 도전한 시간을 더해준다.
            solved_time += time_prev * failed_solve # 이전 문제를 도전한 시간을 더해준다.
            solved_time += time_cur # 현재 문제를 풀 수 있는 시간을 더해준다.

            consumed_time += solved_time

        # 제한시간을 초과한 경우 False 리턴
        if consumed_time > limit:
            return False

    # 제한시간을 준수한 경우 True 리턴
    return True

def solution(diffs, times, limit):

    # 이분탐색의 최소/최대 범위를 산출한다.
    # 최소는 문제에 의해 반드시 1로 고정되어있다.
    # diffs의 최대 숙련도 이상이 되면, 한 번에 풀 수 있으므로, 가장 최고의 경우이다. 이보다 크면 의미가 없음.
    low = 1
    high = max(diffs)

    while low <= high:

        # 현재 범위의 중간 숙련도 값을 구해준다.
        mid_level = (low + high) // 2

        # 퍼즐 시뮬레이션을 돌려 결과를 산출한다.
        result = solve_simulation(diffs, times, limit, mid_level)

        # 결과가 성공적이었다면, 현재 값보다 상위의 값은 더 이상 볼가치가 없음.
        if result:
            high = mid_level - 1

        else: # 결과가 틀렸다면, 최소가 더 높아야 의미가 있음.
            low = mid_level + 1

    return low

Answer 1

좋은 글 감사합니다

저야말로 글 읽어주셔서 감사함다

전현서―2025.02.22 11:49

Answer 2

감사합니다 덕분에 쉽게 풀었습니다

Answer 3

좋은 해설 감사합니다 ~!

전현서

2024.12.8 12:06

[문제해설 + 정답코드] 퍼즐 게임 챌린지 해설

문제에서 요구하는 것

문제 유형

문제에 대한 풀이 흐름

마무리

작성중인 코드―solution.py

3 개의 답변

김민규

2025.2.21 23:55

전현서―2025.02.22 11:49

윤동훈

2025.2.25 11:08

yurrrri

2025.7.30 17:02

답변 쓰기

이 입력폼은 마크다운 문법을 지원합니다.