프로그래머스. 외벽점검

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

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

 

순열을 이용해 모든 경우의수를 구하는 문제였는데 

문제가 좀 햇갈리는게 문제에서는 반시계 방향을 언급하는데 사실 반시계 방향으로 돌 필요는 없다.

생각해보면 범위가 원형이므로 1에서 시작해서 +3 해서 4를 가는것이나 

4에서 시작해서 -3해서 1로 가는것이나 동일하다.

또한 예제에서 소수점 범위인 4.5미터에서 출발하는게 나오는데 weak에서 주어지는 숫자는 정수이므로 소수점에서 출발할 일도 없다.

포함범위가 원형이라 애를 먹다가 다른 분들의 코드를 봤다.

먼저 원형범위의 탐색을 위해 weak 배열의 크기를 늘리는 방법이 있었다.

weak 배열이 {1, 5, 6, 10} 이고, n = 12라면 

weak 배열의 각 원소에 12를 더한 값을 뒤에 푸쉬해주면

{1, 5, 16, 10, 13, 17, 18, 22} 이 된다.

 

이렇게 배열을 만들면 문제가 훨씬 풀기 쉬워진다.

모든 외벽을 탐색하는것은 새로 만들어진 weak 배열에서 인접한  w개 (기존 weak 배열의 크기, 즉 탐색해야할 외벽의수)를 방문하는 것과 같다. 

 

예를들어 1,5,16,10 을 방문해도 모두 방문한것이고,

5,16,10,13(1) 이렇게 방문해도 모두 방문한것 이라는 것을 알 수 있다.

 

여기까지 하면 이제 인원을 보내는 순서를 순열로 만들어서 모든 경우를 따져보면 된다. 

 

 

상당히 어려웠던 문제다..

몇일 지난 후 다시 풀어봐야겠다.