[문제풀이] - 섞기 전 카드 위치⭕

https://www.codetree.ai/training-field/search/problems/card-position-before-shuffling?&utm_source=clipboard&utm_medium=text

---

풀이

문제를 이해하는 것이 어려웠던 문제. 문제를 이해하고 나서는 괜찮게 풀 수 있었다.

이 문제에서 생각해야 할 것은 해당하는 순번과 값을 바꾼다는 것이다.

예를 들어서, 주어진 배열이 2 3 5 4 1 이면 1번째에 있는 수를 2번째에 넣는다는 것을 의미한다.

다만, 여기서 내가 오해했던 것은 서로간의 수를 스위칭하는 것이라고 착각한 것.

문제가 의도한 것은 첫번째 수를 배열 두번째 칸에 넣으시오.라는 의미였는데, 내가 의도한 것은 첫번째 수와 두번째 수를 서로 스위칭해서 바꾸시오라고 생각했다. 덕분에 예시와 맞지 않아서 큰 고민이 있었다.

뜻을 이해했다면 풀기는 쉽게 풀 수 있다.

1. 1부터 n까지 수가 들어가 있는 배열을 만든다.
2. 그 배열을 주어진 순서에 따라 3번 섞는다.
3. 최종적으로 나온 순서의 수열을 key 값으로 하고, 섞었을 때의 값을 value 값으로 하는 map을 만든다.
4. map에서 value값을 출력한다.

이때, map은 key와 value값을 가지고 있는 STL 연관 컨테이너로 중복을 허락하지 않는 것이 가장 큰 특징이다.

또한, 삽입, 삭제, 검색이 모두 O(log n)이 소요되는 레드블랙트리로 구성되어 있다.

그리고, map은 자동으로 key를 오름차순으로 정렬하기 때문에 따로 정렬을 할 필요 없이 삽입 후 value 값을 출력만하면 된다.

---

코드

코드는 다음과 같다.

#include <iostream>
#include <map> // map 해더파일
using namespace std;

int n, i, j;

// 섞인 숫자, 순서를 알려줄 배열, 임시 배열, 주어진 순서 배열
int num[101], original[101], temp[101], sec[101];

map<int, int> mp; 

int main()
{
	//freopen("input.txt", "r", stdin);
	cin >> n;
	
	for (i = 1; i <= n; i++)
		original[i] = i; // 초기화
	
	for (i = 1; i <= n; i++)
		cin >> sec[i];

	for (i = 1; i <= n; i++)
		cin >> num[i];

	for (i = 1; i <= 3; i++) { // 3번 반복
		for (j = 1; j <= n; j++) {
			int switchA = j, switchB = sec[j]; // 순서
			temp[switchB] = original[switchA]; // temp에 우선 넣는다.
		}

		for (j = 1; j <= n; j++)
			original[j] = temp[j]; // origin을 갱신
	}
	
    // 최종적으로 갱신된 origin을 key로 하는 map을 만든다.
    // 이때, value는 섞인 값.
	for (i = 1; i <= n; i++)
		mp.insert({ original[i], num[i] }); // 삽입

	for (auto iter = mp.begin(); iter != mp.end();  iter++)
		cout << iter->second << endl; // value값만 출력
	return 0;
}

---