[BaekJoon] 1138 한 줄로 서기

1.  문제 링크

2.  문제

요약

• N명의 사람이 한 줄로 서는데 각 사람이 자신보다 키가 큰 사람이 왼쪽에 몇 명이 있는지만 기억합니다. 이 정보를 보고 줄을 어떻게 서야 하는지 구합니다.
• 입력: 첫 번째 줄에는 사람의 수 N이 주어지고 두 번째 줄에는 키가 1인 사람부터 N인 사람까지 왼쪽에 본인보다 키가 큰 사람이 몇 명이 있는지 주어집니다.
• 출력: 줄을 선 순서를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	public ArrayList<Integer> getSequence(int[] seq) {
		ArrayList<Integer> sequence = new ArrayList<Integer>();
		sequence.add(seq.length);
		for(int i = seq.length - 2; i >= 0; i--) {
			sequence.add(seq[i], i + 1);
		}
		return sequence;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int num = Integer.parseInt(br.readLine());
		int[] seq = new int[num];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < seq.length; i++) {
			seq[i] = Integer.parseInt(st.nextToken());
		}
		br.close();
		Main m = new Main();
		ArrayList<Integer> sequence = m.getSequence(seq);
		for(int i = 0; i < sequence.size(); i++) {
			bw.write(sequence.get(i) + " ");
		}
		bw.flush();
		bw.close();
	}
}

4.  접근

• 자신보다 키가 큰 사람이 왼쪽에 몇 명이 있는지 주어지기 때문에 가장 키가 큰 사람부터 작은 순서로 줄을 세웁니다.
• 이 때, 이렇게 줄을 세우는 이유는 자신보다 키가 큰 사람이 몇 명이 왼쪽에 있는지 주어지므로 자신보다 작은 사람은 주어진 정보에 필요하지 않기 때문입니다.
• 큰 순서대로 세우면서 주어진 숫자만큼 큰 사람을 왼쪽에 놓은 후에 해당 자리에 해당 사람을 넣고 이 과정을 가장 작은 사람까지 진행하면 조건에 맞는 줄이 세워지게 됩니다.