[알고리즘 스터디] 5주차 활동 기록

GDCS 알고리즘 스터디 5주차(05/08) 활동 기록입니다.
5주차에는 맵를 이용한 간단한 문제인 백준 2002번 추월 문제에 대한 풀이를 공유하였습니다.

 

문제

 

예제

//예제 입력
ZG431SN
ZG5080K
ST123D
ZG206A
ZG206A
ZG431SN
ZG5080K
ST123D

 

//예제 출력
1

 

문제 정리

터널을 들어갈 때, 나올 때의 차량 목록이 주어질 때, 터널 안에서 반드시 추월했을 것이라고 여겨지는 차량의 수를 구해야 한다. 

 

문제 접근

• 초기 접근 방법
  • 차량 목록을 단순 비교해서 원래 순서(몇 번째 차량인지)보다 먼저 터널을 빠져나오면 추월한 것으로 체크
  • 틀린 이유 : 원래 차량이 가지고 있던 번호(앞에서 부터 몇 번째 차량인지)와 같거나 더 늦게 터널을 빠져나와도 반드시 추월한 것으로 볼 수 있는 케이스가 존재함
  • 접근 방법 개선 : 단순히 어떤 차량이 몇번째 순서인지를 체크하는게 아니라 어떤 차량들 사이에 위치하는지가 중요하기 때문. 즉, 들어가고 나갈 때 앞에서부터 몇 번째인지와 무관하게 차량들간의 선후관계가 중요함.

//초기 접근 방법 반례
//터널 들어간 순서
a
b
c
d

//터널 나온 순서
c
b
a
d

//b는 원래도 두번째로 들어가고 두번째로 나왔지만 b보다 터널에 먼저 들어간 a보다 먼저 터널을 나왔으므로
//반드시 추월했음을 알 수 있음.

• 새로운 접근 방법
  • 터널을 나온 차량 목록을 차례로 방문
  • 방문한 차량보다 나중에 터널을 나온 차량들의 들어온 순서를 확인
  • 하나라도 해당 차량보다 먼저 터널에 들어갔다면 해당차량은 반드시 추월했음을 알 수 있음. 
  • 터널을 나온 차량목록의 차량 번호(string)를 통해서 터널에 들어간 순서를 알 수 있어야함 + 차량 번호는 중복 x 👉 터널 들어간 차량목록은 map에 저장하는 것이 적절함. 
  • 터널 나온 차량 목록은 입력되는 순서대로 차례로 접근해야함 👉 터널 나온 차량목록은 vector에 저장하는 것이 적절함. 
  • 시간 복잡도 : O(n^2) , n은 최대 1000, 시간제한은 2초 => 최대 입력 가능한 n이 작아서 시간제한 내에 해당 접근으로 문제 해결 가능

 

2002번 코드

//2022.05.07
//boj 2002 추월 문제(실버 1)
//boj.kr/2002
#include <bits/stdc++.h>
using namespace std;

int main(void)
{
    ios::sync_with_stdio(false);
	int n;
	cin >> n;
	
	map<string, int> carsIn;
	vector<string> carsOut(n);
	
	//터널 들어가는 순서 맵에 저장
	for (int i = 0; i < n; i++)
	{
	    string s;
	    cin >> s;
	    carsIn[s] = i;
	}

	int result = 0;
	
	//터널 나온 순서 vector에 저장
	for (int i = 0; i < n; i++)
	    cin >> carsOut[i];
	
    //추월차량 계산
	for(int i = 0; i<n; i++)
	{
	    for(int j =i+1; j<n; j++)
	    {
	        if(carsIn[carsOut[i]] > carsIn[carsOut[j]])
	        {
	            result++;
	            break;
	        }
	    }
	}
	cout << result;
}