[백준] 1138 한 줄로 서기 - 구현(Implementation) + 그리디(Greedy, 탐욕법) + 아이디어 JAVA

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

1138번: 한 줄로 서기

코드설명

구현, 아이디어를 활용하는 문제입니다.

 

문제예시를 통해 푼 과정을 정리해보았습니다.

4
2 1 1 0

1. 각 번호의 사람마다 본인보다 키가 큰 사람이 왼쪽에 몇명이 있어야하는지가 입력됩니다.  

2. 자리 배열(arr[]) 을 선언하고, arr[] = 0 일경우 해당 자리는 아직 비어있다고 가정합니다.

3. 만약 0번쨰 사람이 자리를 돌경우를 생각해봅니다.

     3.1 [0번쨰] 사람의 경우 옆에 2명의 본인보다 큰 사람이 있어야합니다.

     3.2 arr[0] 을 확인합니다. 아직 0 이고, [0번째 사람]의 경우 옆에 2명의 본인보다 큰 사람이 있어야하므로 해당 자리에는 가지 못합니다. arr[1]을 확인하러 이동해야하고, 2명의 키 큰 사람에서 1개의 자리를 넘어갔으니 2명을 1명으로 변경시켜줍니다.

      3.3 arr[1]을 확인합니다. 아직 0 이고, [0번째 사람]의 경우 옆에 이제 1명의 본인보다 큰 사람이 있어야하므로 해당 자리에는 가지 못합니다. arr[2]를 확인하러 이동하고, 1명의 키 큰 사람에서 1개의 자리를 넘어갔으니 1명을 0 명으로 변경시켜줍니다.

      3.4 arr[2]를 확인합니다. 아직 0이고, [0번째 사람] 의 경우 0명의 본인보다 큰 사람이 있어야하므로 해당 자리에 착석시키면 마무리됩니다.

4. 3번과정을 계속해서 진행합니다. ( 3번과정에서 만약 arr[]이 0 이 아니라면, 해당 자리에는 못앉으므로 다음자리로 이동시킵니다.

      

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
	public static int N;
	public static int[] arr;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	
    	arr = new int[N];
    	
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) { //현재 번호 (0 번, 1번, .. N-1번)
    		int tallerThanMeLeft = Integer.parseInt(st.nextToken()); //각 번호의 카기 큰 사람이 왼쪽에 몇명있어야하는지
    		for(int j=0; j<N;j++) { //배치할 번호 (0번, 1번 ... N-1번)
    			if(tallerThanMeLeft == 0 && arr[j] == 0) { //나보다 키 큰 사람의 갯수가 왼쪽에 이미 존재하고, 아직 배치되지 않은 자리일경우 자리배치
    				arr[j] = i+1; //자리배치
    				break;
    			}else if(arr[j] == 0) { //0이면 아직 빈공간이고, tallerThanMeLeft가 아직 0이 아니라는 의미는 나보다 큰 사람을 세워둔다는 의미입니다.
    				tallerThanMeLeft-=1;
    			}
    		}
    	}
    	
    	for(int i=0;i<N;i++) {
    		System.out.print(arr[i]+" ");
    	}
    	
    }
    
}

 

정답코드2입니다. (로직은 첫번쨰 코드와 같습니다.)

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	private static int N, K, M;
    private static int answer = 0;
    private static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
     
        N = Integer.parseInt(st.nextToken());
        arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++) {
        	arr[i] = Integer.parseInt(st.nextToken());
        }
        int[] result = new int[N];
       
        for(int i=0; i<N; i++) {
        	for(int j=0; j<N; j++) {
        		if(result[i] == 0 && arr[j] == 0) {
        			result[i] = j + 1;
        			arr[j] -= 1;
        			break;
        		}
        		else if(result[i] == 0 && arr[j] > 0){
        			arr[j] -= 1;
        		}
        	}
        	
        }
        
        for(int i=0;i<N; i++) {
        	System.out.print(result[i]+" ");
        }
    }
    
}