[JAVA] [백준 1138] 한 줄로 서기

문제

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

어느 날 사람들은 오민식이 사람들이 줄 서는 위치를 기록해 놓는다는 것을 알았다. 그리고 아침에 자기가 기록해 놓은 것과 사람들이 줄을 선 위치가 맞는지 확인한다.

사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억한다. N명의 사람이 있고, 사람들의 키는 1부터 N까지 모두 다르다.

각 사람들이 기억하는 정보가 주어질 때, 줄을 어떻게 서야 하는지 출력하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄에 줄을 선 순서대로 키를 출력한다.

✨ Methodology

입력을 StringTokenizer로 받아놓은 후에 배열에 바로 저장하지 않고, 줄세우는 순서대로 저장한다.

1. 본인보다 큰 사람이 없을 경우

본인보다 큰 사람이 없는 경우는 count 가 0인 경우를 뜻한다.
만일, 본인보다 큰 사람이 더이상 없을 때에는 현재 칸에 아무도 없다면 그 자리에 줄을 서면 되고 만일 누군가 서있다면 다음칸에 서면 된다. 또, 그 다음칸에도 누가 이미 있다면 빈 칸 중 가장 가까운 칸에 서면 된다.
이는 입력받는 순서가 키순서이기 때문에, 이미 누군가 서있다면 본인보다 작은 사람이 서있는 중이기 때문에 빈 칸중 가장 가까운 칸에 서면 된다.

if(counts==0) { //본인보다 키가 큰 사람이 없다
//i는 키순서로 들어오기 때문에 본인보다 큰 사람이 없다면 그자리가 본인 자리임
    if(line[j]==0) {//자리에 아무도 없어서 줄 섰다.
		line[j] = i; 
		break;
        }
    else {//본인보다 큰 사람이 왼편에 없지만 이미 누군가 자기보다 작은 사람이 서있다 
		continue;    //양보하고 다른 빈칸중 가장 가까운곳에 서면 된다->다음 j로
	}
 }

2. 본인보다 큰 사람이 존재

본인보다 아직 큰 사람이 존재한다면, 다음 칸으로 넘어가면 된다 -> 현재칸이 비어있던 누군가 있던 큰 사람이 올 수 있는 공간이기 때문에 왼쪽에 있는 큰 사람을 세는 변수인 count를 감소 시키고 count 가 0이 될 때 까지 이동한다.

else if(line[j]==0) {//아직 count가 0이 아님-> 본인보다 큰 사람 존재하므로 다음칸으로 가보자
	counts--;
}

✨ 전체 소스 코드

package Silver;

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

public class BOJ_1138_한줄로서기 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine());//end of input
		
		int[] line = new int[N+1]; //줄에 선 순서
		for(int i = 1 ; i<= N ; i++) {
			int counts = Integer.parseInt(st.nextToken());//i: 본인 키, counts = 본인보다 왼쪽에 큰사람
			for(int j = 1; j<= N ;j ++) {
				if(counts==0) { //본인보다 키가 큰 사람이 없다-> i는 키순서로 들어오기 때문에 본인보다 큰 사람이 없다면 그자리가 본인 자리임
					if(line[j]==0) {//자리에 아무도 없어서 줄 섰다.
						line[j] = i; 
						break;
					}
					else {//본인보다 큰 사람이 왼편에 없지만 이미 누군가 자기보다 작은 사람이 서있다 -> 양보하고 다른 빈칸중 가장 가까운곳에 서면 된다
						continue;
					}
				}
				else if(line[j]==0) {//아직 count가 0이 아님-> 본인보다 큰 사람 존재하므로 다음칸으로 가보자
					counts--;
				}
			
			}
		}
		//Print Answer: 
		for(int i =1 ; i<=N ;i++) {System.out.print(line[i]+" ");}
	}
		
}