사전 순 최대 공통 부분 수열 성공 C++

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

문제는 백준에서 읽을 수 있습니다.

해당 문제는 solved.ac에서 4 클래스 문제를 다 풀기 위해서 문제를 해결하려고 했으나, 너무 오래 걸렸다.

문제에서는 해당 부분을 주의 깊게 보면 좋다. 처음에 봤을 때 무슨 말인지 감이 안 왔다.

예제 값과 문제의 설명을 함께 본다면, 무조건 큰 값이 앞에 오면 된다는 내용을 이해할 수 있다.

그러니까 크게 문제의 시간 복잡도도 그렇게 높지도 않기 때문에 DP까지 갈 필요가 없는 문제이기도 하고, 무조건 공통 값 중 큰 값이 앞으로 오면 된다는 점을 착안해서 문제를 풀 수 있다.

내가 오래걸린 문제

일단 다른 사람들의 해결 방법을 보았을 때 살짝 어지러웠다. 문제에서는 공통 값 중 큰 값 순으로 나열하면 된다는 생각이 크게 뇌를 지배하고 있는데, 다들 투 포인터 기법을 곁들여서 공통의 값을 찾아나갔다.

여기까지는 이해할 수 있는 부분인데, 배열을 지워나가는 행위까지 포함되어 있었다.

상당히 복잡해진 느낌이라 왜 이렇게까지 해야하나 싶었다.

질문 게시판에 가면 다른 예제도 볼 수 있다.

여기서 확인할 수 있는 부분은 두 배열에 공통된 수가 있는 경우, 어떻게 처리하는지 놓치지 말자란 생각이 들 수 있다.

하여튼.. 배열은 건드리고 싶지 않고, 공통된 수만 보고 싶다는 내 니즈에 코드를 닦았다가 이상한 조건을 하나 달았다가 된통 오래 걸렸다.

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

int main() {

    int n, m;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    
    cin >> m;
    vector<int> b(m);
    for (int i = 0; i < m; i++) cin >> b[i];
    
    vector<pair<int, pair<int, int>>> commonNumber;
    
    for(int i=0; i<n; i++) {
    	for(int j=0; j<m; j++) {
    		if(a[i] == b[j]) {
    			commonNumber.push_back({ -a[i], { i, j } });
    		}
    	}
    }
    
    sort(commonNumber.begin(), commonNumber.end());
    
    vector<pair<int, pair<int,int>>> ans;
    for(int i=0; i<commonNumber.size(); i++) {
    	if(ans.size() == 0) {
    		ans.push_back(commonNumber[i]);
    	} else {
    		if(
                -ans[ans.size()-1].first >= -commonNumber[i].first 
            &&  ans[ans.size()-1].second.first < commonNumber[i].second.first
    		&& ans[ans.size()-1].second.second < commonNumber[i].second.second
    		) {
    			ans.push_back(commonNumber[i]);
    		}
    	}
    }
    
    cout << ans.size() << "\n";
    for(int i=0; i<ans.size(); i++) {
    	cout << -ans[i].first << " ";
    }
    
    return 0;
}

1. 공통된 값을 찾고, 값 순으로 정렬한다.
2. answer 배열이 비어 있으면 값을 추가하거나 Answer의 마지막 요소의 인덱스를 A, B 배열의 인덱스확인해서 값을 추가한다.

코드는 굉장히 간단한 흐름을 가지고 있다.

위 코드에서 이상한 점을 찾았을까?

                -ans[ans.size()-1].first >= -commonNumber[i].first 

위 코드는 불필요하다.

이미 공통 값을 가진 배열이 내림차순 정렬이 되어 있기 때문이다.

또한 나는 >=에서 =를 빼먹어서 계속 틀렸다. 결국.. 잘 몰랐다는 점을 상기할 수 있었다.