백준#1138 - 한 줄로 서기

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

1138번: 한 줄로 서기

그리디 알고리즘으로 분류된 1138번 한 줄로 서기 문제 입니다.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace _1138
{
    class Program
    {
        
        static void Main(string[] args)
        {
            //사람수 입력받기.
            int lineLength = int.Parse(Console.ReadLine());
 
            //사람들의 왼쪽으로 큰 사람수 입력.
            string[] splitInput = Console.ReadLine().Split(' ');
 
            //줄을 세워 저장할 lineArray와 입력받은 인풋을 저장할 배열.
            int[] lineArray = new int[lineLength];
            int[] leftArray = new int[lineLength];
 
            //lineArray와 leftArray초기화.
            for (int i = 0; i < lineArray.Length; i++) 
            {
                lineArray[i] = -1;
                leftArray[i] = int.Parse(splitInput[i]);
            }
 
            for (int i = 0; i < leftArray.Length; i++)
            {
                int count = 0; //자신의 왼쪽 사람을 세는 변수.
                int countLine = leftArray[i]; //자신의 정해진 왼쪽 사람 수.
                for(int j = 0; j < leftArray.Length; j++)
                {
                    if(lineArray[j] == -1 && count == countLine)
                    {
                        lineArray[j] = i;
                        break;
                    }
                    if(lineArray[j] == -1)
                    {
                        count++;
                        continue;
                    }
                }
            }
            for (int i = 0; i < lineArray.Length - 1; i++)
                Console.Write((lineArray[i] + 1) + " ");
            Console.Write(lineArray[lineArray.Length - 1] + 1);
        }
    }
}
 

 

먼저 입력이 키가 작은 순서대로 주어지며 줄을 섰을 때 자기 왼쪽에 몇 명의 큰 사람이 있는지

키 순서대로 주어집니다.

 

줄을 어떻게 세워야 하는지 설명 드리겠습니다. 

 

ex) 7

왼쪽 수 : 3 5 2 0 2 0 0 이런 식으로 예시를 만들었습니다.

다음 줄을 세워놓을 배열을 하나 만들겠습니다.

줄 세움 : -1 -1 -1 -1 -1 -1 -1 저는 -1로 세팅했습니다.

 

1. 우선 첫번째 사람은 키가 가장 작습니다. 왼쪽에 어떤 사람이 오던 상관없이 왼쪽에 서있는 사람의 숫자가

곧 왼쪽의 자신보다 큰 사람 수가 되겠습니다. 그럼 첫 사람은 4번째 위치에 서야 합니다.

 

줄 세움 : -1 -1 -1 1 -1 -1 -1

첫번째 사람은 자기의 위치를 찾아갔습니다.

 

2. 두번째 사람은 1번 사람을 제외 하고는 모두 자신보다 키가 큽니다. 1번 사람은 이미 줄에 서있고

다음에 줄 서는 사람들은 모두 자기보다 키가 클 것입니다. 자기 왼쪽에 새로 줄을 서는 5명이 있어야 함을 의미하며

새로 줄을 서는 사람은 키가 크므로 5자리를 비워두고 줄을 서면 됨을 의미합니다.

 

줄 세움 : -1 -1 -1 1 -1 -1 2

두번째 사람은 자리를 찾아갔으며 앞으로 다섯개의 빈 자리가 있습니다.

 

3. 세번째 사람은 줄 서있는 1, 2번을 제외하고 다른 사람들보다 키가 작습니다. 새로 줄을 세워야 하는 사람보다

작으며 자신의 왼쪽에 2자리를 비워두면 되겠습니다.

 

줄 세움 : -1 -1 3 1 -1 -1 2

세번째 사람까지 줄을 잘 섰습니다.

 

이런 방식으로 마지막 사람까지 줄을 세우면 되겠습니다. 코딩은 상당히 귀찮으나 아이디어는 간단하니

꼭 직접 코딩 해보시길 바랍니다.