[prgrammers / kakao] 외벽 점검 (Java)

문제

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

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

원형으로 되어있는 벽에 취약지점이 있다.

"스카피"는 원형으로 되어있는 벽의 취약지점에 친구들을 투입해서, 취약지점을 수리하려고 한다.

(단, 친구들은 각자 지정된 거리만 이동할 수 있다.)

 

이때, 친구들을 최소몇명 투입해야 외벽을 모두 수리할 수 있는지 찾는 문제다.

---

풀이

백 트래킹에 그리디로 푸는 문제다.

 

weak의 길이가 최대 15, dist의 거리가 8이므로, 최악의 경우

15 * 14 * 13 * ... * 10 * 9 * 8 만큼의 반복으로 답을 구할 수 있다. (약 2~3억번 반복)

(백준의 경우 문제당 시간제한이 걸려있는데, 프로그래머스에는 시간제한이 없어서...이런 상황에서 완탐이 가능한지 안되는지 햇갈린다... 내가 못찾는건가?)

 

논리 

1. 탐색가능한 모든 경우의 수를 고려한다. (백 트래킹으로 구현)
2. 친구의 투입 순서를 정할때, 더 많은 거리를 이동할 수 있는 친구를 항상 먼저 투입해도 손해보지않는다. (그리디)

위 논리를 코드로 그대로 구현하면 된다.

 

또, 꿀팁이 있는데... 이 문제는 시계 반대방향으로 탐색하나 시계방향으로 탐색하나 결과는 같다. 외벽의 길이가 12, 취약지점이 [1, 2, 3, 9, 10] 일때, 최소 거리는 3에서 시계 반대방향으로 9까지 탐색해주는 것 이다. 이는 9에서 시계방향으로 3까지 탐색하는것과 같은 말이다. 우리는 어차피 모든 경우를 전부 고려해줄것 이므로, 시계반대방향이던 시계방향이던 상관없이 탐색해주면 된다. (어차피 모든 경우가 고려됨)

 

문제를 풀때 주의해야할 점이 있었는데, "중복 수리된 벽을 미수리"로 바꾸는 오류다. (6번 11번이 이거 저격인듯?)

자세한 내용은 다음 링크를 참고하자 (아래 링크도 내가 작성한 글인데, 두번 설명하기 싫어서 링크로 남긴다)

https://programmers.co.kr/questions/30340

프로그래머스

 

주요 소스코드

workers에는 투입 가능한 친구들이 들어가며, 이 친구들을 갖고 백 트래킹을 진행 했을때, 수리 가능한지 구하는 함수이다.

    private boolean isRepairable(int size, int idx, int[] repaired, int[] weak, List<Integer> workers){
        if(idx == workers.size()) return this.isAllRepaired(repaired);
        boolean repairResult = false;
        for(int i = 0; i < weak.length; i++){
            if(repaired[i] > 0) continue;
            this.repair(size, workers.get(idx), i, repaired, weak);
            repairResult = this.isRepairable(size, idx+1, repaired, weak, workers);
            if(repairResult) return repairResult;
            this.unRepair(size, workers.get(idx), i, repaired, weak);
        }
        return repairResult;
    }

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/%5Bprogrammers%20kakao%5D%20%EC%99%B8%EB%B2%BD%EC%A0%90%EA%B2%80/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃