[JAVA] 17266번 - 어두운 굴다리

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하여 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

 

두가지 방법으로 풀었다.

첫번째 방법은 그냥 풀었고 두번째는 이분탐색을 이용!

 

첫번째 방법

그림을 그려서 생각하면 금방 답이 보인다

1) 시작지점에서부터 첫번째 가로등까지의 길이

2) 가로등 i와 j의 거리 / 2

3) 마지막 가로등에서 마지막 지점까지의 길이

중에서 제일 큰 값을 찾으면된다.

두번째 방법

이분탐색을 이용한다. 어떻게 이분탐색을 써야하지...? 고민을 좀 했다.

그냥 풀어도 풀리는데... 어떻게 하나 생각함...

이분탐색의 알고리즘을 이용해 mid값을 가로등의 높이로 생각한다. mid의 높이 일때, 굴다리를 모두 비출 수 있는지 확인한다. 

비출 수 있으면 더 작은 높이로도 가능한지 확인한다.

 

 

 

시간복잡도

1. 첫번째 풀이방법은 가로등의 갯수만큼 그 간격을 구해서 최대값으로 갱신해줘야한다,

최대m번 반복할 수 있고 m은 최대 100,000이니까 O(100,000)으로 1초안에 충분히 가능하

 

2. 두번째 풀이방법은 이분탐색이기 때문에 O(log N)이다.

start부터 end까지 탐색하고, n은 최대 100,000이다

그리고 빛을 비출 수 있는지 가로등을 탐색해야한다. 개수만큼 탐색하니까 O(m)이다

이진탐색의 단계마다 가로등을 탐색하니까 곱한다.

전체 시간 복잡도=O(m⋅logN)= 약 17번의 횟수다. 1초안에 충분히 가능하다 

 

코드 설계하기

위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡았다면, 문제 풀이를 본격적으로 하기전, 문제를 풀이 위한 로드맵을 그려본다
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

두번째 풀이 방법

두 부분으로나눈다. 

 

1) 이진탐색

while(start<=end) {
        	int mid = (start+end)/2;
        	if(lightCheck(mid)) {
        		ans = mid;
        		end = mid-1; //더 작은 높이에서도 가능한지 확인하기 위해 탐색 범위줄임 
        	}
        	else {
        		start = mid+1; //불가능한 경우는 높이가 더 커져야함 
        	}
        }

 

2) 불빛 확인

 

a. 높이를 파라미터로 받아서 해당 높이에서 전체 굴다리를 비출 수 있는지 확인한다.

포인트는 현재 가로등이 비추는 시작점이 이전 가로등이 비춘 마지막 지점보다 작거나 같아야한다.

prev 변수를 하나 써서 현재까지 가로등이 비춘 마지막 지점을 이용

 

가로등이 밝힐 수 있는 범위는 이렇게 나타낼 수 있다. 이걸 이용한다.

arr[i]-mid
arr[i]+mid

 

 

그림을 예시로 들어보면 현재가로등7이 비추는 시작지점4가 이전가로등3이 비춘 마지막지점 6보다 작거나 같아야한다!

그렇지 않으면 중간에 비추지 못하는 구간이 생긴다

이걸 코드로 표현하면 다음과 같다. 

arr[i]-mid<=prev

비출 수 있다면 다음 가로등도 계속 탐색을 해야하니까 prev를 현재 가로등이 비출 수  있는 구간의 끝 지점으로 갱신

만약 첫번째 가로등에 대해 탐색했다면 prev는 0에서 6 이 된다.

prev = arr[i]+mid;

 

b. 마지막으로 마지막 가로등이 굴다리의 끝 지점까지 커버하는지 확인한다.

n-prev

 

private static boolean lightCheck(int mid) {
	int prev= 0; //현재까지 가로등이 비춘 마지막 지점 
	
	for(int i=0; i<arr.length; i++) {
		if(arr[i]-mid<=prev) {
			prev = arr[i]+mid;
		}
		else {
			return false;
		}
	}
	if(n-prev>0) {
		return false;
	}
	else {
		return true;
	}
	
}

 

 

시도 회차 수정 사항

- 무분별하게 "맞았습니다" 가 나올때까지 수정하는 형태의 문제 풀이를 반복하면, 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 된다
- 틀렸습니다를 받았다면 왜 틀렸는지 고민핸보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

 

첫번째 방법

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {
   public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));       
        
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        
        int[] arr = new int[m];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<m; i++) {
        	arr[i] = Integer.parseInt(st.nextToken());
        }
        
        int a = arr[0];
        for(int i=0; i<m-1; i++) {
        	 int gap = arr[i+1]-arr[i];
        	 int height = (gap % 2 == 0) ? gap / 2 : (gap / 2) + 1;
        	 a=Math.max(a, height);
        }
        
        a = Math.max(a, n-arr[m-1]);
        System.out.println(a);
      
    }  
}

 

두번째 방법

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {
	static int[] arr;
	static int n,m;
   public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));       
        
        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());
        
        arr = new int[m];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<m; i++) {
        	arr[i] = Integer.parseInt(st.nextToken());
        }
        
        int start = 1;
        int end = n;
        int ans = 0;
        
        while(start<=end) {
        	int mid = (start+end)/2;
        	if(lightCheck(mid)) {
        		ans = mid;
        		end = mid-1; //더 작은 높이에서도 가능한지 확인하기 위해 탐색 범위줄임 
        	}
        	else {
        		start = mid+1; //불가능한 경우는 높이가 더 커져야함 
        	}
        }
        System.out.println(ans);
        
    }

private static boolean lightCheck(int mid) {
	int prev= 0; //
	
	for(int i=0; i<arr.length; i++) {
		if(arr[i]-mid<=prev) {
			prev = arr[i]+mid;
		}
		else {
			return false;
		}
	}
	if(n-prev>0) {
		return false;
	}
	else {
		return true;
	}
	
}
  
}