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

 

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

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

 

약 0.6%의 정답률인 문제입니다.

투 포인터 + dfs로 풀려다가 도저히 답이 안 나와서 풀이를 보고 다시 풀어봤습니다.

가장 간단한 방법은 취약 지점을 한 칸씩 밀어주고, 친구들의 거리를 순열로 뽑은 후 검사하는 것입니다.

 

취약 지점을 예로 들자면

[1, 5, 6, 10] 

1. [5, 6, 10, 13]
2. [6, 10, 13, 17]
3. [10, 13, 17, 18]

이렇게 초기 배열 1개와 밀려난 배열 3(4-1) 개를 얻을 수 있습니다.

 

친구들의 거리도 순열로 뽑아서 원소의 개수가 1개~dist.length개까지 뽑아줍니다.

 

그리고 모든 경우에 대해 검사를 하며 최소값을 찾으면 됩니다.

해설을 보니 별 거 없지만 시험이었다면 못 풀었을거라 생각합니다.

---

전역 변수

n, weak[], dist []= 문제에서 주어진 값

min = 정답(최솟값)

rotateWeak [][] = 취약지점을 한 칸씩 밀어준 배열

visit [] = 친구 거리를 순열로 뽑아낼 때 방문 확인

메소드

int solution

전역 변수들의 값을 채워주고, 배열들의 크기를 정해줍니다.

(rotate, per 호출)

 

void rotate

weak 배열을 한 칸씩 밀어준 배열을 rotateWeak에 저장합니다.

 

void per

순열로 친구 거리를 뽑아줍니다. 원하는 인원수(length)가 채워졌다면 얘들로 벽을 점검이 가능한지 검사해줍니다.(check 호출)

 

void check

순열로 뽑힌 친구들로 점검을 시작합니다.

이 친구들은 rotateWeak.length만큼 일을 합니다.(모든 경우의 수 검사)

 

index는 외벽 배열의 index를 가리키고, start는 일을 해야 할 포인트의 값입니다.

while문을 통해 친구들 중 한 명이 일을 할 수 있는 범위까지 밀어줍니다.

 

예를 들어 [1, 4, 60, 70]의 취약 지점이 있다면 5의 일을 하는 친구를 골랐을 때, 

index는 0에서 2가 되고 start는 60이 됩니다.

 

친구들이 일을 끝냈다면 index가 배열 밖으로 밀려날 것이고 이때 친구들의 인원수의 최솟값으로 최적화해줍니다.

public class Solution {
	
	public int n, min;
	public int[] weak, dist;
	public int[][] rotateWeak;
	public boolean[] visit;
	
	public int solution(int n, int[] weak, int[] dist) {
		this.n = n;
		this.weak = weak;
		this.dist = dist;
		rotateWeak = new int[weak.length][weak.length];
		visit = new boolean[dist.length];
		min = Integer.MAX_VALUE;
		rotate();
		
		for(int i = 1; i <= dist.length; i++) {
			per(0, i, "");
		}
		
		return min == Integer.MAX_VALUE ? -1 : min;
	}
	
	public void rotate() {
		for(int j = 0; j < weak.length; j++) {
			int ro[] = new int[weak.length];
			int index = j;
			
			for(int i = 0; i < weak.length; i++) {
				ro[i] = weak[index % weak.length];
				
				if(index >= weak.length)
					ro[i] += n;
				index++;
			}
			rotateWeak[j] = ro;
		}
	}
	
	public void per(int count, int length, String s) {
		if(count == length) {
			check(s.trim().split(" "));
			return;
		}
		
		for(int i = 0; i < dist.length; i++) {
			if(!visit[i]) {
				visit[i] = true;
				per(count+1, length, s + dist[i]+ " ");
				visit[i] = false;
			}
		}
	}
	
	public void check(String s[]) {
		int people[] = new int[s.length];
		for(int i = 0; i < s.length; i++)
			people[i] = Integer.parseInt(s[i]);
		
		for(int i = 0; i < rotateWeak.length; i++) {
			int index = 0;
			int start = rotateWeak[i][index];
			
			for(int j = 0; j < people.length; j++) {
				while(index < rotateWeak.length && rotateWeak[i][index]-start <= people[j]) {
					index++;
				}
				if(index >= rotateWeak.length)
					min = Math.min(min, people.length);
                else
                    start = rotateWeak[i][index];
			}
		}
	}
}

 

문제 푸는 데 정신 팔려 최적화를 하지 않아 시간, 공간 복잡도는 엉망입니다.

<(＿　＿)>