https://programmers.co.kr/learn/courses/30/lessons/60062
코딩테스트 연습 - 외벽 점검 | 프로그래머스
레스토랑을 운영하고 있는 스카피는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하는 도중에 주기적으로 외벽의 상태를 점검해야 할 필요가 있습니다. 레스토랑의 구조는 완전히 동그란 모양이고 외벽의 총 둘레는 n미터이며, 외벽의 몇몇 지점은 추위가 심할 경우 손상될 수도 있는 취약한 지점들이 있습니다. 따라서 내부 공사 도중에도 외벽의 취약 지점들이 손상되지 않
programmers.co.kr
어디서부터 어떻게 손대야 할지 감도 안 와서 어려웠던 문제.
검색해서 알아봐도 풀이방법이 참 다양하다. DFS, Brute Force, DP 등등
최대한 내가 이해한 방향으로 풀어보자면
1. 시계 - 반시계 문제는 배열을 두 배 늘려서 해결한다.
예컨대 위 사례에서 "4에서 출발해 반시계 방향으로 7만큼 돌면 9에 도착한다"는 건,
"9에서 출발해 시계 방향으로 7만큼 돌면 4에 도착한다" 와 같은 말이다.
문제에서 외벽 길이는 12였으므로, 9에서 출발해 4에 도착한다는 건, 9에서 7만큼 이동한 16이 4와 같다는 뜻이다.
따라서 위 사례의 경우 [1,3,4,8,9,10]에 "각 원소 + 외벽길이"를 붙여준다.
그러면 [1,3,4,8,9,10, 12 + 1, 12 + 3, 12 + 4, 12 + 8, 12 + 9, 12+ 10]이 되는데,
외벽 검사 출발할 지점을 1, 3, 4, 8, 9, 10 중 하나로 선택하면 시계 / 반시계 문제는 해결된다.
2. 두 배 늘린 배열에서, 외벽 검사를 시작할 지점부터 len(weak) 만큼의 원소를 탐색해야 한다.
3. dist에 있는 친구 배열도 모든 경우의 수를 따져야 한다. permutations로 모든 경우의 수를 만들어준다.
4. 탐색한다.
'프로그래밍 > 코딩테스트 문제풀이' 카테고리의 다른 글
| [Python] 백준 12100. 2048(Easy) (1) | 2020.02.27 |
|---|---|
| [Python] 백준 1325. 효율적인 해킹 (0) | 2020.02.26 |
| [Python] 백준 11403. 경로 찾기 (0) | 2020.02.24 |
| [Python] 백준 17406. 배열 돌리기 4 (0) | 2020.02.18 |
| [Python] 프로그래머스. 카드 게임 (Level 4) (0) | 2020.02.17 |