이번 문제는 지난번 이분탐색 문제 풀때와는 다르게 방법이 약간 생각이 났지만 자세히는 어떻게 해야할지 몰라
결국 답지를 보게 되었다.
문제부터 살펴보자.
문제 설명
출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다.
예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 [2, 14, 11, 21, 17] 지점에 놓여있을 때 바위 2개를 제거하면 출발지점, 도착지점, 바위 간의 거리가 아래와 같습니다.
제거한 바위의 위치각 바위 사이의 거리거리의 최솟값
| [21, 17] | [2, 9, 3, 11] | 2 |
| [2, 21] | [11, 3, 3, 8] | 3 |
| [2, 11] | [14, 3, 4, 4] | 3 |
| [11, 21] | [2, 12, 3, 8] | 2 |
| [2, 14] | [11, 6, 4, 4] | 4 |
위에서 구한 거리의 최솟값 중에 가장 큰 값은 4입니다.
출발지점부터 도착지점까지의 거리 distance, 바위들이 있는 위치를 담은 배열 rocks, 제거할 바위의 수 n이 매개변수로 주어질 때, 바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 도착지점까지의 거리 distance는 1 이상 1,000,000,000 이하입니다.
- 바위는 1개 이상 50,000개 이하가 있습니다.
- n 은 1 이상 바위의 개수 이하입니다.
입출력 예
| distance | rocks | n | return |
| 25 | [2, 14, 11, 21, 17] | 2 | 4 |
문제 풀이에 앞서 일단 소스를 보여주고 해당 소스에 대한 설명은 아래에 설명을 하겠다.
public int solution(int distance, int[] rocks, int n) {
int answer = 0;
Arrays.sort(rocks);//이분탐색할 때는 정렬을 해야함
int left=1;
int right=distance;
int remove=0;//제거한 바위갯수
int mid;//바위사이의 최소 거리
int lastRock=0;//마지막 바위
while(left<=right){
System.out.println("left : "+left);
System.out.println("right : "+right);
mid=(left+right)/2;
System.out.println("mid : "+mid);
for(int i=0;i<rocks.length;i++){ //바위 위치 배열 접근
int temp = rocks[i] - lastRock;
//현재돌 위치 - 이전돌의 위치 가 최소거리보다 작으면 해당 바위는 제거해야한다.
//최소거리 mid 보다 작으면 해당바위를 제거하는 이유는
//최소거리중 최대값을 찾아야 하기 때문이다.
//따라서 최소거리 mid 보다 작은 값들은 답과 먼 값이기때문에 remove한다
if(mid>temp) {
remove++;
System.out.println("remove : "+remove);
}
else { //현재돌위치 - 이전돌 위치 가 최소 거리보다 크다면 이전돌 위치를 현재돌 위치로 바꿈
//이부분에 들어오는 값은 답이 될수 있기 때문에 remove를 하지 않는다.
//돌을 제거 하지 않았으니 다음 돌과의 거리를 구하기 위해
//해당 돌의 위치 값을 이전돌의 위치 값으로 바꿔준다.
lastRock=rocks[i]; //더크다면 이전돌을 옮김
System.out.println("lastRock : "+lastRock);
}
}
//위의 반복문을 통해서 우리는 값을 구하기 위해 몇개의 돌을 제거하는지를 구했다.
//하지만 마지막 돌과 도착지점까지의 거리를 구하지 않았다.
System.out.println("---for문 끝---");
//그래서 이부분에서 마지막도과 도착지점까지의 거리를 구하고 해당 거리가 답인 mid 보다 작으면
//해당 돌을 제거하게 했다.
if(distance-lastRock<mid) {
remove++;//마지막바위와 도착지간의 거리 체크
System.out.println("remove : "+ remove);
}
//이부분이 답을 구하게 해주는 부분인대
//만약 우리가 답을 구하기 위해 제거한돌의 개수 remove가 제거해야하는 돌의개수 n보다 크게 되면
//임의로 정한 최소값 mid가 답 이 아니기때문에 right의 index 값을 mid-1로 옮겨준다.
if(remove>n) {
//제거하려는 수가 제거할수 있는수? 보다 클때?
right=mid-1;
System.out.println("right : "+right);
}
//이부분은 위 if문과 반대로 제거한 돌의 개수 remove가 제거해야할 돌의 개수보다 작기 때문에
//시작지점인 left를 옮겨준다.
else{
//이부분은 이제 제거한 돌의수 remove가 제거해야할 돌의 개수와 같거자 작을때 진입하는 부분이다.
//우리는 최소값중 최대값을 집어 넣어야 하기때문에 Math.max 값을 넣게 하였고
//left값을 임의로 정한 mid 값을 높이기 위해 left 값을 수정한다.
//left 값을 올리는 이유는 제거해야할 돌의 개수가 제거한 돌의 개수보다 클수가 있기 때문이다.
answer=Math.max(answer, mid);
left=mid+1;
System.out.println("answer : "+ answer);
System.out.println("left : "+left);
}
//제거한 돌의 개수를 0으로 다시 초기화 해주고 이전돌의 위치도 다시 0으로 초기화 해준다.
//lastRock도 바꿔준 이유는 while문을 다시 한번 돌때는 mid값이 바뀌니 제거할 돌이 달라지기때문이다.
remove=0;
lastRock=0;
System.out.println("------while 끝-----");
}
return answer;
}
문제 풀이
이번 문제는 일단 이분탐색의 기본인 start와 end가 나와 있다.
start = 0
end = 25
이걸 알면 이제 중간값 mid를 가지고 무언가를 해야한다는건 짐작이 갈수 있다.
하지만 중간 값을 뭘로 설정을 해야할지는 감이 안잡힐수 있다. (내가 그랬기 때문)
문제 1. 중간값을 뭘로 설정을 해야하나
문제가 원하는 답을 알면 mid값을 뭘로 설정할지 감이 잡힐수 있다.
문제가 원하는 답은 돌과의 최소 거리이니 mid 값을 돌과의 최소거리로 설정을 하자.
(start+end)/2 = mid(임의의 돌사이 최소거리)
그럼 우리는 이분탐색으로 계속해서 mid값보다 큰지 작은지 계속 비교해 나가서
start와 end의 위치를 변경해주어야 한다.
그렇다면 mid와 어떤걸 계속해서 비교해줘야 하나?
문제 2. mid와 어떤 걸 계속해서 비교해가며 확인해야하나?
mid는 위에서 말했듯이 임의로 우리가 돌과의 최소 거리를 정해 놓은것이다.
우리가 임의로 정해놓은 이유는 계속해서 돌과의 최소거리를 찾기위해서 임의로 정해 놓은것이다.
그래서 우리가 임의로 정한 mid값과 계속해서 비교할 값은 돌과 돌사이의 거리를 계속해서 비교해 나가면 된다.
그럼 돌과 돌 사이의 거리는 어떻게 구하는가?
문제 3. 돌과 돌 사이의 거리는 어떻게 구하나?
돌과 돌 사이의 거리를 구하려면 일단
현재돌 위치에서 이전 돌 위치를 빼면 된다.
ex)
현재돌 위치 - 이전돌
하지만 이때 우리가 주의해야할 점은
위 문제에서 구하려는것은 최소거리중 최대값을 구하는것이기 때문에
mid값보다 작을때의 돌의 위치는 답이 될수 없기때문에 돌을 제거한다.
아래와 같은 조건식을 만들어야 한다.
if(mid>temp) {
remove++;
System.out.println("remove : "+remove);
}
그리고 mid값보다 크게 되면 해당 돌의 위치는 답이 될수 있기 때문에 돌을 제거하지 않고
이전 돌의 위치를 현재 돌의 위치로 변경을 해준다.
이렇게 해주는 이유는 mid 값보다 크기때문에 돌을 제거하지 않았기 때문이다.
돌을 제거 하지 않았으니 다음 돌을 만났을때 이전돌의 위치가 되어야 한다.
그래서 이 조건을 맞추려면 아래와 같은 조건식이 되어야 한다.
else {
lastRock=rocks[i]; //더크다면 이전돌을 옮김
System.out.println("lastRock : "+lastRock);
}
위처럼 하게 되면 돌과 돌사이의 거리를 구할수 있게 되지만은
마지막 돌과 도착지점까지의 거리를 mid와 비교를 하지 못하게 된다.
따라서 해당 부분도 검사를 하기 위해서 아래 조건식을 넣어줘야 한다.
if(distance-lastRock<mid) {
remove++;//마지막바위와 도착지간의 거리 체크
System.out.println("remove : "+ remove);
}위 조건식은 (도착지점 - 마지막 돌위치) 가 mid보다 작으면 돌을 제거하라는 뜻이다.
그럼 우리는 임의로 정한 최소거리 mid에 맞게 돌을 제거했으니 우리가 확인해봐야 할것은 무엇일까?
문제 4. mid에 맞게 제거한 돌의 개수 remove와 어떤걸 비교해야 할까?
우리는 mid에 맞게 제거한 돌의 개수 remove와 우리가 제거하기로한 돌의 개수 n과 비교해야한다.
따라서 조건식은 아래와 같아야 한다.
if(remove>n){
}else{
}그렇담 안의 조건식에는 어떤 값을 넣어줘야 할까??
문제5. 조건식 안에 어떤 명령문을 넣어줘야 할까?
일단 제거한 돌의 개수 remove 가 n보다 크다는것은
우리가 mid값을 너무 크게 잡아 돌을 너무 많이 제거했다는뜻이다.
따라서 우리는 mid값을 작게 잡기 위해서는 end값을 mid-1의 값으로 수정해줘야 한다.
그래서 명령문은 아래와 같이 해야한다.
if(remove>n) {
right=mid-1;//right 와 end는 같은 말
System.out.println("right : "+right);
}
그리고 remove가 n보다 작거나 같다라는것은
mid값을 너무 작게 설정했기때문에 돌을 적게 제거했다는뜻이다.
따라서 우리는 mid값을 높이기 위해서 start값을 높여야 하고
remove가 n보다 같을수도 있을때를 고려해서 기존의 answer값과 mid값중 큰값을 answer로 넣어줘야 한다.
else{
answer=Math.max(answer, mid);
left=mid+1;
System.out.println("answer : "+ answer);
System.out.println("left : "+left);
}
그렇담 이제 start와 end값을 수정했으니 우리는 다시 제거한 돌의 개수를 세기 위해서
remove를 0으로 초기화 시키고 이전돌의 위치도 다시 구하기 위해 0으로 설정해야 한다.
느낀점
1. 이분탐색은 무엇을 탐색할지 찾고 정하는게 제일 우선이다.
2. 탐색해야할 개수가 엄청 많다면 이분탐색을 고려해라.
'코딩일기 > 알고리즘' 카테고리의 다른 글
| [자료구조] 플로이드 워셜 알고리즘 (Java) (0) | 2021.07.09 |
|---|---|
| [프로그래머스 : 레벨 3] 가장 먼 노드 : BFS(Java) (0) | 2021.07.09 |
| [프로그래머스 : 레벨3] 입국심사 : 이분탐색(Java) (0) | 2021.06.30 |
| [자료구조] 이분(이진)탐색 트리 구현 (Java) (0) | 2021.06.29 |
| [프로그래머스 : 레벨3] 여행경로 : DFS(Java) (0) | 2021.06.22 |
