[백준] 1138 한 줄로 서기

1. 문제

www.acmicpc.net/problem/1138

1138번: 한 줄로 서기

2. 접근방법

키 순서대로 내 앞에 나보다 큰 사람이 몇명 있는지 입력으로 주어진다.

 

즉 그냥 내 앞에 나보다 큰 사람들이 들어올 자리만큼 비워주고 그 다음 자리에 내가 서면 된다.

 

예제를 보면

 

1번 앞에 자기보다 큰 사람 2명이 있어야 하니

자기보다 큰 사람 2명이 설 자리를 놔두고 3번째 자리에 들어가면 된다.

만약 4번째 자리에 가게 되면

나머지 사람들이 다 나보다 키가 크니 내 앞에 키 큰 사람 3명이 되어서 불가능하다.

 

그 다음으로 2번 앞에 1명이 있어야하니

한자리를 비우고 

3번 앞에도 1명이 있으니

한자리를 비우고 그 다음 빈자리로 들어간다.

마지막으로 4번은 앞에 0명이니

남은 자리로 바로 들어가면 된다.

3. 자바 코드

package Silver;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class P1138한줄서기 {
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int arr[] = new int[N];
		boolean visit[] = new boolean[N];
		st = new StringTokenizer(br.readLine());
		for(int i = 0 ; i < N ; i++) {
			int n = Integer.parseInt(st.nextToken());
			int cnt = 0;
			for(int j = 0 ; j < N ; j++) {
				if(!visit[j]) {
					if(cnt == n) {
						visit[j] = true;
						arr[j] = i+1;
						break;
					}
					cnt++;
				}
			}
		}
		StringBuilder sb = new StringBuilder();
		for(int i = 0 ; i < N ; i++)
			sb.append(arr[i]+" ");
		System.out.println(sb);
	}

}

4. 마치며

나쁘지 않은 문제였다.