์ฝ๋๋ก ๋ฐ๋ก ๊ฐ๊ธฐ
์ฝ๋ ๊ตฌํ๋ ฅ์ด ๋ถ์กฑํ๋ค. ๋ค์ ๊ธฐ์ด๋ถํฐ.
ํ์ด
์ค ์ธ์ฐ๊ธฐ ๋ฌธ์ ๋ก, ์ค๋ณต์๋ ์์ฐจ์ ์ธ ํค๋ฅผ ๊ฐ์ง ๊ฐ ์ฌ๋๋ค์ ์์ ์ ์ผ์ชฝ์ ์ ์ฌ๋ ์ค ์์ ๋ณด๋ค ํค๊ฐ ํฐ ์ฌ๋์ ๋ช
์๋ฅผ ์ ์ฅํฉ๋๋ค.
์์๋ก ๋์จ ์
๋ ฅ์
4
2 1 1 0
์ผ๋ก, 4๋ช
์ ์ฌ๋์ด ์๊ณ , ํค๊ฐ 1์ธ ์ฌ๋์ ์๊ธฐ๋ณด๋ค ํฐ ์ฌ๋ 2๋ช
์ด ์ผ์ชฝ์, 2์ธ ์ฌ๋์ 1๋ช
์ด ์ผ์ชฝ์, 3์ธ ์ฌ๋์ ์ผ์ชฝ์ 1๋ช
, 4์ธ ์ฌ๋์ ์ผ์ชฝ์ 0๋ช
์ด ์์์ ์๋ฏธํฉ๋๋ค.
์ผ์ชฝ์ n๋ช
์ด ์๋ค๋ ๊ฒ์ ์๋ฏธ๋ ๊ฒฐ๊ตญ โ์์ ๋ณด๋ค ํค๊ฐ ์์ ์ฌ๋์ ์ ์ธํ์ ๋ ์์ ์ ์ค์๊ธฐ ์์๊ฐ n๋ฒ์งธโ์์ ์๋ฏธํฉ๋๋ค.
์ด๋ฅผ ํ ๋๋ก ์ฝ๋๋ฅผ ์ธ์ ์ต๋๋ค. arr๋ฐฐ์ด์ ์ค ์ ์์๋ฅผ ์๋ฏธํ๋ฉฐ, ์ฒ์์๋ ์๋ฌด๋ ์ค์ ์์์ง ์๊ธฐ ๋๋ฌธ์ ๋ชจ๋ ๋
ธ๋์ -1์ ํ ๋นํด์ฃผ์์ต๋๋ค.
์ดํ ์ฌ๋์ ์๋ฅผ ๋ฐ๊ณ , ์ ๋งํผ for๋ฃจํ๋ฅผ ๋๋ฉฐ ์
๋ ฅ์ผ๋ก ์ฃผ์ด์ง โ์ผ์ชฝ์ ์ ์ฌ๋ ์โ๋ฅผ ๋ด๋ p(people) vector๋ฅผ ๋ง๋ค์ด์ฃผ์์ต๋๋ค.
์ดํ (0~N]๋งํผ ์ด์ค ํฌ๋ฌธ์ ๋๋ฉฐ, ์ค์์ ์์ ๋ณด๋ค ํฐ ์ฌ๋์ ์๊ฐ p[i]๊ฐ ๋ ๋๊น์ง ์ด๋(cnt++)ํฉ๋๋ค. p[i]๊ฐ ๋๋ฉด(cnt == left_p) arr[j]์ ํ ๋นํ์ฌ ์ค์ ์ธ์์ฃผ์์ต๋๋ค.
์
๋ ฅ๊ณผ ์ถ๋ ฅ์ ์ ์ธํ๊ณ ๋จ์ํ for๋ฌธ์ผ๋ก ์ถ์ ํ ์๊ฐ๋ณต์ก๋๋ O(N^2)์ด๋ ์ต์
์ ๊ฒฝ์ฐ(๋ ์์ ์ ์๋ฆฌ๋ฅผ ๊ฐ์ฅ ๋ง์ง๋ง์ ์ฐพ๋ ๊ฒฝ์ฐ, ์ฆ 4, 4 3 2 1 ๋ฑ ๋ด๋ฆผ์ฐจ์์ผ๋ก ๋ค์ด์ค๋ ๊ฒฝ์ฐ)์๋ ์์ฐจ์ ์ผ๋ก ์๋ฆฌ๋ฅผ ๋นจ๋ฆฌ ์ฐพ์ ๊ฒ์
๋๋ค. ๊ทธ๋ฌ๋ฏ๋ก ์๊ฐ๋ณต์ก๋๋ O(NlogN)์
๋๋ค.
์ฝ๋
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;
int arr[11];
int main()
{
for (int i = 0; i < 11; i++) arr[i] = -1;
int N = 0;
cin >> N;
vector<int> p;
for(int i=0;i<N;i++) {
int n;
cin >> n;
p.push_back(n);
}
for (int i = 0; i < N; i++) {
int left_p = p[i];
int cnt = 0;
for (int j = 0; j < N; j++)
if (arr[j] == -1) {
if (cnt == left_p) arr[j] = i + 1;
cnt++;
}
}
for (int i = 0; i < N; i++) cout << arr[i] << ' ';
return 0;
}