[1138번] 한 줄로 서기

문제 기출 : [https://www.acmicpc.net/problem/1138]

 

 

 

풀이 방법

[그리디알고리즘] 접근   키가 큰 사람 다음에 키가 작은사람이 있으면 하는 생각에 여러가지에 테스트 케이스를 생각해보다가 "정말 이게 가능한가?"라는  생각이 문득 들었다. 그 순간 어렵게 접근하지 않고 쉽게 접근해보았다. 모든 것을 다 내려 놓자.   키가 큰 순서대로 list에 저장하면 될 일이 아닌가?   즉 역순으로 탐색하면서 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지의 자리에 (인덱스+1)을 넣는다.   키가 4인 사람은 0명. list = [4]   키가 3인 사람은 1명. list = [4, 3]   키가 2인 사람은 1명. list = [4, 2, 3]   키가 1인 사람은 2명. list = [4, 2, 1, 3]

 

문제 풀이

public class Main	 {
	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String answer = "";

		try {
			int N = Integer.parseInt(br.readLine());
			StringTokenizer tokens = new StringTokenizer(br.readLine(), " ");
			int[] height = new int[N];
			
			int i = -1;
			
			while (tokens.hasMoreTokens()) {
				i++;
				height[i] = Integer.parseInt(tokens.nextToken());
			}
			
			ArrayList<Integer> list = new ArrayList<Integer>();
			for (int j = N; j >= 1; j--) {
				list.add(height[j-1], j);
			}
			
			for (int j = 0; j < list.size(); j++) {
				answer = answer.concat(list.get(j) + " ");
			}
			
			System.out.println(answer.trim());
			
		} catch (Exception e) {
			e.printStackTrace();
		} finally {
			try {
				br.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
	}
}