[Problem Solving] BOJ 1138 : 한 줄로 서기

문제 링크 : https://www.acmicpc.net/problem/1138

 

입력이 2 1 1 0 이라면,

1번 왼쪽에는 1보다 큰 수 2개,

2번 왼쪽에는 2보다 큰 수 1개,

3번 왼쪽에는 3보다 큰 수 1개,

4번 왼쪽에는 4보다 큰 수 0개

가 되도록 1 2 3 4를 줄 세워야 한다.

 

v = {2, 1, 1, 0}

s = {1, 2, 3, 4}

가 있다고 하자.

 

s[i]오른쪽으로 옮기며 대소비교를 하며, s[i] 보다 큰 값을 v[i]번 발견하여 자리를 바꿔주는 식으로 해결할 수 있다.

 

{1, 2, 3, 4}

-> {2, 1, 3, 4}

-> {2, 3, 1 ,4} (2번의 swap을 거쳐 1 옮기기 완료)

-> {3, 2, 1, 4} (1번의 swap을 거쳐 2 옮기기 완료)

-> {4, 2, 1, 3} (1번의 swap을 거쳐 3 옮기기 완료)

-> {4, 2, 1, 3} (0번의 swap을 거쳐 4 옮기기 완료)

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
#include <algorithm>
#include <stack>
#include <set>
#include <cmath>
#include <climits>
#define endl '\n'
using namespace std;

int N;
vector<int> v;
vector<int> s;

void input()
{
    cin >> N;
    v.resize(N + 1, 0);
    s.resize(N + 1, 0);

    for (int i = 1; i <= N; i++)
    {
        cin >> v[i];
    }
    for (int i = 1; i <= N; i++)
    {
        s[i] = i;
    }
}

void ele_swap(int a, int b)
{
    int temp = s[a];
    s[a] = s[b];
    s[b] = temp;
}

void solution()
{
    for (int i = 1; i <= N; i++)
    {
        int n;
        for (int j = 1; j <= N; j++)
        {
            if (i == s[j])
            {
                n = j; // i가 s에서 몇번째에 있는지 찾기
                break;
            }
        }

        int cnt = 0;
        for (int j = n + 1; j <= N; j++)
        {
            if (cnt == v[i])
                break;
            if (s[n] < s[j])
            {
                ele_swap(n, j);
                n = j;
                ++cnt;
            }
        }
    }
}

void output()
{
    for (int i = 1; i <= N; i++)
    {
        cout << s[i] << " ";
    }
    cout << endl;
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    input();
    solution();
    output();

    return 0;
}