(JAVA) 백준 1138번 : 한 줄로 서기

https://www.acmicpc.net/problem/1138

1138번: 한 줄로 서기

 

 

그리디 알고리즘 방식인데

순열 구하는 방법(LinkedList)과 똑같이 사용했다.

(다음에 시간되면 포스팅해보겠다....!!!!!)

 

 

 

매커니즘

---

사람의 수를 N이라고 한다.

 1) 그래서 0 ~  N-1 까지의 수를 순서대로 하나씩 LinkedList<Integer>에 넣어둔다.

 

 2) 인덱스 대로 줄 서있는 사람을 나타내는 int 배열을 생성한다.

 

 3) 왼쪽에 자기보다 키 큰 사람의 수를 입력받아온다.

 

 4) 그 수를 LinkedList의 index로 생각하여 LinkedList.remove(index)를 진행한다.

   ** remove()의 결과 값이 곧 실제 줄 선 순서가 된다.

   ** 한 순서에 여러 명이 동시에 줄서있을 경우는 없기 때문에 한 명이 그 순서에 줄서면 LinkedList에서 제거해야 한다.

 

 5)  4)의 결과 값을 2)에서 만든 배열의 인덱스로 사용하고, 해당 인덱스에 그 사람의 키를 넣는다.

    ** 사람의 키는 순서대로 1부터 N이라고 문제 조건에 명시되어 있다.

 

 6) int 배열 결과 출력하면 끝!!!

 

 

소스 코드

---

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

// 한 줄로 서기 문제
// 그리디 알고리즘 -> 순열 구하기와 비슷?!
public class p1138 {
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.valueOf(st.nextToken());
		
		LinkedList<Integer> indexs = new LinkedList<Integer>();
		int[] line = new int[n];
		
		// LinkedList 초기 값 설정
		for(int i = 0; i < n; i++) {
			indexs.add(i);
		}
		
		st = new StringTokenizer(br.readLine());
		for(int i = 1; i <= n; i++) {
			int people = Integer.valueOf(st.nextToken());
			int index = indexs.remove(people);
			line[index] = i;	// 해당하는 키 i를 가진 사람은 index 번째 줄에 서있다.
		}
		for(int ele : line) {
			System.out.print(ele + " ");
		}
	}
}