[프로그래머스] 외벽 점검 / 2020 KAKAO BLIND RECRUITMENT - JAVA

🖇️ 문제 링크

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

레스토랑을 운영하고 있는 "스카피" 는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하는 도중에 주기적으로 외벽의 상태를 점검해야 할 필요가 있습니다. 레스토랑의 구조는 완전히 동그란 모양이고 외벽의 총 둘레는 n미터이며, 외벽의 몇몇 지점은 추위가 심할 경우 손상될 수도 있는 취약한 지점들 이 있습니다.

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

 

---

📝 문제 분석

레스토랑의 구조가 원형이기 때문에 끝과 처음이 연결되어 있는 구조입니다.

이것을 선형으로 만들어주기 위해 weak = [1, 5, 6, 10]라면 linearWeak = [1, 5, 6, 10, 1 + n, 5 + n, 6 + n, 10 + n]의 형태로 만들어줍니다.

weak의 길이를 wlen이라고 할 때

linearWeak의 배열에서 친구들을 배치시켜 연속된 wlen개의 취약지점을 커버할 수 있는 최소 친구의 수가 정답입니다.

 

모든 경우를 시도해보기 위해, 친구들의 순열을 모두 구해서 배치합니다.

public void solve(int[] linearWeak, int[] dist) {
    for(int i = 0; i < wlen; i++) {
       	int s = linearWeak[i];
        int e = linearWeak[i + wlen - 1];
        
        for(int j = 1; j <= dlen; j++) {
          	s += pick[j - 1];
            if(s >= e) {
	        			ans = Math.min(ans, j); 
                break;
            }
            s = linearWeak[upperBound(linearWeak, s)];
        }
    }
}

linearWeak은 오름차순으로 되어 있기 때문에, s에서 친구들을 배치시키기 시작하여 e에 도달한다면 성공입니다. 배치하는 중간에 다음 칸으로 배치시키기 위하여 s보다 큰 최소의 인덱스를 구해줍니다.

 

 

---

⌨️ 코드

class Solution {
    int[] linearWeak, pick;
    boolean[] chk;
    int wlen, dlen, ans = (int)1e9;
    
    public int solution(int n, int[] weak, int[] dist) {
        wlen = weak.length;
        dlen = dist.length;
    	linearWeak = new int[wlen * 2];
        pick = new int[dlen];
        chk = new boolean[dlen];
        
        for(int i = 0; i < wlen; i++) {
            linearWeak[i] = weak[i];
            linearWeak[wlen + i] = weak[i] + n;
        }
        
       	perm(0, linearWeak, dist);
        return (ans == (int)1e9) ? -1 : ans;
    }
    
    public void solve(int[] linearWeak, int[] dist) {
        for(int i = 0; i < wlen; i++) {
           	int s = linearWeak[i];
            int e = linearWeak[i + wlen - 1];
            
            for(int j = 1; j <= dlen; j++) {
	            	s += pick[j - 1];
                if(s >= e) {
			        			ans = Math.min(ans, j); 
                    break;
                }
                s = linearWeak[upperBound(linearWeak, s)];
            }
        }
    }
    
    public int upperBound(int[] linearWeak, int s) {
        int lo = 0, hi = wlen * 2;
        while(lo < hi) {
            int mid = (lo + hi) / 2;
           	if(linearWeak[mid] > s)
                hi = mid
            else
                lo = mid + 1
        }
        return hi;
    }
    
    public void perm(int cnt, int[] linearWeak, int[] dist) {
        if(cnt == dlen) {
           	solve(linearWeak, dist);
            return;
        }
        
        for(int i = 0; i < dlen; i++) {
            if(!chk[i]) {
                chk[i] = true;
                pick[cnt] = dist[i];
                perm(cnt + 1, linearWeak, dist);
                chk[i] = false;
            }
        }
    }
}

 

 

 

 

Uploaded by Notion2Tistory v1.1.0