프로그래머스 - 야간 전술보행
오늘은 프로그래머스 2단계 야간 전술보행을 풀어보겠습니다.
※ 문제 설명을 아는 분들은 스킵하셔도 됩니다!
문제 설명
문제를 간단하게 설명 하겠습니다.
- 화랑이는 야간 전술보행으로 적군 기지에 침투해야 합니다.
-> 화랑이의 현 위치부터 적군 기지까지의 거리(m)가 'distace'입니다.- 화랑이의 야간 전술보행은 1m/s 입니다.
-> 화랑이는 1초에 1m를 갈 수 있습니다.- 화랑이는 쉬지 않고 적군 기지까지 갑니다.
-> 화랑이는 멈춰설 수 없습니다.- 경비병들의 단속 구간이 있습니다.
-> 경비병이 단속하는 구간을 담은 2차원 배열은 'scope', 각 경비병마다 단속하는 구간은 'scope[i]'입니다.- 경비병의 근무 시간과 휴식 시간을 담은 2차원 정수 배열은 'time'입니다.
이 문제가 원하는 것은 '화랑이가 적군 기지까지 갈 때, 경비병에게 걸릴 때까지 갈 수 있는 거리를 반환하는 것' 입니다.
예시
입출력 예제 1번을 보며 설명하겠습니다.
-
첫 번째 경비병의 단속 구간은 3~4, 근무 시간은 2초, 휴식 시간은 5초 입니다.
60분 근무하면 42분 쉬는 월급 루팡 경비병 -
두 번째 경비병의 단속 구간은 5~8, 근무 시간은 4초, 휴식 시간은 3초 입니다.
-
화랑이가 첫 번째 경비병의 간속 구간인 3, 4를 지나갈 때, 첫 번째 경비병은 휴식 시간 입니다.
-
화랑이가 두 번째 경비병의 단속 구간 5, 6, 7을 지나갈 때, 두 번째 경비병은 휴식 시간 입니다.
-
화랑이의 위치가 8일 때, 휴식을 마친 두 번째 경비병이 복귀하므로 하랑이는 경비병에게 발각 됩니다.
-
화랑이가 '경비병에게 발각된 위치'를 반환합니다.
풀이
※ 제가 푼 방법보다 더 좋은 방법으로 풀 수 있기 때문에, 참고용으로만 봐주셨으면 좋겠습니다.
-
단속 구간과 근무 시간, 휴식 시간을 가지고 있는 경비병 클래스를 만듭니다.
-
PriorityQueue에 경비병을 넣습니다.
(PriorityQueue에 정렬 방식은 scope의 가장 낮은 단속 구간 지점부터 오름차순 정렬합니다.)여기서 많은 분들이 실수해서, 테스트 케이스 9번을 통과하지 못합니다.
그 이유는 scope[i][0]이 scope[i][1]보다 작다고 생각하기 때문입니다.
scope를 정렬하는 과정에서 scope[i][0]과 scope[i][1] 중, 더 낮은 단속 구간의 지점을 가지고 scope를 정렬해야 화랑이가 지나가는 구간이 경비병이 단속하는 구간인지 확인할 수 있기 때문입니다. 지문에서도 'scope[i]가 정렬되지 않을 수도 있다.'라고 말합니다.
-
PriorityQueue에서 가장 낮은 단속 구간을 가지고 있는 경비병을 가져옵니다.
-
반복문을 이용하여 1초 단위로 화랑이의 위치를 바꿔줍니다.
-
화랑이가 경비병이 단속하는 구역을 지나가는데 경비병이 근무 시간인 경우, 반복문을 중단하고 화랑이의 위치를 반환합니다.
-
화랑이가 경비병이 관리하는 구역을 단속되지 않고 지나갔을 경우, PriorityQueue에서 다음 경비병을 가져옵니다.
-
반복문을 끝까지 반복했다면 적군 기지까지의 거리인 'distance'를 반환합니다.
코드
import java.util.PriorityQueue;
class Solution {
class Guard implements Comparable<Guard>
{
int smallScope;
int bigScope;
int workTime;
int restTime;
Guard(int[] time, int[] scope)
{
workTime = time[0];
restTime = time[1];
smallScope = Math.min(scope[0],scope[1]);
bigScope = Math.max(scope[0],scope[1]);
}
@Override
public int compareTo(Guard o) {
return smallScope-o.smallScope;
}
}
public int solution(int distance, int[][] scope, int[][] times)
{
// 경비병들을 담는 queue, scope가 작은 것부터 오름차순 정렬
PriorityQueue<Guard> guards = new PriorityQueue<>();
// 경비병을 PriorityQueue에 담기
for(int i = 0; i < scope.length; i++)
guards.add(new Guard(times[i],scope[i]));
// 가장 낮은 구간을 단속하는 경비병 가져오기
Guard guard = guards.poll();
int hwaRang = 0;
for(; hwaRang < distance; hwaRang++)
{
// 화랑이의 위치가 단속 구간 전이라면, continue
if(hwaRang < guard.smallScope)
continue;
// 화랑이가 단속구간을 지나갈 때, 경비원의 시간 사이클만을 가져오기 위한 나머지 연산
int time = hwaRang % (guard.workTime + guard.restTime);
// time이 0보다 크고 경비원의 근무 시간 안에 있다면, 발각 당한 것이므로 반복문 중단
if(0 < time && time <= guard.workTime)
break;
// 화랑이가 해당 경비원의 단속 구간을 벗어났을 경우, 다음 구간을 단속하는 경비원 가져오기
if(guard.bigScope <= hwaRang && guards.size() != 0)
guard = guards.poll();
}
// 화랑이의 최종 위치 반환
return hwaRang;
}
}테스트
'distance', 'int[][] scope', 'int[][] time'을 랜덤으로 만들어 주는 클래스입니다.
대충 만들어서 distance의 범위도 실제 테스트 케이스에서 주어지는 것 보다 작고, scope[i]의 범위가 넓어 length만큼 채우지 못해 무한 반복할 때가 있긴합니다..ㅠㅠ (무한 반복될 때, 다시 실행해 주세요.)
해당 클래스 이용해서 본인 코드와 정답 코드의 반환 값이 같은지 확인하는 용도로 쓰시면 될 것 같습니다.
import java.util.Random;
class Source
{
Random random;
int length;
int distance;
int[][] scopes;
int[][] times;
Source()
{
random = new Random();
distance = random.nextInt(50)+10;
length = random.nextInt(distance / 4)+1;
setScope();
setTimes();
}
public void setScope()
{
scopes = new int[length][2];
for(int i = 0; i < length; i++)
{
int[] newScope = new int[2];
do {
newScope[0] = random.nextInt(distance)+1;
newScope[1] = random.nextInt(distance)+1;
} while (newScope[0] == newScope[1] || !chkScope(newScope));
scopes[i] = newScope;
}
}
public boolean chkScope(int[] newScope)
{
for(int[] scope : scopes)
{
if(Math.max(newScope[0],newScope[1]) < Math.min(scope[0],scope[1])
|| Math.max(scope[0],scope[1]) < Math.min(newScope[0],newScope[1]))
continue;
return false;
}
return true;
}
public void setTimes()
{
times = new int[length][2];
for(int i = 0; i < times.length; i++)
{
int[] time = new int[2];
time[0] = random.nextInt(10)+1;
time[1] = random.nextInt(10)+1;
times[i] = time;
}
}
}#썸네일 제작 : 미리 캔버스
