한 줄로 서기

문제

백준 1138번 - 한 줄로 서기

언어

JavaScript

순서도

1 번 사람부터 N 번 사람까지 각 사람마다
왼쪽 키 큰 사람 수 만큼 오른쪽으로 이동하며 위치 구하기
이 때, 왼쪽 키 큰 사람 수가 0 인 경우와 1 이상인 경우를 나누기
1. 왼쪽 키 큰 사람 수가 0 인 경우, 이미 자리가 찬 위치 만큼 오른쪽으로 이동
2. 왼쪽 키 큰 사람 수가 1 이상인 경우, 이미 자리가 찬 위치 만큼 오른쪽으로 이동하고, 이에 더해서 왼쪽 키 큰 사람 수 만큼 오른쪽으로 이동
구한 위치에 사람 위치시키기

문제 풀이 step 1

N 명의 사람이 주어집니다.
각 사람은 자기 위치에서 자기보다 키가 큰 사람이 왼쪽에 몇 명 있는지 주어집니다. (단, 사람들의 키는 1 부터 N 까지 모두 다릅니다.)
이 때, 각 사람의 위치를 구하는 문제입니다.

문제 풀이 step 2

본 문제는 그리디 방식으로 풀 수 있습니다.
매 순서마다 현재 상황에서 가장 최선의 선택(가장 적합한 위치)만 하면 되기 때문입니다.
예를 들어, 1번 사람 왼쪽에 2명이 있고, 2번 사람 왼쪽에 3명이 있다고 가정하겠습니다.
- 1번 사람의 경우, 왼쪽에서 3번째 위치에 위치하게 됩니다. ([ ][ ][1][ ][ ])
- 2번 사람의 경우, 왼쪽에서 4번째 위치에 위치하게 됩니다. 단, 1번 사람의 위치를 고려해야 합니다.
  - 하지만 1번 사람의 위치를 고려하는 것은 어렵지 않습니다. 왜냐하면 1번 사람은 무조건 2번 사람보다 작기 때문입니다.
  - 즉, 1번 사람은 무조건 작기 때문에 [ ][ ][1][ ][ ] => [ ][ ][ ][ ] 과 같이 1번 사람을 제외시킬 수 있고, 현재 위치에서 2번 사람을 4번째 위치에 넣으면 되는 것입니다.
  - 즉, [ ][ ][ ][2] 처럼 넣게 될 것이고, 여기에 아까 1번 사람의 위치를 기억했다가 다시 넣으면 [ ][ ][1][ ][2] 과 같이 될 것입니다.
물론 위 방식은 쉽게 설명하고, 그리디 방식에 어울리게 설명을 하기 위해서 약간 번거로운 과정이 들어갔습니다.
실제로 구현할 때는 1번 사람의 위치를 기억했다가 다시 넣기보다는 1번 사람과 같이 이미 위치한 사람만큼 오른쪽으로 이동하면 될 것입니다.

후기

구현 방식의 알고리즘을 풀고 싶어서 문제를 찾았지만, 구현 보다는 그리디 성향이 더 강하기 때문에 그리디 알고리즘으로 분류하게 되었습니다.
처음에는 구현 방식의 완전 탐색으로 풀어볼까 했지만, 그리디 알고리즘이 더 적합하고 로직이 간단해지기 때문에 그리디 방식을 선택하게 되었습니다.
그리디 방식은 항상 느끼지만 문제 안에 숨어있는 명확한 조건 (ex. 이전 순서에서 진행한 로직은 다음 순서에서는 상관이 없다 : 1번 사람을 위치시키면 2번 사람에게는 아무 영향이 없다) 을 찾는게 중요한거 같습니다.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

const solution = (input) => {
	const n = Number(input[0]);
	const cntOfLeft = input[1].split(" ").map(Number);
	const answer = Array.from({length: n}, () => -1);

	for (let i = 1; i < n + 1; i++) {
		// 왼쪽 키 큰 사람 수
		let cnt = cntOfLeft[i - 1];

		// 각 사람의 위치 구하기
		let index = 0;

		// 왼쪽 키 큰 사람 수가 0 인 경우
		for (let j = 0; j < n + 1; j++) {
			if (answer[j] === -1) break;

			// 이미 위치한 사람 수 만큼 오른쪽으로 이동
			index += 1;
		}

		// 왼쪽 키 큰 사람 수가 1 이상인 경우
		while (cnt > 0) {
			// 왼쪽 키 큰 사람 수 만큼 오른쪽으로 이동
			index += 1;

			// 이동한 위치에 사람이 있다면 cnt 감소되지 않게 처리
			if (answer[index] !== -1) continue;

			// 오른쪽으로 이동한 만큼 cnt 감소
			cnt -= 1;
		}

		// 해당 위치에 사람 넣기
		answer[index] = i;
	}

	return answer.join(" ");
};

console.log(solution(input));