링크

도둑질

난이도

  • 프로그래머스 난이도 4만큼 어렵다.
    • python에서 시스템적인 문제도 알아야한다. (뭐야이게…)
    • python재귀의 한계가 존재하는것을 알아야한다.
      • setrecursionlimit의 존재를 알게되었다.

문제요약

  • 호텔 방을 순차적으로 배정하는데 이미 배정되어있다면, 해당 호텔방보다 높은 호텔방에서 제일 낮은방을 배정해준다.
    • 1 1 3이면 1 2 3으로 배정이 된다.

접근

  1. check라는 dict를 선언하고, 방번호: 다음방번호로 지정
    • i에 대해 check[i]가 없으면 해당 i + 1을 넣어주고, answer에 i를 넣는다.
    • 이후 i를 value로 가진것들 i+1로, i+1로 시작하는것들은 i+2로 이런업데이트작업을 수행 - 좋은 방식이라 생각했지만 효율성실패, 정확성실패
    • 중간에 잘못 계산된게 있고 너무 계산할게 많아졌다.
  2. 집합이용
    • 빈방들을 집합으로 선언 check = set([1,2,…])
    • i에 대해 i in check이면 check에서 삭제, answer에 넣기
    • i in check가 아니면, 집합을 반목문으로 i보다 커졌을때의 값을 answer에 넣고, check에서 삭제
    • 이것은 정확성만 성공
  3. 단순반복문
    • 1부터 k까지 반복으로 1을 예시로 처음 1은 넘기고 다음 1을 만날때마다 +1을 중첩으로 넣어준다.
    • [1 1 3 2 1 5]일때 처음 1부터하면 [1 2 3 2 2 5]가 되고 2는 [1 2 3 3 4 5]가 되고, 3은 [1 2 3 4 4 5]가되고 이를 이중반복문으로 - 당연히 정확성만 성공
  4. 1번풀이 개량
    • 너무 계산할것이 많은것을 단순히 노드형식으로 변경
    • check는 그저 방번호: 다음방번호라는 규칙을 고정해서 진행
    • check에 key로 방번호 i 가 존재안하면 빈방, answer에 방번호 i 넣기, check[i] = i+1
    • check에 key로 방번호 i가 존재할때
    • k = check[i]-> k = check[k]로 key가 존재안할때까지 반복하면서 빈방을 찾는다. - 정확성은 성공(1에서 실수한것을 제대로 풀음) 하지만 효율성은 실패
    • check을 반복적으로 확인하는것에서 최악으로 모든 check를 돌아야하므로 시간초과가 걸리는것을 확인
    • 방번호: 다음방번호를 방번호:다음빈방번호로 바로 도출되게 수정해야함

간단 알고리즘

  • check는 dict로 선언 방번호: 다음 빈방 번호
  • 확인할 방번호 i에 대해
    • check[i]가 없을때
      • check[i] = i+1로 해주고 종료
    • check[i]가 존재
      • 재귀적으로 check[i+1]로 넘어가면서 빈방 k 찾기
      • 찾았으면 다시 돌아오면서 지금까지 들렀단 방들에게 다음 빈방인 k+1로 업데이트 해준다.
  • 주위사항!
    • python은 재귀하는 한계가 정해져있다고한다.
    • 이걸 안하면 효율성 4번은 런타임 에러가 난다. 
      •  import sys
 sys.setrecursionlimit(200000) # 한계를 늘려준다.

후기

  • python에 호출 제한이 있는것을 처음확인
  • 일단 저 재귀호출 제할 해제부터 하고 시작해야할듯하다.
  • 문제 접근할때 초반에 접근은 좋았지만, 세부적인 문제풀이가 너무 복잡하고 계산량도 많게 하다보니 정확도와 효율성은 다 틀렸다.
    • 초반 접근을 좀더 생각해서 개량했으면 좀더 빨리 풀었을듯