[백준 2002] 추월

이 문제는 unordered_map을 사용하면 데이터를 읽고 쓰기 굉장히 쉽다

알고리즘보다는 초반 자료구조 선택이 굉장히 큰 비중을 차지하고 있는 것 같아 자료구조 부분에 넣어놓는다

 

일단 데이터 간 정렬이 필요하지 않는데

데이터들을 key-value 쌍으로 저장해야하긴 한다

왜냐하면 터널을 지나기 전에의 index와 터널을 지난 후의 index를 비교해야하기 때문이다.

 

따라서 unordered_map으로 O(1)의 최고효율 탐색을 통해 코드와 시간복잡도를 줄일 수 있다

초반에는 최장증가부분수열 문제인줄 알고 dp로 풀었으나 2%에 틀이 떠서 반례를 찾았다

(24.8.21 코테 감 다시 잡는다고 두번째 풀었을때도 LIS로 풀다 첫번째에 틀림...)

 

int lis() {
    for (int i = 0; i < N; i++) {
        dp[i] = 1;
        for (int k = 0; k < i; k++) {
            if (arr[i] > arr[k]) {
                dp[i] = max(dp[i], dp[k] + 1);
            }
        }
    }
    return dp[N - 1];
}

 

4

1234

4231

 

이렇게 하면 lis 사용하면 23이므로 답이 2(4-2)가 떠야한다

근데 사실 답은 3이다.

왜냐하면 423 이 추월한 차들이기 때문이다.

 

따라서 다시보아하니 추월이란 개념이 상대적인 것이다.

즉 내 뒤에 나보다 작은 놈이 있으면 나는 추월한 것이다.

 

따라서 내 뒤에 작은 놈이 있는지 없는지만 확인해주면 되는 것이었다.

 

---

#include <iostream>
#include <unordered_map>
#include <string>
#include <bitset>

#define SIZE 1001

using namespace std;

int N;
int arr[SIZE];
bitset<SIZE> visited;
unordered_map<string, int> um;

int ans = 0;

void solve() {
	int next = 1;
	for (int i = 1; i <= N; i++) {
		if (arr[i] > next) {
			ans++;
			visited[arr[i]] = 1;
		}

		else if (arr[i] == next) {
			visited[next] = 1;
			while (visited[next]) next++;
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N;

	string s;
	for (int i = 1; i <= N; i++) {
		cin >> s;
		um[s] = i;
	}

	for (int i = 1; i <= N; i++) {
		cin >> s;
		arr[i] = um[s];
	}

	solve();

	cout << ans;

	return 0;
}