공부하고 기록하는, 경제학과 출신 개발자의 노트

프로그래밍/코딩테스트 문제풀이

[Python] 프로그래머스. 2020 카카오 recruit - 외벽 점검 (Level 3)

inspirit941 2020. 2. 25. 16:24

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. 탐색한다.