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

문제:

 

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

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

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

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

 

입력:

 

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

 

 

출력:

 

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

 

 

 

 

알고리즘 설계:

 

4

2 1 1 0 이 입력 됬을때

키가 작은사람부터 줄을 세우려고 하면 조금 복잡해 보여서

키가 큰 사람부터 줄을 세우기로 했다

{4}

{4 3}

{4 2 3}

{4 2 1 3}

 

여기서 중요한건 왼쪽에 있는 자기보다 키 큰 사람의 수+1=자기가 줄을 서게 될 위치 라는 규칙을 발견하는 것이다

키가 4인 사람 왼쪽엔 4보다 키큰사람이 없으므로  줄세울때 1번째에 세운다

그 다음에 키가 3인 사람은 줄세울때 2번째에 세운다

키가 2인 사람은 또 역시 2번쨰에 세운다(왼쪽에 있는 자기보다 키 큰 사람이 1명이니까) (그러면 자동으로 키가 3인 사람은 뒤로 밀린다)

키가 1인 사람은 3번째에 세운다 (왼쪽에 있는 자기보다 키 큰 사람이 2명이니까)  (그러면 또 키가 3인 사람은 뒤로 밀린다)

 

결과적으로 키가 4 2 1 3인 순서대로 줄서게 된다 

 

 

 

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner scan=new Scanner(System.in);
		int N=scan.nextInt(); // 사람수 입력
		int []tall=new int[N+1]; //키 1~N까지 사람의 왼쪽에 있는 자기보다 큰 사람수를 저장하는 배열 
		                         //tall[0]은 비워둔다 
		for(int i=1;i<N+1;i++) {
			tall[i]=scan.nextInt(); //tall[1]은 키가 1인 사람의 왼쪽에 있는 자기보다 큰 사람수 
		}
		
		List<Integer> line=new ArrayList<>(); // 줄을 세울 ArrayList line
		for(int i=N;i>=1;i--) {
			line.add(tall[i],i); //키가 i인 사람을 인덱스 tall[i]번째에 삽입한다 
		}
		
		for(Integer e: line)
			System.out.println(e);
	}
}

 

 

느낀점:

일단 딱봤을때 정답률도 높고 쉬워보여서 금방 풀줄 알았는데 머리가 생각보다 안돌아가서 자괴감에 빠진 문제였다

그리디 알고리즘 문제는 무작정 코딩을 하기전에  수학적 규칙을 찾는것이 가장 중요하다