백준 10431 줄세우기 (Java)

1. 문제 링크

10431번: 줄세우기

 

2. 문제 및 입출력예제

 

3. 문제 풀이

20명을 차례대로 줄 세우는 문제이다.

list(height)를 만들어서 학생 한 명씩 넣는 과정에서 list에서 지금 입력값보다 큰 값이 나오는 순간의 인덱스를 구한다.

그렇게 하면 뒤로 한 걸음씩 물러서야 하는 학생의 수를 전체 list의 크기 - 현재 인덱스 -1이 된다.

그 과정을 반복하면 답이 나온다.

 

4. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new java.io.InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		for(int t=1;t<T+1;t++) {
			sb.append(t+" ");
			List<Integer> height = new ArrayList<>();
			String[] split = br.readLine().split(" ");
			
			int where, cnt = 0;
			height.add(Integer.parseInt(split[1]));
			
			for(int i=2;i<21;i++) {
				int now = Integer.parseInt(split[i]);
				
				where = -1;
				for(int j=0;j<i-1;j++) {
					if(height.get(j)>now) {
						where = j;
						break;
					}
				}
				if(where == -1) { //다 작았을 때
					height.add(now);
				}
				else {
					height.add(where, now);
					cnt += height.size()-where-1;
				}
			}
			sb.append(cnt).append("\n");
		}
		System.out.println(sb);
	}	
}