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

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

1138번: 한 줄로 서기

 

난이도: solved.ac 실버 2

 

알고리즘 분류

구현

 

접근 방법

키가 가장 큰 N부터 1까지 자리를 배정해 주면 된다.

 

이때 자기의 왼쪽에 자신보다 키 큰 사람이 n명 있다고 하면, 현재 줄에서 맨 왼쪽 자리로부터 n만큼 떨어진 곳에 자리를 배정한다.

 

배치하려는 자리에 이미 사람이 있다면 해당 자리부터 그 오른쪽 사람들은 오른쪽으로 한 칸씩 밀고 배치한다.

 

이는 c++ vector의 insert를 이용하면 쉽게 구현할 수 있다.

 

코드

#include <bits/stdc++.h>
using namespace std;
int arr[10];
vector<int> loc;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, i;
	cin >> n;
	for (i = 0; i < n; i++)
		cin >> arr[i];
	for (i = n - 1; i >= 0; i--)
		loc.insert(loc.begin() + arr[i], i + 1);
	for (i = 0; i < n; i++)
		cout << loc[i] << ' ';
}

성능

코드 제출 결과