Notice
Recent Posts
Recent Comments
Link
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
Archives
Today
Total
관리 메뉴

차근차근

[백준 2002] 추월 본문

대학교/Algorithm

[백준 2002] 추월

SWKo 2020. 2. 24. 14:36

0. 제목

  • 백준 2002 추월
  • BOJ 2002 추월
  • C++ 2002 추월

1. 문제

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


2. 풀이

  • 추월 여부를 확인해주는 함수를 작성하였다. 인자로 들어오는 vector는 추월한 차들이 원소로 들어있는 vector이다. 그 vector와 문자열 s를 비교하여 있으면 true를, 없으면 false를 반환해준다.
  • main함수에서 들어오는 차들이 담겨있는 v1의 인덱스를 idx1로 놓고 나가는 차들이 담겨있는 v2의 인덱스를 idx2로 놓는다.
  • 비교를 실시하여 같으면 인덱스를 하나씩 증가시켜준다.
  • 다르다면 v1[idx1] 값이 추월vector에 속해있는지 검사한다.
  • 속해있으면 idx1을 1증가해주고, 속해있지 않으면 v2[idx2]를 v3에 넣어주고 idx2와 추월차량의 개수를 1씩 증가시켜준다.
  • idx1과 idx2가 각 vector의 size보다 모두 작은 동안 반복을 한다.
  • 루프를 빠져나오면 추월차량의 개수를 출력한다.

3. 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <vector>
using namespace std;
 
vector<string> v1;//들어오는 차
vector<string> v2;//나가는 차
vector<string> v3;//추월한 차
 
//추월여부 확인
bool isOvertake(string s, vector<string> &v){
    for(int i = 0; i < v.size(); i++)
        if(s == v[i])
            return true;
    return false;
}
 
int main(int argc, const char * argv[]) {
    int N;
    string str;
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> str;
        v1.push_back(str);
    }
    for(int i = 0; i < N; i++){
        cin >> str;
        v2.push_back(str);
    }
    
    int idx1 = 0, idx2 = 0;
    int ans = 0;
    while(idx1 < v1.size() && idx2 < v2.size()){
        if(v1[idx1] == v2[idx2]){
            idx1++;
            idx2++;
        }
        else{
            if(isOvertake(v1[idx1], v3))
                idx1++;
            else{
                v3.push_back(v2[idx2]);
                idx2++;
                ans++;
            }
        }
    }
    cout << ans << '\n';
    
    return 0;
}
 
 
 

'대학교 > Algorithm' 카테고리의 다른 글

[백준 1764] 듣보잡  (0) 2020.02.24
[백준 6581] HTML  (0) 2020.02.24
[백준 1094] 막대기  (0) 2020.02.23
[백준 1065] 한수  (0) 2020.02.23
[백준 1922] 네트워크 연결  (0) 2020.02.23
Comments