-
백준(BOJ) 2002번 추월알고리즘 풀이/백준(Boj) 2020. 3. 9. 17:00
문제 :
https://www.acmicpc.net/problem/2002
2002번: 추월
문제 대한민국을 비롯한 대부분의 나라에서는 터널 내에서의 차선 변경을 법률로 금하고 있다. 조금만 관찰력이 있는 학생이라면 터널 내부에서는 차선이 파선이 아닌 실선으로 되어 있다는 것을 알고 있을 것이다. 이는 차선을 변경할 수 없음을 말하는 것이고, 따라서 터널 내부에서의 추월은 불가능하다. 소문난 명콤비 경찰 대근이와 영식이가 추월하는 차량을 잡기 위해 한 터널에 투입되었다. 대근이는 터널의 입구에, 영식이는 터널의 출구에 각각 잠복하고, 대근이는 차
www.acmicpc.net
풀이 :
해쉬 맵을 통해 각 차량이 들어온 번호와 순서를 적어두자 < String, Int >
이제 나온 번호를 보면서 해당 차량에 입구 순서가 그 뒤에 있는 차량들에 입구 순서보다 늦은 순서라면 추월한
차량이기에 +1을 해주고 이를 각 차량에 대해서 반복해주면 된다.
코드 (C ++)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters#include <string> #include <iostream> #include <unordered_map> #include <vector> using namespace std; int main() { int n; cin >> n; unordered_map<string, int> m; for (int i = 0; i < n; ++i) { string s; cin >> s; m[s] = i; } vector<string> v(n); int cnt = 0; for (int i = 0; i < n; ++i) { cin >> v[i]; } for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (m[v[i]] > m[v[j]]) { cnt += 1; break; } } } cout << cnt << "\n"; return 0; } '알고리즘 풀이 > 백준(Boj)' 카테고리의 다른 글
백준(BOJ) 16986번 인싸들의 가위바위보 (0) 2020.03.13 백준(BOJ) 1194번 달이 차오른다, 가자. (0) 2020.03.12 백준(BOJ) 1175번 배달 (0) 2020.03.08 백준( BOJ ) 16236번 아기 상어 (0) 2020.02.24 백준 BOJ(1062) 가르침 (2) 2020.02.22