코딩 테스트/프로그래머스
외벽 점검
땅어
2021. 7. 2. 17:17
728x90
300x250
문제
https://programmers.co.kr/learn/courses/30/lessons/60062
코딩테스트 연습 - 외벽 점검
레스토랑을 운영하고 있는 "스카피"는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하
programmers.co.kr
나의 풀이
브루트 포스 문제이다. 생각보다 어려웠던 것 같다. 중요하게 고려해야 할 것은 크게 두 가지이다.
1. 외벽은 원형으로 이루어져 있는데 주어진 weak 리스트가 그것을 반영하지 못한다. -> weak 리스트 배열의 길이를 2배로 늘려서 해결. 예컨대, weak = [1,5,6,10], n=12라면 weak_point = [1,5,6,10,13,17,18,22]로 해서 이 중에서 원래 weak의 원소 갯수였던 4개의 연속된 지점을 선택하는 문제로 바꿀 수 있다.
2. 같은 상황이라도 dist 배열의 친구들을 어떠한 위치에 어떠한 순서로 넣을지에 따라 결과가 달라진다. -> 순열 사용
코드
from itertools import permutations
def solution(n, weak, dist):
INF = 987654321
answer = INF
weak_point = weak + [ w + n for w in weak ]
L = len(weak)
# 시작점
for (idx, start) in enumerate(weak):
# 가능한 모든 케이스의 순열
for p in permutations(dist):
count = 1
pos = start
for d in p:
pos += d
if pos >= weak_point[idx + L - 1]:
answer = min(answer, count)
break
else:
pos = [w for w in weak_point if w > pos][0]
count += 1
return -1 if answer == INF else answer
728x90
300x250