[프로그래머스] 징검다리 건너기 - LEVEL 3

🔗 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/64062

✍️ 문제 풀이

해당 문제는 이진 탐색 중 파라메트릭 서치 문제로, 건널 수 있는 인원의 최소와 최대 범위를 이진 탐색을 통해 탐색하여 건널 수 있는 인원 중 최대 인원을 구해주었다.

1) start를 1, end를 200,000,000 으로 초기화 한다.

• 문제 조건에서 stones 내의 각 원소들의 값은 1 이상 200,000,000 이하인 자연수로 지정됨.

2) stones 벡터를 복사하여 저장할 stones_copy 벡터를 선언해준다.

3) end가 start보다 크거나 같지 않을 때까지 이진 탐색을 반복 해준다.

• mid를 start와 end의 중간값으로 초기화 해준다.
• stones_copy에 stones를 그대로 복사한다.
• 해당 mid 값을 건너는 인원으로 가정했을 때 건널 수 있는 경우인지 판별한다.
  • 건널 수 있는 경우 : 0인 징검다리가 연속으로 나오는 개수가 k개 미만이어야한다.
    • 0이 연속으로 나오는 개수를 저장할 count를 선언한다.
    • stones_copy를 처음부터 끝까지 돌면서 연속된 0의 개수를 확인한다.
      • stones[i] - mid <= 0 이라면 count를 1 증가시킨다.
      • 아니라면 count를 0으로 초기화한다. (연속성이 깨지게 되므로)
      • count가 k개 이상이 되는 순간 루프를 빠져나간다. (건널 수 없는 경우에 도달)
• 종료되었을 때 count의 개수를 기준으로 start와 end의 위치를 옮겨준다.
  • count >= k : 건너는 인원을 너무 많이 잡아 건널 수 있는 거리 초과
    -> mid 이상은 불가능하므로 mid 미만 범위 탐색 -> end = mid - 1
  • count < k : 건너는 인원을 너무 적게 잡거나 딱 맞게 잡아 최대 거리 초과 X
    -> 일단 answer를 mid로 초기화하고, mid를 초과하는 값도 탐색
    -> start = mid + 1

4) 이진 탐색이 종료된 이후 answer에 최대 인원이 저장되는데, 이 때 answer에 +1을 해주어야 한다.

• mid가 건너는 인원이라고 가정했을 때 건널 수 있는 경우인지 판별하는데, 판별 기준이 mid명이 건너고 난 뒤의 상태에 대해 판별된다.
  • ex. stones = [2, 4, 5 ,3, 2, 1, 4, 2, 5, 1], k = 3이고 mid = 3이라고 할 때
    • 3명이 건너고 난 상태면 [0, 1, 2, 0, 0, 0, 1, 0, 2, 0] 과 같은 상태가 된다.
    • 4 ~ 6 인덱스에서 0이 연속으로 3개 나와 건널 수 없는 경우로 판별된다.
    • 하지만 3명이 건널 때 실제로는 [0, 2, 3, 1, 0, 0, 2, 0, 3, 0] 인 상태에서 1명이 더 건너는 경우이기 때문에 가능한 경우다.
    • 따라서 mid가 n이면 n번째 인원을 통과하고도 한 명 더 통과할 수 있는 상태가 되는 것이다.

🖥️ 풀이 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> stones;

int solution(vector<int> stones, int k) 
{
	int start = 1, end = 200000000, answer;
	vector<int> stones_copy;
	while (end >= start)
	{
		int mid = start + (end - start) / 2;
		stones_copy = stones;

		// 연속으로 0이 나올 때 count를 1씩 증가시키고, 연속성이 깨지면 다시 count를 0으로 초기화
		int count = 0;
		for (int i = 0; i < stones_copy.size(); i++)
		{
			if (stones_copy[i] - mid <= 0)
				count++;
			else
				count = 0;

			// 연속으로 나온 0의 개수가 가능한 거리를 넘으면 바로 반복 종료
			if (count >= k)
				break;
		}
		if (count >= k)			// 건너는 인원을 너무 많이 잡아 건널 수 있는 거리 초과 ->  mid 이상은 불가능하므로 mid 미만 값 탐색
			end = mid - 1;
		else                    // 건너는 인원을 너무 적게 잡거나 딱 맞게 잡아 거리 안에 가능 -> 일단 answer를 mid로 초기화하고 mid 초과 값도 탐색  
		{
			answer = mid;
			start = mid + 1;
		}
	}
	return answer + 1;		// mid가 n이면 n번째 인원을 통과하고도 한 명 더 통과할 수 있는 상태이므로 +1
}