관리 메뉴

막내의 막무가내 프로그래밍 & 일상

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

알고리즘/그리디

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

막무가내막내 2020. 11. 11. 23:59
728x90

www.acmicpc.net/problem/1138

 

1138번: 한 줄로 서기

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

www.acmicpc.net

 

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

키가 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번)

그리디 알고리즘을 사용하는 문제였다. 입력에서 키 정보와 자신보다 키가 큰 사람이 왼쪽에 몇 명이 있는지에 대한 정보가 주어진다. 그렇게 때문에 줄을 어떻게 서야 하는지에 대한 정보를 저

lipcoder.tistory.com

 

풀이는 다음과 같습니다.

[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] + " ");
        }
    }
}

 

 

 

 

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

728x90
Comments