[프로그래머스] 카카오 블라인드 리크루트 2020 - 외벽 점검 (Java)

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

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

문제 설명

레스토랑을 운영하고 있는 스카피는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하는 도중에 주기적으로 외벽의 상태를 점검해야 할 필요가 있습니다.

레스토랑의 구조는 완전히 동그란 모양이고 외벽의 총 둘레는 n미터이며, 외벽의 몇몇 지점은 추위가 심할 경우 손상될 수도 있는 취약한 지점들이 있습니다. 따라서 내부 공사 도중에도 외벽의 취약 지점들이 손상되지 않았는 지, 주기적으로 친구들을 보내서 점검을 하기로 했습니다. 다만, 빠른 공사 진행을 위해 점검 시간을 1시간으로 제한했습니다. 친구들이 1시간 동안 이동할 수 있는 거리는 제각각이기 때문에, 최소한의 친구들을 투입해 취약 지점을 점검하고 나머지 친구들은 내부 공사를 돕도록 하려고 합니다. 편의 상 레스토랑의 정북 방향 지점을 0으로 나타내며, 취약 지점의 위치는 정북 방향 지점으로부터 시계 방향으로 떨어진 거리로 나타냅니다. 또, 친구들은 출발 지점부터 시계, 혹은 반시계 방향으로 외벽을 따라서만 이동합니다.

외벽의 길이 n, 취약 지점의 위치가 담긴 배열 weak, 각 친구가 1시간 동안 이동할 수 있는 거리가 담긴 배열 dist가 매개변수로 주어질 때, 취약 지점을 점검하기 위해 보내야 하는 친구 수의 최소값을 return 하도록 solution 함수를 완성해주세요.

제한사항

• n은 1 이상 200 이하인 자연수입니다.
• weak의 길이는 1 이상 15 이하입니다.
  • 서로 다른 두 취약점의 위치가 같은 경우는 주어지지 않습니다.
  • 취약 지점의 위치는 오름차순으로 정렬되어 주어집니다.
  • weak의 원소는 0 이상 n - 1 이하인 정수입니다.
• dist의 길이는 1 이상 8 이하입니다.
  • dist의 원소는 1 이상 100 이하인 자연수입니다.
• 친구들을 모두 투입해도 취약 지점을 전부 점검할 수 없는 경우에는 -1을 return 해주세요.

입출력 예

n	weak	dist	result
12	[1, 5, 6, 10]	[1, 2, 3, 4]	2
12	[1, 3, 4, 9, 10]	[3, 5, 7]	1

---

풀이

1. 원형으로 이루어진 외벽을 어떻게 탐색할 것인가?

: weak 배열을 확장하여 원형이 아닌 직선의 형태로 생각하여 접근한다. 탐색을 시작하는 취약 지점을 달리하여 경우를 생각해줘야 한다. 예를 들어 weak = [1, 5, 6, 10] 인 경우에 두 번째 원소부터 시작한다고 하면 [5, 6, 10, 1] 순으로 탐색이 되어야 한다. 가능한 경우의 배열을 모두 탐색해야하기 때문에 circleWeak라는 리스트를 만들어준다. 주어진 weak 다음에는 n + i를 넣어주면 된다. 위에 언급한 예를 고려하면 circleWeak = [1, 5, 6, 10, 13, 17, 18, 23] 이 된다. 탐색 시, 앞에서부터 차례로 weak의 length만큼만 가져다 탐색하면 된다.

 

2. 친구들을 어떤 순서로 보낼 것인가?

: 점검을 보낸 친구들의 순서에 의해 결과가 달라질 수 있다. 예를들어 외벽 간 거리가 5, 10이고 친구 두 명의 점검 가능 거리가 10, 9라고 하자. 9의 거리를 갈 수 있는 친구를 먼저 보내면 2명으로 해결이 가능하지만 10인 친구를 먼저 보내면 이 경우는 해결 불가능하다는 결론이 나버린다. 모든 경우의 배치 순서를 고려하여 탐색을 해야한다. 이 경우에 순열(dfs)로 순서를 배치 가능하다.

 

+) 어려웠던 점

: 친구들을 가능 거리가 높은 순으로 정렬을 하고 시도하면 모든 경우를 고려할 수 있다고 생각했지만 실수였다. 벽 사이의 거리가 오름차순인 경우에는 내림차순인 친구들로는 해결 불가능했다. 결국엔 친구들도 만들 수 있는 모든 순서에 대한 탐색이 이루어졌어야 했다.

 

코드

import java.util.LinkedList;
import java.util.List;

public class Solution {
    private static int result = Integer.MAX_VALUE;
    private int[] dist;
    private boolean[] visit;
    private LinkedList<Integer> circleWeak;
    private int weakSize;

    public int solution(int n, int[] weak, int[] dist) {
        int answer = 0;
        this.dist = dist;
        visit = new boolean[dist.length];
        weakSize = weak.length;
        circleWeak = new LinkedList<>();

        for (int i = 0; i < weakSize; i++) {
            circleWeak.add(weak[i]);
        }

        for (int i = 0; i < weakSize; i++) {
            circleWeak.add(weak[i] + n);
        }

        getPermutation(0, new LinkedList<>());


        if (result == Integer.MAX_VALUE) {
            answer = -1;
        } else {
            answer = result;
        }

        return answer;
    }

    private void getPermutation(int count, LinkedList<Integer> friends) {
        if (count == dist.length) {
            check(friends);
            return;
        }

        for (int i = 0; i < dist.length; i++) {
            if (!visit[i]) {
                visit[i] = true;
                friends.add(dist[i]);
                getPermutation(count + 1, friends);
                friends.removeLast();
                visit[i] = false;
            }
        }
    }

    private void check(List<Integer> friends) {

        for (int i = 0; i < weakSize; i++) {
            int index = 0;
            boolean mark = false;
            int start = circleWeak.get(i);

            for (int j = i; j < i + weakSize; j++) {
                if (friends.get(index) < (circleWeak.get(j) - start)) {
                    start = circleWeak.get(j);
                    index++;

                    if (index == friends.size()) {
                        mark = true;
                        break;
                    }
                }
            }

            if (!mark) {
                result = Math.min(result, index + 1);
            }
        }
    }
}

 

[참고]

https://uyoo-story.tistory.com/52