231110 - 호텔방배정(리스트 시간 초과 -> dict 재귀 활용), DP(계단 오르기 문제와 유사)

[robert-min]

호텔방배정

• https://school.programmers.co.kr/learn/courses/30/lessons/64063
• 풀이
  • 일반적으로 풀 경우 정확성은 맞지만, 효율성 해결 불가
  • 그 이유는 리스트로 비교하는 과정에서 많은 시간이 낭비되기 때문
  • 이를 해결하기 위해서는 set, dict 자료구조로 결과를 찾아야 함.
  • 핵심은 빈방을 사용한 후 해당 방의 value를 다음 방으로 설정해놓음 => 이렇게 할 경우 빈방이 찾을 때까지 재귀함수가 반복되기 때문에 효율적

import sys
sys.setrecursionlimit(10000000) # 설정해주지 않으면 재귀가 많이 일어나면서 런타임에러 등이 나타날 수 있다.

def findEmptyRoom(number, rooms):
    if number not in rooms:
        # 방문한 방의 빈 방을 value에 저장
        rooms[number] = number + 1
        return number

    # 재귀가 일어 났을 때는 number에 값이 들어가 있기 때문에 그대로 반환
    empty = findEmptyRoom(rooms[number], rooms)
    rooms[number] = empty + 1
    return empty

def solution(k, room_number):
    answer = []
    rooms = dict() # 몇번 방이 비어있는지 체크하는 딕셔너리

    # 이 문제의 핵심은 list로 했을 경우 시간 초과 발생, dict으로 비교
    for number in room_number:
        emptyRoom = findEmptyRoom(number, rooms)
        answer.append(emptyRoom)

    return answer

[robert-min]

도둑질 - DP(계단 오르기 문제와 유사)

• https://school.programmers.co.kr/learn/courses/30/lessons/42897#
• 풀이
  • DP 점화식의 경우 문제 상에 금방 볼 수 있음
  • 다만, 첫집과 마지막 집이 붙어있는 경우를 생각해야 함
  • 첫집을 훔치는 경우와 훔치지 않는 경우를 분리해서 값을 찾아야 함

def solution(money):
    """
    Return 도둑이 훔칠 수 있는 최대값
    - 집은 둥근 형태로 배치 => 첫 집과 마지막 집은 연결 됨.
    - dp : 그 집에서 털 수 있는 최대
        - 현재 집 X => 이전 집 dp[i-1]
        - 현재 진 O => 이전전 집 dp[i-2] + 현재 집 money[i]
    """
    # 첫 집을 무조건 터는 경우(마지막 집X)
    dp1 = [0] * len(money)
    dp1[0] = money[0]
    dp1[1] = max(money[0], money[1])

    for i in range(2, len(money)-1): 
        dp1[i] = max(dp1[i-1], money[i]+dp1[i-2])

    # 마지막 집을 무조건 터는 경우(첫 집 X)
    dp2 = [0] * len(money)
    dp2[0] = 0
    dp2[1] = money[1]

    for i in range(2, len(money)): 
        dp2[i] = max(dp2[i-1], money[i]+dp2[i-2])

    # 두 경우 중 최대
    return max(max(dp1), max(dp2))