[백준_1138번] 한 줄로 서기

[문제]

 N명의 사람들은 매일 아침 한 줄로 선다. 이 사람들은 자리를 마음대로 서지 못하고 오민식의 지시대로 선다.

 어느 날 사람들은 오민식이 사람들이 줄 서는 위치를 기록해 놓는다는 것을 알았다. 그리고 아침에 자기가 기록해 놓은 것과 사람들이 줄을 선 위치가 맞는지 확인한다. 사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억한다. N명의 사람이 있고, 사람들의 키는 1부터 N까지 모두 다르다. 각 사람들이 기억하는 정보가 주어질 때, 줄을 어떻게 서야 하는지 출력하는 프로그램을 작성하시오.

 

[입력 조건]

•  첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 크거나 같고, N-i보다 작거나 같다. i는 0부터 시작한다.

 

[코드]

import java.util.*;

public class BaekJoon_1138 {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int[] result=new int[n];
		
		for(int i=1;i<=n;i++) {
			int count=sc.nextInt(); // 왼쪽에 위치한 사람 중 나보다 큰 사람의 수
			
			for(int j=0;j<n;j++) { // 모든 자리 탐색
				// 더이상 왼쪽에 나보다 큰 사람이 위치할 필요가 없고, 자리가 비었으면 해당 자리에 서기
				if(count==0&&result[j]==0) { 
					result[j]=i;
					break;
				}
				else if(result[j]==0) // 아직 왼쪽에 큰 사람이 위치해야 할 경우
					count--; // 사람수 줄여주기
			}
		}
		for(int i=0;i<n;i++)
			System.out.print(result[i]+" ");
	}

}

 

[고찰]

 이번 문제는 예시를 보면서 입력이 어떤 식으로 주어지는지 해석하는게 가장 어려웠다. 입력의 인덱스에 따른 값이 무엇을 의미하는지 해석만 하면 구현은 그리 어렵지 않았다. 

 입력은 입력 순서에 해당하는 번호를 가진 사람의 왼쪽에 자신보다 큰 사람의 수를 의미한다. 따라서 결과 값을 저장할 배열을 선언하고, 해당 배열을 처음부터 탐색해주면서 더이상 자신의 왼편에 큰 사람이 위치할 필요가 없으며 자리가 빈 곳에 위치시켜주면 된다.