[백준 1138번] 한 줄로 서기 with Java

guswls·2024년 5월 4일

구현 그리디 백준

알고리즘

목록 보기

15/39

문제

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

코드

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

class Main {
	public static final int BLANK = -1;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());
		int[] line = new int[N];
		Arrays.fill(line, BLANK);

		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int tall = 0; tall < N; tall++) {
			int leftCount = Integer.parseInt(st.nextToken());

			//tall은 나중의 값이 현재 값보다 무조건 큼
			//현재 시점의 leftCount는 큰 수가 와야하는 공간의 개수를 의미
			//따라서 빈 위치일 때만 count를 증가시킨다.
			//만약 count가 leftCount와 같아진다면, 해당 자리가 tall을 삽입한다.
			int count = 0;
			for (int i = 0; i < N; i++) {
				if(line[i]==BLANK) {
					if (count == leftCount) {
						line[i] = tall + 1;
						break;
					}
					
					count++;
				}
			}
		}

		// 결과 출력
		for (int i = 0; i < N; i++) {
			System.out.print(line[i] + " ");
		}
	}
}

문제 이해

이번 문제는 문제 상황을 직접 그려보며 이해하는 것이 중요하다.
아래 그림을 살펴보자
입력으로 들어오는 값은 내 왼쪽에 존재하는 큰 수의 개수이다.
이때 넣는 순서가 곧 배열에 넣어야 할 값이 된다. (그림의 괄호 참고)
순차적으로 상황에 따라 수를 넣는 상황은 위 그림과 같다.
수의 왼쪽에 위치한 빈칸의 개수가 곧 왼쪽에 존재하는 자신보다 큰 수의 개수를 의미한다. 이것이 문제의 main idea이다.

풀이 방법

배열을 -1로 초기화한다. -1은 현재 인덱스의 배열이 비어있는 상태임을 의미하며, 명확성을 위해 BLANK라는 상수로 정의하였다.
두번째 라인의 입력 값들은 곧 현재 위치에서 왼쪽에 존재하는 배열의 빈칸의 개수를 의미한다.
따라서 입력을 받은 후에, line배열을 순회하며 만약 빈 값이면 count를 증가시킨다.
만약 증가된 count가 leftCount와 같아진다면, 그 위치가 값이 들어가야할 위치이다.

핵심 포인트

입력값이 빈칸의 개수라는 것이 직관적으로 이해가 매우 힘들다.
하지만 위와 같이 그림을 그려보면 바로 이해할 수 있다.
배열 내부에 들어가는 값은 입력으로 주어지는 것이 아닌 입력 순서로 주어진다.
따라서 나중에 입력받는 수가 현재보다 무조건 크며 이것으로 빈칸의 개수 == 자신보다 큰 수의 개수 가 성립하게 된다.
그렇기 때문에 이미 배열에 들어있는 값들이 현재 값보다 큰지 작은지 비교할 필요가 없다. 이전에 들어있는 값들은 현재 값보다 무조건 작기 때문이다.
이러한 특징으로 인해 이 문제는 그리디한 성질을 갖게 된다.

보완할 점 / 느낀 점

쉬운 문제인줄 접근했다가 크게 낭패를 본 문제이다.
처음에는 위의 개념을 잡지 않고 단순히 넣어야 될 위치에 값이 존재하면, 값이 존재하지 않는 위치까지 이동한 다음 그 위치에 삽입하는 방법으로 문제를 해결하려 하였다.
하지만 이러한 풀이의 경우는 빈칸의 개수를 고려하지 않았기 때문에 이 문제에 성립하지 않은 풀이이다.
문제를 완벽하게 이해한 후, 그리디하게 접근하는 것이 문제 풀이의 핵심이라고 생각한다.
생각할 거리가 많았고, 굉장히 좋은 문제라고 생각한다.