[백준] 1138_한줄로서기 / 그리디알고리즘, 그리디란?

 

 

Sliver

 

 

문제

 

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

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

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

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

 

 

입력

 

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

 

 

출력

 

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

 

 

 

 

---

 

풀이

 

import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        int[] position = new int[N]; 

        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        for(int i=0; i<N; i++){
            int index = 0; // 자리 탐색을 위한 인덱스
            int count = arr[i]; // 자신보다 큰 사람의 수 
            
            while(true){
                // 자신보다 큰 사람이 충분힝 있고, 현재 자리가 비어져있을 경우
                if(count==0 && position[index]==0){
                    position[index] = i+1;  
                    break; // 자리를 찾았음으로 종료 
                }
                // 비어있는 자리를 찾아가며 자신보다 큰 사람의 수를 차감
                if(position[index]==0){ 
                    count -= 1; 
                }
                // 다음 자리 탐색
                index += 1;
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i=0; i<N; i++){
            sb.append(position[i] + " "); 
        }
        System.out.println(sb);
    }
}

 

 

해결방법

1. 자신보다 키가 큰 사람의 데이터를 받아 arr 배열에 저장한다. 
2. arr 배열을 탐색하면서 사람들을 배치할 자리를 추적한다. 배치할 자리는 position 배열에 저장한다. 
   • index변수를 사용하여 배치할 자리를 탐색한다. 
   • 현재 자리(index)가 비어있을 경우, 자신보다 큰 사람의 수(count)를 차감하고 다음 자리를 탐색한다.
   • 자신보다 큰 사람이 충분히 있고, 현재 자리가 비어있을 경우 사람을 배치하고 탐색을 종료한다. 

 

 

 

 

---

 

그리디 알고리즘

• 당장 최적인 선택이 앞으로도 최적일 것이라는 가정 하에, 각 단계에서 최적이라고 생각되는 선택을 하는 방식 

그리디를 사용한 이유 

• 각 사람의 조건에 맞는 자리를 배치하는 문제에서, 각각의 선택이 다른 선택에 영향을 주지 않고 독립적으로 이루어진다.
• 한 번 배치한 후에는 해당 값을 변경할 필요 없이 바로 최적의 결과를 얻을 수 있기 때문에, 그리디 방식으로 해결할 수 있다.

 

출처 : chatGPT 

---

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