프로그래머스 - 퍼즐 게임 챌린지 (그런데 OOP를 곁들인)

이 글의 풀이는 효율보다는 객체 지향적 코드 작성에 의의를 두고 작성한 풀이입니다.
실제 업무에서 유지보수 및 개선을 염두하는 느낌으로 작성했습니다.
그리고 문제에서 보장한 입력 조건에 대해선 검증을 하지 않습니다.
질문과 피드백은 언제나 환영합니다!

문제: 퍼즐 게임 챌린지

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/340212
(문제는 간단한 참고용으로 복붙만 했습니다. 문제를 안보셨다면 링크타고 가독성좋은 곳에서 보시는걸 추천합니다)

---

문제 설명

당신은 순서대로 n개의 퍼즐을 제한 시간 내에 풀어야 하는 퍼즐 게임을 하고 있습니다. 각 퍼즐은 난이도와 소요 시간이 정해져 있습니다. 당신의 숙련도에 따라 퍼즐을 풀 때 틀리는 횟수가 바뀌게 됩니다. 현재 퍼즐의 난이도를 diff, 현재 퍼즐의 소요 시간을 time_cur, 이전 퍼즐의 소요 시간을 time_prev, 당신의 숙련도를 level이라 하면, 게임은 다음과 같이 진행됩니다.

diff ≤ level이면 퍼즐을 틀리지 않고 time_cur만큼의 시간을 사용하여 해결합니다.
diff > level이면, 퍼즐을 총 diff - level번 틀립니다. 퍼즐을 틀릴 때마다, time_cur만큼의 시간을 사용하며, 추가로 time_prev만큼의 시간을 사용해 이전 퍼즐을 다시 풀고 와야 합니다. 이전 퍼즐을 다시 풀 때는 이전 퍼즐의 난이도에 상관없이 틀리지 않습니다. diff - level번 틀린 이후에 다시 퍼즐을 풀면 time_cur만큼의 시간을 사용하여 퍼즐을 해결합니다.
예를 들어 diff = 3, time_cur = 2, time_prev = 4인 경우, level에 따라 퍼즐을 푸는데 걸리는 시간은 다음과 같습니다.

level = 1이면, 퍼즐을 3 - 1 = 2번 틀립니다. 한 번 틀릴 때마다 2 + 4 = 6의 시간을 사용하고, 다시 퍼즐을 푸는 데 2의 시간을 사용하므로 총 6 × 2 + 2 = 14의 시간을 사용하게 됩니다.
level = 2이면, 퍼즐을 3 - 2 = 1번 틀리므로, 6 + 2 = 8의 시간을 사용하게 됩니다.
level ≥ 3이면 퍼즐을 틀리지 않으며, 2의 시간을 사용하게 됩니다.
퍼즐 게임에는 전체 제한 시간 limit가 정해져 있습니다. 제한 시간 내에 퍼즐을 모두 해결하기 위한 숙련도의 최솟값을 구하려고 합니다. 난이도, 소요 시간은 모두 양의 정수며, 숙련도도 양의 정수여야 합니다.

퍼즐의 난이도를 순서대로 담은 1차원 정수 배열 diffs, 퍼즐의 소요 시간을 순서대로 담은 1차원 정수 배열 times, 전체 제한 시간 limit이 매개변수로 주어집니다. 제한 시간 내에 퍼즐을 모두 해결하기 위한 숙련도의 최솟값을 정수로 return 하도록 solution 함수를 완성해 주세요.

제한사항

1 ≤ diffs의 길이 = times의 길이 = n ≤ 300,000
diffs[i]는 i번째 퍼즐의 난이도, times[i]는 i번째 퍼즐의 소요 시간입니다.
diffs[0] = 1
1 ≤ diffs[i] ≤ 100,000
1 ≤ times[i] ≤ 10,000
1 ≤ limit ≤ 1015
제한 시간 내에 퍼즐을 모두 해결할 수 있는 경우만 입력으로 주어집니다.

---

Code

from typing import List


class Puzzle:
    
    def __init__(self, diff: int, time_cur: int):
        self.diff = diff
        self.solving_time = time_cur

        
class Player:
    
    def find_best_level(self, puzzles: List[Puzzle], limit: int) -> int:
        min_diff, max_diff = 0, max(p.diff for p in puzzles)
        level = (max_diff + min_diff + 1) // 2
        prev_level = -1
    
        while prev_level != level:
            solve_times = self.solve_puzzles(puzzles, level)
            if solve_times > limit:
                min_diff = level
            else:
                max_diff = level

            prev_level = level
            level = value = (max_diff + min_diff + 1) // 2
        
        return level

    def solve_puzzles(self, puzzles: List[Puzzle], level) -> int:
        def solve_time(_cur_p, _prev_p):
            return (
                _cur_p.solving_time
                + max(_cur_p.diff - level, 0) * (_cur_p.solving_time + _prev_p.solving_time)
            )
            
        solve_times = puzzles[0].solving_time
        for p_idx in range(1, len(puzzles)):
            cur_p, prev_p = puzzles[p_idx], puzzles[p_idx-1]
            solve_times += solve_time(cur_p, prev_p)
        
        return solve_times
        

def solution(diffs, times, limit):
    puzzles = [Puzzle(d, t) for d, t in zip(diffs, times)]
    player = Player()
            
    return player.find_best_level(puzzles, limit)

코드 설명

플레이어와 퍼즐 두 객체를 정의했습니다.
퍼즐 객체는 퍼즐에 대한 정보를 가지고 있습니다. 퍼즐을 푸는 주체는 플레이어이므로 퍼즐을 받아 해결하는건 플레이어의 역할로 둡니다. 그리고 퍼즐을 풀기 위해선 이전 퍼즐의 정보가 필요하기 때문에 퍼즐을 푸는 것을 퍼즐의 역할로 두기에는 애매해집니다.

class Puzzle:
    
    def __init__(self, diff: int, time_cur: int):
        self.diff = diff
        self.solving_time = time_cur

퍼즐 객체는 난이도(diff), 풀이 시간(solving_time) 두 가지의 정보만을 가지기 때문에 굳이 클래스로 두어야할까? 라는 생각을 예전에는 했었던 것 같습니다.
만약 딕셔너리나 리스트, 튜플로 정의한다면 해당 변수가 가진 정보를 보려면 정의한 단계를 다시 찾아가봐야 하는 불편함이 생깁니다.

# ex. list
puzzles = [(1, 2), (3, 2)]
puzzles[0][1]  # 1시간만 지나도 못알아볼 듯

# ex. dict
puzzles = [{"diff": 1, "solving_time": 3}, ...]
puzzles[0]["diff"]  # 첫 예시보다는 나아졌지만 어떤 키를 가지는지 확인하려면 정의 단계로 돌아가야함

플레이어 객체는 함수 외에 특별히 가지는 속성은 없기 때문에 클래스로 사용하지 않고 함수만 정의해서 사용해도 문제 풀이에는 이상이 없습니다. 하지만 추상화를 통해 객체 지향적으로 정의해두었으므로, 추후 퍼즐이 플레이어의 능력에 의존하게 된다면 수월한 개발을 기대할 수 있습니다.

class Player:
	def find_best_level(self, ...): ...
    
    def solve_puzzles(self, ...): ...
    
 # 만약 플레이어의 체력에 따라 영향을 받는 기능이 추가된다면
 class Player:
 	def __init__(self, hp):
    	self.hp = hp
       
    # 함수의 인자를 추가할 필요없이 self로 접근가능
	def find_best_level(self, ...): ...
    

물론 당장 구현할 필요가 없기 때문에 함수만 구현해도 됩니다. 다만 퍼즐을 푼다는 것은 플레이어의 능력에 의존할 가능성이 크기 때문에 개발 방향을 고려한다면 플레이어로 추상화 해두는 것이 개인적으로 좋아보입니다.

TODO

• 현재 퍼즐 객체의 풀이시간이 이전 퍼즐 객체에 의존성이 있음
  • 만약 퍼즐 객체들간 관계가 복잡해지기 시작한다면 Puzzles 객체를 통해 퍼즐리스트를 관리하는 방향이 필요해보임
• best_level의 의미가 불명확. 베스트의 기준을 담을 수 있는 구체적인 함수명이나 주석이 필요해보임
• find_best_level 내의 while문(이분탐색 알고리즘) 부분은 분리 가능성이 보임.

고민사항

• diff, times 길이가 최대 300,000 이라는 점에서 알고리즘 고려는 필수였다.
• find_best_level, solve_puzzles 함수를 좀 더 작은 단위로 쪼갤 수 있을지 생각을 꽤 했다.
  • 이전 퍼즐과 현재 퍼즐을 푸는 함수를 내부 함수로 둘지 인스턴스 함수로 둘지 고민했는데 함수가 복잡하지 않다는 점(테스트 불필요)과 다른 곳에서는 사용하지 않을 가능성이 크다는 점에서 내부 함수로 두었다.

---