본문 바로가기
ALGORITHM/PROGRAMMERS

[PG/Python] 외벽 점검

by 안녕나는현서 2022. 1. 15.
728x90

📌 문제

https://programmers.co.kr/learn/courses/30/lessons/60062

 

코딩테스트 연습 - 외벽 점검

레스토랑을 운영하고 있는 "스카피"는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하

programmers.co.kr

 

📌 문제 접근 방법

  1. 완전탐색으로 풀이하였다.
  2. 시계방향, 반시계방향을 모두 고려해주기 위해서 weak리스트의 요소에 n을 더하여 추가해준다.
  3. weak리스트의 원래 원소들만을 출발점으로해서 원래 weak의 길이만큼 슬라이싱하여 queue를 만들어준다.
  4. dist를 순열을 사용하여 people에 저장하고 큐의 형태로 만들어준다.
  5. people의 0번째에 저장된 친구가 어디까지 갈 수 있는지 계산 후, 해당 거리만큼 queue에서 요소를 빼준다.
  6. queue의 요소 제거가 완료되었으면 친구는 외벽 점검이 끝났으므로, people에서 pop해준다.
  7. 만약 queue가 비었을 경우, 외벽 점검이 완료된 것이므로 answer값을 갱신해준다.

 

📌 코드

from itertools import permutations
from collections import deque

def solution(n, weak, dist):
    weak_len = len(weak)
    for i in range(weak_len):
        weak.append(weak[i]+n)
    
    answer = float('inf')
    for j in range(weak_len):
        for people in permutations(dist, len(dist)):
            queue = deque(weak[j:j+weak_len])
            people = deque(people)
            
            while queue and people:
                able = queue[0] + people[0]
                while queue and queue[0] <= able:
                    queue.popleft()
                    
                people.popleft()
                
                if not queue:
                    answer = min(answer, len(dist)-len(people))
    
    if answer == float('inf'):
        answer = -1

    return answer
728x90

'ALGORITHM > PROGRAMMERS' 카테고리의 다른 글

[PG/Python] 입국심사  (0) 2022.01.25
[PG/Python] 2 x n 타일링  (0) 2022.01.24
[PG/Python] 합승 택시 요금  (0) 2022.01.14
[PG/Python] 이중우선순위큐  (0) 2022.01.11
[PG/Python] 자물쇠와 열쇠  (0) 2022.01.10

댓글