[C++] 백준 2002 문제 해설

2002번: 추월

처음에는 별생각없이 풀었고, 나중에 다들 map 을 쓴다는걸 알게되어서 추가하였다.

두가지 버전 모두 첨부한다.

map(X)

#include <iostream>
#include <vector>

int main()
{
	int N;
	bool visited[1000] = {false, };
	std::vector<std::string> input;
	std::vector<std::string> output;

	std::cin >> N;
	std::string temp;

	// 입력 로직
	for(int i = 0; i < N; ++i)
	{
		std::cin >> temp;
		input.push_back(temp);
	}

	for(int i = 0; i < N; ++i)
	{
		std::cin >> temp;
		output.push_back(temp);
	}
	
	// 최종 출력될 count
	int count = 0;

	// index_output 은 output vector 를 뒤에서부터 진입함.
	int index_output = N-1;

	for(int index_input = N-1; index_input >= 0; --index_input)
	{
		while(visited[index_output] == true)
		{
			index_output -= 1;
		}

		if(input[index_input] != output[index_output] && visited[index_output] == false)
		{
			++count;

			for(int z = index_output; z >= 0; --z)
			{
				if(input[index_input] == output[z])
				{
					visited[z] = true;
					break;
				}
			}
		}
		else
		{
			visited[index_output] = true;
			index_output -= 1;
		}
	}

	std::cout << count;
}

예를들어 아래와 같은 입력이 있다고 생각 해 보자, 왼쪽은 input 이고, 오른쪽은 output 이다.

총 20개의 예제이며, 정답은 16이다.

# 20 / 16
# 66G776P8  24446M23
# 361517    66G776P8
# X20G2M    X20G2M
# AO6C4D    AO6C4D
# V8O717LM  47B6322B
# 47B6322B  V8O717LM
# 1280DH03  E75828
# 4AI1AC7   4AI1AC7
# A3G550    A3G550
# 38586T25  465HQ54
# E75828    G1288Y1
# 3M200VPN  3M200VPN
# 7M02R0G0  7M02R0G0
# 877F43    877F43
# 24446M23  361517
# 465HQ54   38586T25
# 5013DC12  5013DC12
# 525745    525745
# G1288Y1   1280DH03
# 7005B8    7005B8

어떤 차가 추월했는지 쉽게 파악이 가능하다.

좌측(input)과 우측(output)을 비교하며 나아가는 방식이다.

for(int z = index_output; z >= 0; --z)
{
	if(input[index_input] == output[z])
	{
		visited[z] = true;
		break;
	}
}

만약 N의 사이즈가 커진다면, 해당 코드에서 시간제한 문제가 생길 가능성이 크다.

물론 문제에서 주어진 1000개 분량에서는 문제가 생기지 않았다.

 

이러한 문제를 예방하고자 map 을 사용할 수 있고,

아래와 같이 수정하였다.

map(O)

#include <iostream>
#include <vector>
#include <map>

int main()
{
	int N;
	std::cin >> N;

	std::vector<std::string> input;
	std::vector<std::string> output;
	std::map<std::string, bool> visited;

	std::string temp;

	// 입력 로직
	for(int i = 0; i < N; ++i)
	{
		std::cin >> temp;
		input.push_back(temp);
		visited.insert(std::pair<std::string, bool>(temp, false));
	}

	for(int i = 0; i < N; ++i)
	{
		std::cin >> temp;
		output.push_back(temp);
	}
	
	// 최종 출력될 count
	int count = 0;

	// index_output 은 output vector 를 뒤에서부터 진입함.
	int index_output = N-1;

	for(int index_input = N-1; index_input >= 0; --index_input)
	{
		while(visited[output[index_output]])
		{
			--index_output;
		}

		visited[input[index_input]] = true;
		
		if(input[index_input] == output[index_output])
		{
			--index_output;
		}
		else
		{
			++count;
		}
	}

	std::cout << count;
}