문제를 이해하고 있다면 바로 풀이를 보면 됨
전체 코드로 바로 넘어가도 됨
마음대로 번역해서 오역이 있을 수 있음

문제

운전자가 고속도로에서 운전하고 있다. 그의 자동차의 엔진 경고등이 켜져있고, 운전자는 지금 바로 서비스 받고 싶다. 운 좋게, 서비스 차로는 고속도로와 평행하게 있다. 이 차로는 다양한 너비와 길이가 다양하다.

도로의 지점에서의 폭과 진입과 이탈 지점이 주어진다. 각 진입과 이탈 지점을 고려하여 해당 서비스 차로에서 안전하게 이동할 수 있는 최대 크기의 차량을 구해라.

Example

n = 4
width = [2, 3, 2, 1]
cases = [[1, 2], [2, 4]]

만약 진입 지점이 i = 1이고, 이탈 지점이 j = 2이면 각각 2와 3, 2개 폭이 있다. 둘 다 진입할 수 있는 차의 폭은 2이다. 만약 i = 2이고, j = 4일때 폭은 [3, 2, 1]이고 차량의 폭은 1로 제한된다.

Function Description

serviceLane 함수를 완성해라.
serviceLane 함수는 아래와 같은 매개변수를 가지고 있다.

• int n: 폭의 크기 배열
• int cases[t][2]: 각 진입과 이탈의 배열

Returns

• int[t]: 구간 별로 안전하게 지나갈 수 있는 차량의 폭

Constraints

• 2 <= n <= 100000
• 1 <= t <= 1000
• 0 <= i < j < n;
• 2 <= j - i + 1 <= min(n, 1000)
• 1 <= width[k] <= 3, 단 0 <= k < n

풀이

문제를 이해하고 풀기 시작할때, 주어진 메소드의 매개변수가 이상하다는 것을 알 수 있다. Result 클래스의 매개변수를 수정해야하고, 수정하면서 Solution 클래스에서 해당 메소드를 사용하는 부분도 수정해야한다.

// 변경 전
public static List<Integer> serviceLane(
	int n, List<List<Integer>> cases
) {}

// 변경 후
public static List<Integer> serviceLane(
	List<Integer> width, List<List<Integer>> cases
) {}

// 변경 전
List<Integer> result = Result.serviceLane(n, cases);

// 변경 후
List<Integer> result = Result.serviceLane(width, cases);

이제 실제 풀이로 가서 차량의 폭을 담을 정수형 리스트 Result를 생성한다.

List<Integer> result = new ArrayList<>();

cases를 반복해서 해당 범위의 최소값을 찾는다. 최소값을 찾는 이유는 주어진 폭 모두 지나다닐 수 있어야하기 때문이다.

for(int i = 0; i < cases.size(); i++){
	int min = Integer.MAX_VALUE;
	
    for(int j = cases.get(i).get(0); j <= cases.get(i).get(1); j++){
		min = Integer.min(min, width.get(j));

		// 최소값이 1이면 더 이상 반복할 필요가 없어서 빠져나간다.
		if(min == 1){
			break;
		}
	}

	result.add(min);
}

마지막으로 result를 반환한다.

return result;

전체 코드

public static List<Integer> serviceLane(List<Integer> width, List<List<Integer>> cases) {
	List<Integer> result = new ArrayList<>();

	for(int i = 0; i < cases.size(); i++){
		int min = Integer.MAX_VALUE;

		for(int j = cases.get(i).get(0); j <= cases.get(i).get(1); j++){
			min = Integer.min(min, width.get(j));

			if(min == 1){
				break;
			}
		}

		result.add(min);
	}

	return result;
}