백준 2002 c++ "추월" -PlusUltraCode-

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

 

[필자 사고]

와 2시간 만에 해결한 문제이다.

답을 볼 수도있었지만 몰입이라는 책에서 말해주듯이 계속 생각했다.

그러다가 과부화가와서 밥을 먹고 릴렉스 된 상태에서 문제를 다시보니 해결할 수 있었다.

 

핵심은 간단하다. 

이전 순서를 저장하는 vector 배열이 있고

이후 변경된 myMap형태로 순서를 넣었다.

 

그리고 브루스트알고리즘을 이용하여 for문 전체탐색으 진행했고
만약 탐색한 지역이 있따면 visited를 통해 방문 처리를 했다.

갱신작업은 현재 문자열의 미래 인덱스와 다음 문자열의 미래인덱스의 순서가 바껴져 있으면 갱신하는 법으로 문제를 해결했다.

 

아래는 자세한 코드 해설이다.

[코드 해설]

1. 입력 처리 (Input 함수)

Input() 함수는 사용자로부터 두 번에 걸쳐 문자열을 입력받습니다.

• 첫 번째 입력에서는 arr 벡터에 문자열을 저장하며, 이는 문자열의 원래 순서를 나타냅니다.
• 두 번째 입력에서는 map<string, int> myMap에 문자열과 그에 해당하는 새로운 순서 인덱스를 저장합니다.
  즉, 같은 문자열 집합에 대해 두 가지 다른 순서 정보를 저장하는 구조입니다.

---

2. 게임 로직 수행 (Game_Start 함수)

Game_Start() 함수는 arr의 순서를 기준으로 두 문자열 쌍 (i, k)에 대해 상대 순서가 바뀌었는지를 판별합니다.

• visited 벡터는 중복 계산을 방지하기 위해 사용됩니다.
• 이중 for문을 통해 i < k인 모든 문자열 쌍을 검사하며:
  • arr[i]가 나중에 오고, arr[k]가 먼저 오는 경우 (nextPos < nowPos)
  • 그리고 arr[k]가 아직 처리되지 않은 경우 (visited[nextPos] == false)
  • 이 경우 순서가 뒤바뀐 경우로 간주하여 resultCount를 증가시키고, 해당 위치를 방문 처리합니다.
• 최종적으로 resultCount는 상대 순서가 역전된 쌍의 수를 의미합니다.

---

3. 메인 함수 (main)

main() 함수는 단순히 Input()으로 입력을 받고, Game_Start()를 호출하여 게임의 결과를 계산하고 출력합니다.

[소스 코드]

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

using namespace std;

int N;
vector<string> arr;
map<string, int> myMap;
vector<bool> visited;
void Input() {
	cin >> N;
	arr.resize(N + 1);
	for (int i = 1; i <= N; i++) {
		string str;
		cin >> str;
		arr[i] = str;
	}
	for (int i = 1; i <=N; i++) {
		string str;
		cin >> str;
		myMap[str] = i;
	}
}

void Game_Start() {
	visited.resize(N + 1, false);
	int resultCount = 0;
	for (int i = 1; i < N; i++) {
		for (int k = i + 1; k <= N; k++) {
			string nowStr = arr[i];
			string nextStr = arr[k];
			int nowPos = myMap[nowStr];
			int nextPos = myMap[nextStr];

			if (visited[nextPos] == true)continue;

			if (nextPos < nowPos) {
				resultCount++;
				visited[nextPos] = true;
			}
		}
	}

	cout << resultCount;
}

int main(void) {
	Input();
	Game_Start();
}