백준 1138 c++ "한 줄로 서기" -PlusUltraCode-

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

 

[필자 사고]

접근 방식을 몰라 못푼 문제다.

해설을 보니 코드 구현은 쉬었지만 생각하는 사고 과정이 다소 어려움이 있었다.

내가 이해한 바로 말하자면 주어진 입력값에서 resultArr에 해당 idx를 넣는다. 만약 어떠한 값이 있다면 다음으로 넘어간다. 이런식으로 반복하면 resultArr은 모든 값을 채워지고 그게 정답이다.

 

일단은 이 정도로 하고 넘어가기로 했다. 

 

다음은 코드해설이다.

[코드 해설]

Input() 함수

• 사용자로부터 정수 N을 입력받는다. 이 N은 전체 사람의 수를 의미한다.
• 그 다음 N개의 정수를 입력받아 arr 벡터에 저장한다.
  이 배열의 arr[i]는 i + 1번 사람 앞에 자신보다 키 큰 사람이 몇 명 있어야 하는지를 의미한다.
• 즉, 이 입력 배열은 줄의 조건 정보를 담고 있다.

---

Game_Start() 함수

1. resultArr 벡터를 크기 N만큼 0으로 초기화한다.
   이 벡터는 줄을 설 최종 결과를 저장할 공간으로, 각 인덱스는 줄의 위치를 의미하고 값은 사람 번호를 의미한다.
2. 사람 번호 i + 1을 앞에 키 큰 사람이 arr[i]명 있어야 한다는 조건에 따라 배치한다.
   구체적으로는 다음과 같은 방식으로 구현된다.
   • count = arr[i]로 설정하여 앞에 건너뛰어야 할 빈 칸(또는 이미 채워진 키 큰 사람 수)을 세는 기준으로 삼는다.
   • 줄의 앞에서부터 오른쪽으로 순회하면서, 아직 비어 있는 자리(resultArr[k] == 0)를 만났을 때만 count를 줄인다.
   • 만약 count == 0이 되었을 때 빈 자리를 발견하면, 그 자리에 사람 번호 i + 1을 배치한다.
   • 이렇게 하면 각 사람이 자신보다 키 큰 사람 수만큼 앞자리를 비운 상태에서 정확히 자리에 앉게 된다.
3. 모든 사람에 대해 위 과정을 반복하면 resultArr에는 최종 줄 선 결과가 저장된다.
4. 마지막으로 resultArr를 출력하여 줄을 선 순서를 보여준다.

---

main() 함수

• Input() 함수를 호출하여 입력을 받고,
• Game_Start() 함수를 호출하여 줄을 세우는 로직을 수행한다.

이 함수는 전체 프로그램의 흐름을 제어하며, 입력 → 처리 → 출력 과정을 담당한다.

[소스 코드]

#include <iostream>
#include <vector>

using namespace std;

int N;
vector<int> arr;
vector<int> resultArr;
void Input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		arr.push_back(num);
	}
}

void Game_Start() {
    resultArr.resize(N, 0);
    for (int i = 0; i < N; i++) {
		int count = arr[i];
		for (int k = 0; k < N; k++ ) {
			if (resultArr[k] == 0) {
				if (count == 0) {
					resultArr[k] = i + 1;
					break;
				}
				count--;
			}
			
		}
    }

    for (int i = 0; i < N; i++) {
        cout << resultArr[i] << " ";
    }
}


int main(void) {
	Input();
	Game_Start();
}