[백준] 1138 한 줄로 서기 C++

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

 

해설

오민식의 방법대로 한 줄로 세우면 되는 문제이다.

입력과 출력문을 보면서 이해를 했는데, 2 1 1 0 으로 입력을 받는 경우 1번 사람 왼쪽에는 2명의 큰 사람이 있기 때문에 2번만큼 오른쪽으로 큰 사람이 나올 때 까지 swap을 해주면된다.

모든 사람에 대해서 swap을 1번 부터 4번까지 위처럼 해주게 되면 4 2 1 3과 같은 한 줄이 나오게 된다.

 

코드

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <stack>
#include <sstream>
#include <set>
#include <unordered_set>
#include <cmath>

using namespace std;
using ll = long long;
#define endl "\n"

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	vector<int> v;
	int n; cin >> n;
	for (int i = 0; i < n; ++i) v.push_back(i + 1);
	for (int i = 1; i <= n; ++i) // i는 시작 번호
	{
		int moveCnt = 0; cin >> moveCnt;
		int idx = 0;
		for (int j = 0; j < v.size(); ++j)
		{
			if (v[j] == i)
			{
				idx = j; // 1 2 3 4 중에 해당 루프에 해당하는 번호를 찾는다
				break;
			}
		}
		while (moveCnt > 0) // 입력받은 횟수 만큼 swap을 수행하도록 한다.
		{
			for (int j = idx + 1; j < v.size(); ++j)
			{
				if (v[idx] < v[j])
				{
					swap(v[idx], v[j]);
					moveCnt--;
					idx = j;
					break;
				}
			}
		}
	}
	for (int a : v) cout << a << " ";
	return 0;
}

 

 

다른 풀이 참고

https://yoon-1212.tistory.com/117

[C++][백준 1138] 한 줄로 서기