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

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

1138번: 한 줄로 서기

 

1. 문제 설명

 

왼쪽에 자기보다 키 큰 사람이 몇 명이 있었는지 주어졌을 때 줄을 어떻게 서야 할지 출력하는 문제이다.

 

키가 작은 순서부터 입력을 받아서 각 사람의 위치 n이 주어지면 이미 사람이 서있는 자리는 제외하고 n번째 자신의 위치에 배치하도록 풀 수 있다.

 

아래 코드는 시간복잡도 O(n^2)이다. 줄이고 싶었지만 다른 방법을 찾지 못했다.

 

 

2. 코드

#include <iostream>

using namespace std;

int main()
{
    
    int num;
    
    cin >> num;
    
    int *person=new int[num];
    int *arr=new int[num]{0,};
    
    for(int i=0;i<num;i++)
    {
        cin >> person[i];
        
        int x=-1;
        
        while(person[i]>=0)
        {
            x++;
            
            if(arr[x]==0)
                person[i]--;
            
        }
       
        
        arr[x]=i+1;
        
    }
    
        
    for(int i=0;i<num;i++)
        cout << arr[i] <<" ";

    return 0;
}