쌍(pair)으로 이루어진 배열 P가 있다고 가정해 보겠습니다. 여기서 P[i]는 (l, r) 형태를 가지며, 또 하나의 숫자 k가 주어집니다. n개의 챕터로 구성된 책을 읽으려고 하는데, 책의 각 페이지는 정확히 하나의 챕터에 속하고 각 챕터는 최소 한 페이지 이상을 포함합니다. 일부 페이지를 이미 읽었으며, k번 페이지는 아직 읽지 않은 첫 번째 페이지로 표시되어 있습니다. 이때 우리가 구해야 할 값은 아직 완전히 읽지 못한 챕터의 개수입니다. 배열 P의 각 원소는 해당 챕터의 페이지 번호 범위를 나타냅니다.
예를 들어 입력이 P = [[1, 3], [4, 7], [8, 11]]; k = 4라면 출력은 2가 됩니다. 첫 번째 챕터(1~3페이지)는 이미 모두 읽었고, 두 번째와 세 번째 챕터는 아직 읽어야 하기 때문입니다.
풀이 접근 방식
이 문제는 매우 간단한 선형 탐색으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- k가 속한 챕터의 범위를 찾으면, 그 챕터부터 마지막 챕터까지가 모두 '완전히 읽지 않은' 챕터입니다.
- 따라서 k가 포함된 챕터의 인덱스를 찾은 뒤, 전체 챕터 수에서 그 앞에 있는 챕터 수를 빼주면 됩니다.
구체적인 풀이 단계는 다음과 같습니다.
n := P의 크기
i := 1부터 i <= n까지 반복하며(i를 1씩 증가):
만약 k >= P[i - 1][0] 이고 k <= P[i - 1][1]이라면:
return n - i + 1
return 0즉, k가 포함된 챕터를 발견하는 즉시 n - i + 1(현재 챕터부터 마지막 챕터까지의 개수)를 반환하고, 끝까지 찾지 못하면 모든 챕터를 다 읽었다는 의미이므로 0을 반환합니다.
예제 코드
더 잘 이해할 수 있도록 다음 C++ 구현 예제를 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int solve(vector<vector<int>> P, int k){
int n = P.size();
for (int i = 1; i <= n; i++){
if (k >= P[i - 1][0] && k <= P[i - 1][1])
return n - i + 1;
}
return 0;
}
int main(){
vector<vector<int>> P = { { 1, 3 }, { 4, 7 }, { 8, 11 } };
int k = 4;
cout << solve(P, k) << endl;
}입력
{ { 1, 3 }, { 4, 7 }, { 8, 11 } }, 4출력
2
이 알고리즘의 시간 복잡도는 O(n)이며, 공간 복잡도는 O(1)입니다. 챕터 수에 비례하여 한 번만 배열을 순회하면 되므로 매우 효율적입니다.