길이가 n인 배열 A와 숫자 k가 주어졌다고 가정해 봅시다. 대회에는 총 n개의 문제가 출제되어 있으며, Amal의 문제 해결 능력은 k입니다. Amal은 항상 목록의 양쪽 끝에 있는 문제만 풀 수 있고, 난이도가 k보다 큰 문제는 풀 수 없습니다. 왼쪽 끝과 오른쪽 끝의 문제 난이도가 모두 k보다 커지면 더 이상 문제를 풀지 못하고 멈추게 됩니다. 우리가 구해야 할 것은 그가 풀 수 있는 문제의 개수입니다. 여기서 A[i]는 i번째 문제의 난이도를 의미합니다.
문제 예시
예를 들어 입력이 A = [4, 2, 3, 1, 5, 1, 6, 4]이고 k = 4라고 해봅시다. 이 경우 출력은 5가 됩니다.
- 먼저 왼쪽 끝의 난이도 4짜리 문제를 풉니다.
- 다음으로 오른쪽 끝의 난이도 4짜리 문제를 풉니다.
- 이후 오른쪽 끝의 문제(난이도 6)는 풀 수 없으므로 방향을 바꿉니다.
- 왼쪽에서부터 난이도 2, 3, 1인 문제를 차례로 풉니다.
결과적으로 총 5개의 문제를 해결할 수 있습니다.
풀이 접근 방식
이 문제는 두 포인터(two pointer) 기법으로 간단히 해결할 수 있습니다. 왼쪽 끝에서 시작해 연속으로 풀 수 있는 문제의 개수를 세고(l), 오른쪽 끝에서도 마찬가지로 세면(r) 됩니다. 전체 문제 수에서 중간에 풀 수 없는 구간을 제외하면 정답을 구할 수 있습니다.
알고리즘 단계
이 문제를 해결하기 위해 다음 단계를 따릅니다.
n := A의 크기 l := 0 r := n - 1 for initialize i := 0, when i < n, update (increase i by 1), do: if A[i] <= k and l is same as i, then: (increase l by 1) while A[r] <= k, do: (decrease r by 1) if l is same as n, then: return n Otherwise return n - 1 - r + l
예제 코드
더 잘 이해할 수 있도록 다음 C++ 구현을 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A, int k) {
int n = A.size();
int l = 0, r = n - 1;
for (int i = 0; i < n; ++i) {
if (A[i] <= k && l == i)
++l;
}
while (A[r] <= k)
--r;
if (l == n)
return n;
else
return n - 1 - r + l;
}
int main() {
vector<int> A = { 4, 2, 3, 1, 5, 1, 6, 4 };
int k = 4;
cout << solve(A, k) << endl;
}입력
{ 4, 2, 3, 1, 5, 1, 6, 4 }, 4출력
5
정리
이 알고리즘은 배열을 한 번씩만 순회하므로 시간 복잡도는 O(n)입니다. 모든 문제의 난이도가 k 이하인 경우 l == n이 되어 전체 n을 반환하고, 그렇지 않은 경우 왼쪽에서 풀 수 있는 문제 수(l)와 오른쪽에서 풀 수 있는 문제 수(n - 1 - r)를 합산하여 답을 계산합니다.