[알고리즘] 백준 1138 한 줄로 서기 -그리디- 자바

www.acmicpc.net/problem/1138

1138번: 한 줄로 서기

 

백준 그리디 유형의 문제입니다.

키가 1인 사람부터 N인 사람까지 차례대로 입력을 받으며 해당 키 사람의 왼쪽에 입력 만큼의 키큰 사람이 왼쪽에 있어야합니다.

 

다음 블로그에서 설명을 잘해놓았습니다.

lipcoder.tistory.com/entry/%ED%95%9C-%EC%A4%84%EB%A1%9C-%EC%84%9C%EA%B8%B0-%EB%B0%B1%EC%A4%80-1138%EB%B2%88

한 줄로 서기 (백준 - 1138번)

 

풀이는 다음과 같습니다.

[Java]

import java.util.Scanner;

class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n+1];
        for (int i = 1; i <= n; i++) { //현재번호
            int left = sc.nextInt(); //나보다 키가 큰 사람이 left 명 있어야함
            for (int j = 1; j <= n; j++) {//배치할번호
                if (left == 0 && arr[j] == 0) { //나보다 왼쪽에 키큰사람이 있어야할 수 만큼 존재하고 아직 배치되지 않은 자리에 자리배치
                    arr[j] = i; // 자리배치
                    break;
                } else if (arr[j] == 0) { //0이면 일단 자신보다 큰 사람이 위치하게 자리비켜줌
                    left--;
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

 

 

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다.