[백준] 1138번 한 줄로 서기 (java, 구현)

www.acmicpc.net/problem/1138

1138번: 한 줄로 서기

자신의 번호가 들어갈 수 있는 배열을 하나 만든다(0 초기화)

 

그리디 탐색으로 보고있는 자리가 비워져있다면 나보다 큰 사람이 들어갈 곳으로 판단해서 cnt를 1감소시킨다.

 

cnt가 0이라 나보다 큰 애는 없어도 자리가 비워져있지 않다면 나보다 작은 친구가 들어간 곳이다. 다음 공간을 본다.

 

cnt도 0이고 현재 공간이 0이면 내가 들어갈 자리이다. 

 

import java.util.Scanner;

public class Main {
	static int n,cnt;
	static int[] arr;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		arr=new int[n];
		for (int i = 1; i <=n; i++) {
			cnt=sc.nextInt();// 나보다 큰 사람수
			for (int j = 0; j < n; j++) {
				if(cnt==0 && arr[j]==0) {//cnt가 0이지만 arr[j]가 0이 아니면 나보다 작은사람인 거다.
					arr[j]=i;
					break;
				}else if(arr[j]==0) {//나보다 큰 사람이 들어가는 위치라면
					cnt--;//나보다 큰 사람 수를 줄여준다.
				}
			}
			
		}
		
		for (int i = 0; i < n; i++) {
			System.out.print(arr[i]+" ");
		}
	}
}