💎 문제
N명의 사람들은 매일 아침 한 줄로 선다. 이 사람들은 자리를 마음대로 서지 못하고 오민식의 지시대로 선다.
어느 날 사람들은 오민식이 사람들이 줄 서는 위치를 기록해 놓는다는 것을 알았다. 그리고 아침에 자기가 기록해 놓은 것과 사람들이 줄을 선 위치가 맞는지 확인한다.
사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억한다. N명의 사람이 있고, 사람들의 키는 1부터 N까지 모두 다르다.
각 사람들이 기억하는 정보가 주어질 때, 줄을 어떻게 서야 하는지 출력하는 프로그램을 작성하시오.
💎 입력
첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 크거나 같고, N-i보다 작거나 같다. i는 0부터 시작한다.
ex)
4
2 1 1 0
💎 출력
첫째 줄에 줄을 선 순서대로 키를 출력한다.
ex)
4 2 1 3
💎 풀이 방법
앞선 게시글의 문제들과도 다른 유형의 문제로 직접 생각을 통해 구현해내는 문제였다. 조금 생각하기가 어려웠는데...일단 만약 0이 입력이 된다면 앞에 자신보다 키가 큰 사람이 없다는 뜻으로 순서대로 입력받은 사람에 따라 그 위치에 서있다는 것을 알 수 있었다! 쉽게 말해서 입력이 무엇이든 키 순서에 따라서 0이 된다는 것은 앞선 순서대로 입력받았기 때문에 서야될 순서에 다른 사람이 없고 더 이상 자신 보다 앞에 키 큰 사람이 있다는 것을 확인하지 않아도 될 때 그 자리가 자기가 서야하는 순서라는 것이다.
따라서, 1의 크기의 사람부터 차례대로 순서를 정해주면 되는 것인데, 만약 키가 제일 작은 사람의 입력 값이 2라면, 2명의 키 큰 사람이 자기보다 앞에 와야하므로 2칸을 지나친 다음에 자신의 자리에 서면 된다. 이는 입력받은 2를 하나씩 감소시켜서 0이 되었을 때 그 자리에 서면 되는 것으로 코드를 구현하였다!
for(int i = 1;i <= N;i++){
cin >> people;
for(int j = 0;j < N;j++){
if(people == 0 && result[j] == 0){
result[j] = i;
break;
}
else if(result[j] == 0) people--;
}
}위와 같이 코드를 작성하였다. 키가 1인 사람부터 검사를 시작해서 키 큰 몇 명이 자신보다 앞에 오는지 입력받고 자리를 찾아가면 된다. 현재 자리에 아무도 없다면! 그 위치에 자신보다 키가 큰 사람이 자리하게 될 것이므로 입력 받은 people을 감소시킨 후 다음 위치로 가서 확인을 한다. 결국 이제 입력받은 값이 0이 되고 그 자리에 여전히 아무도 서지 않았다면 그 위치에 줄을 서면 된다. 그 후 break를 통해 다음으로 키 큰 사람을 검사하면 된당!
💎 전체 코드
#include <iostream>
#include <vector>
using namespace std;
int main(int argc, const char * argv[]) {
int N, people;
cin >> N;
vector <int> result(N);
for(int i = 1;i <= N;i++){
cin >> people;
for(int j = 0;j < N;j++){
if(people == 0 && result[j] == 0){
result[j] = i;
break;
}
else if(result[j] == 0) people--;
}
}
for(int i = 0;i < N;i++)
cout << result[i] << " ";
cout << "\n";
return 0;
}
💎 고민
구현 문제를 오랜만에 풀어보았는데 문제 접근하는 시작이 항상 어려운 것 같다. 이번 문제는 간단하게 보였음에도 입력받은 키 큰 사람 수를 감소시켜주면서 자리를 확정짓는 아이디어가 나오기 까지 조금 걸렸다. 지인이 구현 문제가 주로 어렵게 많이 나온다고 하니깐 구현 문제를 많이 풀어볼수록 다른 알고리즘 문제 또한 접근하는 방법이 잘 나올 수 있을 것 같다
화팅!
