[프로그래머스(Programmers)][자바(java)] (Lv3) 외벽 점검

 

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

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

 

문제 요약

• 스카피가 친구들과 함께 1시간 동안 레스토랑 외벽을 점검하려고 하는데, 취약 지점을 점검하기 위해 보내야 하는 친구 수의 최소값을 return 하는 문제
  ( 외벽의 길이 n, 취약 지점의 위치가 담긴 배열 weak, 각 친구가 1시간 동안 이동할 수 있는 거리가 담긴 배열 dist가 매개변수로 주어짐 )
• 레스토랑의 구조는 완전히 동그란 모양이고, 총 둘레는 n미터 이다
• 편의 상 레스토랑의 정북 방향 지점을 0으로 나타내며,
  취약 지점의 위치는 정북 방향 지점으로부터 시계 방향으로 떨어진 거리로 나타냄.
  또, 친구들은 출발 지점부터 시계, 혹은 반시계 방향으로 외벽을 따라서만 이동함.

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

 

문제 풀이

*  완전 탐색

-  제한사항에서 원소들의 길이가 많이 크지 않으므로 완전 탐색 가능

-  외벽이 원형이므로 외벽을 직선으로 늘여놓고 볼 때, 각 취약점을 시작점으로 하여 취약점의 개수( nw : num of weak points )만큼의 취약점 배열( int ws[][] : weak points arr ) 생성

n	12
weak[]	{ 1, 5, 6, 10 }
ws[][]	{ { 1, 5, 6, 10 }, { 5, 6, 10, 13 }, { 6, 10, 13, 17 }, { 10, 13, 17, 18 } }

-  친구마다 1시간동안 이동할 수 있는 거리가 각각 다르고 취약점들 사이의 거리도 다르므로, 친구들을 선택하는 순서의 모든 경우의 수를 구하는( 순열 ) perm() 함수 작성

-  친구들을 선택하는 순서의 각각의 경우( int a[] )마다 ws[][]를 탐색하며 취약점을 점검하는 check() 함수 작성.
   한 친구( id : idx_distance )가 취약점을 점검하는 시작점과 끝점을 구함
   -  시작점( s ) : 취약점
   -  끝점( e ) : 시작점( s )에서부터 현재의 친구가 이동할 수 있는 거리( dist[a[id]] )를 더한 값
   다음 친구의 시작점은 현재 친구가 점검한 마지막 취약점의 다음 취약점이다.
   모든 취약점을 점검하고 나면 점검에 투입된 친구들의 명수( = id + 1 )를 구하고,
  점검 인원의 최솟값( fm : friends_min )을 갱신. 초기값은 친구들의 명수( nf : num of friend ) + 1로 함.

-  만약 모든 친구들이 투입 되었음에도 취약점을 모두 점검하지 못할 경우 -1 리턴, 그렇지 않으면 fm 리턴

public class Solution {
	
	int nn, nw, nf, d[], w[], ws[][], f, fm;
	
	public void perm( int k, int n, int m, int a[], boolean v[] ) {
		if( k == m ) {
			check( a );
			return;
		}
		for( int i = 0; i < n; i++ ) {	
			if( !v[i] ) {
				v[i] = true;
				a[k] = i;
				perm( k + 1, n, m, a, v );
				v[i] = false;
			}
		}
	}
	
	public void check( int a[] ) {
		int i, j, iw, id, s, e;  // iw : idx_weak, id : idx_distance
		for( i = 0; i < nw; i++ ) {
			iw = 0;
			id = 0;
			loop:
			while( iw < nw && id < nf ) {
				s = ws[i][iw];
				e = s + d[a[id]];
				for( j = iw+1; j < nw; j++ ) {
					if( ws[i][j] >= e ) {
						iw = j;
						if( ws[i][j] == e ) {
							if( j == nw-1 )
								break;
							iw++;
						}
						id++;
						continue loop;
					}	
				}
				f = id+1;
				fm = f < fm ? f : fm;
				break;
			}
		}
	}
	
	public void setWeak() {
		int iw, i, j;
		for( i = 0; i < nw; i++ ) {
			iw = 0;
			for( j = i; j < nw; j++ ) 
				ws[i][iw++] = w[j];
			for( j = 0; j < i; j++ )
				ws[i][iw++] = w[j] + nn;
		}
	}
	
	public static int solution(int n, int[] weak, int[] dist) {
		nn = n;				// length
		nw = weak.length;  	// num of weak points
		nf = dist.length;  	// num of friends
		d = dist;
		w = weak;
		ws = new int[nw][nw];	// weak points arr
		setWeak();
		fm = nf+1;			// friends_min
		perm( 0, nf, nf, new int[nf], new boolean[nf] );
		return fm == nf+1 ? -1 : fm;
	}
}

( 처음에는 1시간동안 이동가능한 거리가 긴 친구들부터 먼저 점검을 하는 것이 최소인원을 구할 수 있을거라고 생각해서 dist[]를 내림차순으로 정렬한 후 순서대로 투입하게끔 코드를 짰다. 하지만 취약점들을 선형으로 순서대로 점검 할 시, 각 취약점들 사이의 거리가 내림차순도 아니고 각기 다르기 때문에 무조건 거리가 긴 순서대로 투입하는 것이 틀리다는 것을 깨달았다. 카카오 코테 홈페이지의 해설을 참고하여 문제를 해결하였다 )