백준 30805 c++ "사전 순 최대 공통 부분 수열" -PlusUltraCode-

https://www.acmicpc.net/problem/30805

 

[필자 사고]

일단 사전순에서 가장 느리게 되려면 앞 부분에 가장 큰수가 와야 된다.

이러한 사고과정의 형태로 정렬을 이용할 수 있ㄷ.

 

두번째 문제 해당 부분은 수열이다. 공통 부분 수열은 인덱스 순서를 중요시 한다.

그래서 같은 숫자일 경우 인덱스가 작은거 먼저 와야 더 늦은 사전 순을 만들 수 있다.

 

만든 배열을 잘 정렬한 뒤 이제 i,j를 이용하여 각 idx의 값들을 비교해야 한다.

같은 경우 resultArr에 값을 넣고 lastIdx 도 갱신해준다.

 

나머지 부분은 첫번째 배열 수보다 두번째 배열 수가 크거나 작다면 갱신해주고 또한 lastIdx보다 작은 인덱스라면 

\검사할 필요없이 바로 인덱스를 증가시키는 형태로 해당 문제를 풀었다.

[코드 해설]

2. 두 시퀀스 비교 및 결과 추출 (Game_Start 함수)

Game_Start() 함수는 arr1과 arr2 두 시퀀스를 탐색하며 조건에 맞는 공통 원소를 추출하는 로직을 수행합니다.

먼저 i, j 두 포인터를 0으로 초기화하여 각각 arr1, arr2의 현재 탐색 위치를 나타냅니다.
또한, lastIdx1, lastIdx2는 직전에 매칭된 원소의 인덱스를 기억하기 위한 변수이며, 초기값은 -1입니다.

while 루프를 통해 두 시퀀스를 끝까지 탐색하며 다음 조건을 평가합니다:

• arr1[i].first > arr2[j].first 또는 arr1[i].second < lastIdx1이면 i 증가
  → 현재 arr1[i]가 너무 크거나, 이미 사용된 인덱스보다 앞에 있는 경우 건너뜀
• arr2[j].first > arr1[i].first 또는 arr2[j].second < lastIdx2이면 j 증가
  → arr2[j]가 너무 크거나, 이전 인덱스보다 앞이면 건너뜀
• 그렇지 않다면, 두 원소의 값이 같고, 정렬 순서상 조건도 맞으면
  → arr1[i].first를 결과 벡터에 추가하고, lastIdx1, lastIdx2를 현재 인덱스로 갱신한 뒤 i, j 모두 증가

이렇게 함으로써 두 정렬된 시퀀스에서 공통된 값을 조건에 맞게 순서대로 추출하게 됩니다.

마지막으로, 결과 벡터의 크기(= 매칭된 원소 수)를 출력하고, 결과 벡터의 내용을 공백으로 구분하여 출력합니다.

[소스 코드]

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

int N, M;
typedef pair<int, int> Node;
vector<Node> arr1, arr2;

bool cmp(Node a, Node b) {
	if (a.first == b.first) {
		return a.second < b.second;
	}
	return a.first > b.first;
}

void Input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		arr1.push_back({ num ,i});
	}

	cin >> M;
	for (int i = 0; i < M; i++) {
		int num;
		cin >> num;
		arr2.push_back({ num ,i});
	}
	sort(arr1.begin(), arr1.end(), cmp);
	sort(arr2.begin(), arr2.end(), cmp);
}

void Game_Start() {
	int i = 0, j = 0;
	int lastIdx1 = -1, lastIdx2 = -1;
	vector<int> resultArr;

	while (i < N && j < M) {
		if (arr1[i].first > arr2[j].first || arr1[i].second < lastIdx1) {
			++i;
		}
		else if (arr2[j].first > arr1[i].first || arr2[j].second < lastIdx2) {
			++j;
		}
		else {
			resultArr.push_back(arr1[i].first);
			lastIdx1 = arr1[i].second;
			lastIdx2 = arr2[j].second;
			++i;
			++j;
		}
	}

	cout << resultArr.size() << '\n';
	for (int x : resultArr) {
		cout << x << ' ';
	}
	
}

int main(void) {
	Input();
	Game_Start();
}