이 문제에서는 비토닉(bitonic) 시퀀스와 Q개의 쿼리가 주어집니다. 각 쿼리에는 하나의 정수 x가 포함되어 있으며, 우리의 과제는 각 쿼리의 정수를 시퀀스에 삽입한 후 비토닉 시퀀스의 길이를 출력하는 것입니다. 모든 쿼리 처리가 끝나면 최종 비토닉 시퀀스를 출력해야 합니다.
문제 설명
여기서는 비토닉 시퀀스 하나가 주어지고, 시퀀스에 추가할 정수를 담은 Q개의 쿼리가 입력됩니다. 각 쿼리의 원소를 시퀀스에 추가하면서 비토닉 시퀀스의 길이를 반환하고, 모든 쿼리가 완료된 후에는 최종 비토닉 시퀀스를 출력합니다.
비토닉 시퀀스란?
비토닉 시퀀스는 특정 지점(비토닉 포인트라고 함)까지는 계속 증가하다가 그 이후부터는 감소하는 특수한 형태의 수열입니다.
예시: 1, 5, 6, 8, 9, 7, 5, 2
예제로 이해하기
입력
bseq = {1, 4, 6, 5, 2, 1}
Q = 2
Query = {5, 6}출력
7 7
{1, 4, 5, 6, 5, 2, 1}설명
첫 번째 쿼리에서 삽입할 값은 5입니다. 값 5는 시퀀스의 증가 부분에 삽입할 수 있으므로 시퀀스는 {1, 4, 5, 6, 5, 2, 1}이 되고, 길이는 7이 됩니다.
두 번째 쿼리에서 삽입할 값은 6입니다. 하지만 6은 이미 시퀀스의 최댓값이므로 삽입할 수 없습니다.
따라서 최종 시퀀스는 {1, 4, 5, 6, 5, 2, 1}이며 길이는 7입니다.
문제 해결 접근 방법
이 문제를 해결하려면 비토닉 시퀀스를 두 개의 집합으로 분할해야 합니다. 하나는 최댓값까지의 증가 부분을 담는 집합이고, 다른 하나는 감소 부분을 담는 집합입니다.
삽입할 각 원소에 대해 다음과 같은 경우를 고려할 수 있습니다.
- 경우 1 (원소가 최댓값보다 큰 경우): 해당 원소를 증가 수열의 끝에 추가하고 최댓값을 갱신합니다.
- 경우 2 (원소가 최댓값보다 작은 경우): 먼저 증가 집합에 동일한 원소가 있는지 확인하고, 없다면 증가 집합에 삽입합니다. 이미 존재한다면 감소 집합을 검색하여 가능하면 추가합니다.
- 경우 3 (원소가 최댓값과 같거나 증가·감소 두 집합 모두에 존재하는 경우): 해당 원소는 삽입할 수 없으므로 무시합니다.
각 쿼리 연산 후에는 두 집합의 길이를 더하여 비토닉 시퀀스의 길이를 구할 수 있습니다.
length(bseq) = length(incSet) + length(decSet)
모든 쿼리가 완료되면 incSet을 출력한 뒤 decSet을 출력하여 최종 비토닉 시퀀스를 완성합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
void calcBitonicSeqLenth(int bSeq[], int n, int query[], int Q){
int maxVal = INT_MIN;
for (int i = 0; i < n; i++)
maxVal = max(maxVal, bSeq[i]);
set <int> incSet, decSet;
incSet.insert(bSeq[0]);
decSet.insert(bSeq[n - 1]);
for (int i = 1; i < n; i++)
if (bSeq[i] > bSeq[i - 1])
incSet.insert(bSeq[i]);
for (int i = n - 2; i >= 0; i--)
if (bSeq[i] > bSeq[i + 1])
decSet.insert(bSeq[i]);
decSet.erase(decSet.find(maxVal));
for (int i = 0; i < Q; i++) {
if (maxVal <= query[i]) {
maxVal = query[i];
incSet.insert(query[i]);
}
else {
if (incSet.find(query[i]) == incSet.end())
incSet.insert(query[i]);
else
decSet.insert(query[i]);
}
int length = incSet.size() + decSet.size();
cout<<"For query "<<(i+1)<<": The length of Bitonic Sequence is "<<length<<endl;
}
cout<<"The Bitonic Sequence at the end of all queries is : ";
set<int>::iterator it;
for (it = incSet.begin(); it != incSet.end(); it++)
cout<<(*it)<<" ";
set<int>::reverse_iterator revIt;
for (revIt = decSet.rbegin(); revIt != decSet.rend(); revIt++)
cout<<(*revIt)<<" ";
}
int main(){
int bSeq[] = { 1, 4, 6, 5, 2, 1 };
int n = sizeof(bSeq) / sizeof(bSeq[0]);
int Q = 2;
int query[] = { 6, 5 };
calcBitonicSeqLenth(bSeq, n, query, Q);
return 0;
}실행 결과
For query 1: The length of Bitonic Sequence is 6 For query 2: The length of Bitonic Sequence is 7 The Bitonic Sequence at the end of all queries is : 1 4 5 6 5 2 1
위 코드는 C++ STL의 set 자료구조를 활용하여 중복 원소 관리와 정렬된 상태 유지를 효율적으로 처리합니다. 증가 집합과 감소 집합을 분리해 관리함으로써 각 쿼리마다 시퀀스 전체를 재구성하지 않고도 O(log N) 시간 안에 삽입 여부를 판단할 수 있다는 점이 이 접근 방식의 핵심 장점입니다.