알고리즘) 카카오 블라인드 채용 2020, 외벽 점검

Kakao Blind Recruitment 2020

외벽 점검

프로그래머스

제한사항

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

 

풀이

너무 어렵게 접근해서 푸는데 너무 많은 시간이 소요됐다. 풀면서 실수한 부분을 살펴보면

첫째) 친구들을 모두 투입해도 점검을 못하면 -1을 리턴하는 부분을 놓쳤다.

둘째) 순열을 쓰지 않고 친구들의 정보가 담긴 Dist를 최대값부터 탐색과 최소값부터 탐색을 모두 해서 결과를 ArrayList에 두고 -1을 제외한 최소값을 반환했는데, 순차적으로 친구들이 탐색할 수 있는 경우가 아닌 뒤죽박죽 순서로 검사해야만 검사할 수 있는 경우가 있었다.

정도 문제점이 있었다.

 

오랜 시간동안 풀지 못해서 다른 분의 풀이를 참고했다. 링크

[프로그래머스] 2020 KAKAO BLIND RECRUITMENT 외벽 점검 (Java)

풀이 과정을 보면

1. 취약점 부분이 원형이기 때문에, weak[]의 길이 만큼 각각의 요소에 n을 더한 값을 추가하여 새로운 weakList를 만든다.

2. dist의 길이만큼 for문을 돌며 i 개의 순열을 만드는 함수를 호출한다.

3. 순열 결과로 나온 List를 검사하는 메소드에 넘겨 탐색이 가능한지 weakList를 탐색한다.

4. 가능하다면 전역변수로 설정한 boolean타입의 found에 true값을 넣고 for문을 돌고있는 개수 i 를 답에 넣고 모든 메소드를 종료한다.

 4.1 answer는 -1로 초기화해놨기 때문에(못찾는 경우) found 값이 true 일 때만 i 저장

5. 답을 반환

 

코드

import java.util.LinkedList;

public class OuterWall_2019 {
    final static int MIN_ANSWER = 1;
    static LinkedList<Integer> weakList;
    static boolean found;
    static int weakLen;

    public static void main(String[] args) {
//        int n =12;
//        int[] weak = {1,5,6,10};
//        int[] dist = {1,2,3,4};
//        int[] weak = {1, 3, 4, 9, 10};
//        int[] dist = {3, 5, 7};
//        int[] weak = {0,2,11};
//        int[] dist = {3};

        int n = 50;
//        int[] weak = {1, 5, 10, 16, 44, 47};
//        int[] dist = {3,4,6};
        int[] weak = {1, 5, 10, 16, 22, 25};
        int[] dist = {3,4,6};
        System.out.println(solution(n,weak,dist));
    }

    private static int solution(int n, int[] weak, int[] dist) {
        return n ==MIN_ANSWER || weak.length ==MIN_ANSWER ? MIN_ANSWER : findMinPersons(n, weak, dist);
    }

    private static LinkedList<Integer> getWeakList(int n, int[] weak) {    // n 은 2 이상
        weakLen = weak.length;
        LinkedList<Integer> result = new LinkedList<>();

        for(int num : weak) {
            result.offer(num);
        }
        for(int i=0; i<weakLen; i++) {
            result.offer(result.get(i)+n);
        }

        return result;
    }

    private static void permutation(int[] visit, int[] dist, LinkedList<Integer> result, int cnt) {
        if(found) {
            return;
        }
        if(cnt == 0) {  // 조합 완성
            findCase(result);
            return;
        }

        for(int i=0; i<dist.length; i++) {
            if(visit[i] ==0) {
                result.offer(dist[i]);
                visit[i] = 1;
                permutation(visit, dist, result, cnt-1);
                visit[i] =0;
                result.removeLast();
            }
        }
    }

    private static int findMinPersons(int n, int[] weak, int[] dist) {
        weakList = getWeakList(n, weak);
        found = false;
        int answer =-1;

        for(int i=1; i<=dist.length; i++) {
            permutation(new int[dist.length], dist, new LinkedList<>(), i);
            if(found) {
                answer = i;
                break;
            }
        }
        return answer;
    }

    private static void findCase(LinkedList<Integer> distList) {
        for(int idx = 0; idx < weakLen; idx++) {
            int distIdx = 0;
            int person = distList.get(distIdx);
            int prev = idx; // 이전 값
            boolean allDone = true;
            for (int i = idx; i < idx + weakLen; i++) {
                int diff = weakList.get(i) - weakList.get(prev);
                if (person - diff < 0) {    // 더이상 체크할 수 없으면
                    if (distIdx + 1 < distList.size()) {
                        person = distList.get(++distIdx);
                    } else {
                        allDone = false;
                        break;
                    }
                } else {    // 체크할 수 있으면
                    person -= diff;    // 거리만큼 빼줌
                }
                prev = i; // prev 옮기기
            }
            if (allDone) {  // 결과적으로 다 돌았다는거
                found = true;
                break;
            }
        }
    }
}