[2002] 추월 - 해쉬 ★★☆☆ / 복습 ○

[ 문제 ] : https://www.acmicpc.net/problem/2002

2002번: 추월

---

[ 문제 접근 ]

 

우선 문제를 보고 어려울것 같진 않았다.

 

queue나 stack, map 같은 자료구조를 쓰면 해결 할 수 있겠구나 싶었다.

 

문제는 어떤 자료구조를 쓰냐인데, 우선 저렇게 입력으로 문자열이 주어지는 경우는 경험상 map이 많았다.

 

문제를 보면 추월한 차량을 찾는 문제이기 때문에 추월했다는것을 어떻게 알 수 있을까를 고민해봤다.

 

쉽게 unordered_map<string,int>  차량 번호와 들어간 순서를 알면 나온 차량(key) 순서(value) 를 통해서 비교해 볼 수 있을것 같았다.

 

예를 들어  A (1)  B (2) C (3)  D(4)  순으로 차량이 집입 했다고 하자.

나오는 차량을 보니 D A B C 라면 D는 터널내에서 추월한 차량이다.

 

D(4) A(1) B(2) C(3) 에서 D가 추월한 차량인 이유는

 

idx인 4 뒤로 작은 숫자가 나오기 때문이다. 차량 진입은 4번째로 해놓고 나올땐 1,2,3 보다 빨리 나오면 추월이다.

 

---

[ 최종 코드 ]

 

#include <iostream>
#include<string>
#include <vector>
#include<algorithm>
#include<unordered_map>

using std::cout; using std::cin;
using std::vector;

int n;
std::unordered_map<std::string, int> um;
vector<int> output;
int cnt;

int main(){
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> n;

	for (int i = 0; i < n; i++) {
		std::string car;
		cin >> car;
		um.insert({ car, i + 1 });  // 차량 번호, 들어간 idx;
	}

	for (int i = 0; i < n; i++) {
		std::string car;
		cin >> car;
		output.push_back(um[car]);  // 4 3 2 1 같이 진입 idx 
	}
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (output[i] > output[j]) {
				cnt++;
				break;
			}
		}
	}
	cout << cnt;

	return 0;
}

---

[ Key Point ]

 

👉  로직을 이해하기만 하면 구현은 어렵지 않았던 문제이다. 생각하는 힘!! 중요하다.

 

---