๋ฌธ์
์ํ์ด๋ ์นด๋ ๊ธฐ์ ์ ์ฐ์ตํ๊ณ ์๋ค. ์ํ์ด์ ์์ ๋ค๋ฆฐ ์นด๋๋ฅผ ํ๋์ฉ ๋ด๋ ค๋์ ๋ฐ๋ฅ์ ์์ผ๋ ค๊ณ ํ๋ค. ์ํ์ด๊ฐ ์ธ ์ ์๋ ๊ธฐ์ ์ ๋ค์ 3๊ฐ์ง๋ค.
- ์ ์ผ ์์ ์นด๋ 1์ฅ์ ๋ฐ๋ฅ์ ๋ด๋ ค๋๋๋ค.
- ์์์ ๋ ๋ฒ์งธ ์นด๋๋ฅผ ๋ฐ๋ฅ์ ๋ด๋ ค๋๋๋ค. ์นด๋๊ฐ 2์ฅ ์ด์์ผ ๋๋ง ์ธ ์ ์๋ค.
- ์ ์ผ ๋ฐ์ ์๋ ์นด๋๋ฅผ ๋ฐ๋ฅ์ ๋ด๋ ค๋๋๋ค. ์นด๋๊ฐ 2์ฅ ์ด์์ผ ๋๋ง ์ธ ์ ์๋ค.
์ํ์ด๋ ์ฒ์์ ์นด๋ N์ฅ์ ๋ค๊ณ ์๋ค. ์นด๋์๋ 1๋ถํฐ N๊น์ง์ ์ ์๊ฐ ์ค๋ณต๋์ง ์๊ฒ ์ ํ ์๋ค. ๊ธฐ์ ์ N๋ฒ ์ฌ์ฉํ์ฌ ์นด๋๋ฅผ ๋ค ๋ด๋ ค๋์์ ๋, ๋์ฌ ์๋ ์นด๋๋ค์ ํ์ธํ๋๋ ์์์๋ถํฐ ์์๋๋ก 1, 2, โฆ, N์ด ์ ํ ์์๋ค!
๋๋ ์ํ์ด๋ ์ฒ์์ ์นด๋๊ฐ ์ด๋ป๊ฒ ๋ฐฐ์น๋์ด ์์๋์ง ๊ถ๊ธํด์ก๋ค. ์ฒ์ ์นด๋์ ์ํ๋ฅผ ์ถ๋ ฅํ์ฌ๋ผ.
์ ๋ ฅ
์ฒซ ๋ฒ์งธ ์ค์๋ N (1 โค N โค 106)์ด ์ฃผ์ด์ง๋ค.
๋ ๋ฒ์งธ ์ค์๋ ๊ธธ์ด๊ฐ N์ธ ์์ด A๊ฐ ์ฃผ์ด์ง๋ค. Ai๊ฐ x์ด๋ฉด, i๋ฒ์งธ๋ก ์นด๋๋ฅผ ๋ด๋ ค๋์ ๋ x๋ฒ ๊ธฐ์ ์ ์ผ๋ค๋ ๋ป์ด๋ค. Ai๋ 1, 2, 3 ์ค ํ๋์ด๋ฉฐ, An์ ํญ์ 1์ด๋ค.
์ถ๋ ฅ
์ด๊ธฐ ์นด๋์ ์ํ๋ฅผ ์์์๋ถํฐ ์์๋๋ก ์ถ๋ ฅํ์ฌ๋ผ.
ํ์ด
i๋ฒ์งธ๋ก ์นด๋๋ฅผ ๋ด๋ ค๋์์ ๋ <- ์ด ํํธ์์ i๊ฐ ์ฌ์ฉ๋๊ธฐ ๋๋ฌธ์ 0 ๋์ 1๋ถํฐ ์์ํ๋ ๊ฒ์ด ์ข๋ค
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;
/*
* 1) 1๋ฒ ๊ธฐ์ -> ์ ์ผ ์์ ์นด๋ ๋ฐ๋ฅ์ ๋ด๋ ค๋๊ธฐ -> ์ ์ผ ์์ ๋ผ์๋ฃ๊ธฐ
* 2) 2๋ฒ ๊ธฐ์ -> ์์์ ๋ ๋ฒ์งธ ์นด๋ ๋ฐ๋ฅ์ ๋ด๋ ค๋๊ธฐ -> ์์์ ๋ ๋ฒ์งธ์ ๋ผ์๋ฃ๊ธฐ
* 3) 3๋ฒ ๊ธฐ์ -> ์ ์ผ ๋ฐ์ ์๋ ์นด๋ ๋ด๋ ค๋๊ธฐ -> ์ ์ผ ๋ค์ ๋ผ์๋ฃ๊ธฐ
* => ์/๋ค ๋ผ์๋ฃ๊ธฐ๊ฐ ์์ผ๋ฏ๋ก deque๋ฅผ ์ด๋ค
*/
deque<int> cardGame(int n, vector<int> &card){
deque<int> dq;
for(int i=1; i<=n; i++){ //
switch (card[i]) {
case 1:
dq.push_front(i);
break;
case 2:
{
int x = dq.front();
dq.pop_front();
dq.push_front(i);
dq.push_front(x);
break;
}
case 3:
dq.push_back(i);
break;
}
}
return dq;
}
int main() {
int n;
cin >> n;
// ์
๋ ฅ
vector<int> card(n+1, 0);
for (int i=1; i<=n; i++) // i๋ฒ์งธ๋ก ์นด๋๋ฅผ ๋ด๋ ค๋์์ ๋ card[i]๋ฒ ๊ธฐ์ ์ ์ด๋ค -> 1๋ฒ์งธ๋ถํฐ ์์ํ๋ฏ๋ก i=1
cin >> card[i];
// ์ฐ์ฐ
reverse(card.begin()+1, card.end()); // ๊ฑฐ๊พธ๋ก ์๊ฐํ๊ธฐ ๋๋ฌธ์ reverse ์ฌ์ฉ
deque<int> dq = cardGame(n, card);
// ์ถ๋ ฅ
while(!dq.empty()){
cout << dq.front() << " ";
dq.pop_front();
}
}
'โจ Algorithm' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค/C++] 2504๋ฒ: ๊ดํธ์ ๊ฐ (0) | 2022.07.31 |
---|---|
[๋ฐฑ์ค/C++] 11866๋ฒ: ์์ธํธ์ค ๋ฌธ์ 0 (0) | 2022.07.31 |
[๋ฐฑ์ค/C++] 2108๋ฒ: ํต๊ณํ (0) | 2022.07.24 |
[๋ฐฑ์ค/C++] 1213๋ฒ: ํฐ๋ฆฐ๋๋กฌ ๋ง๋ค๊ธฐ (0) | 2022.07.24 |
[๋ฐฑ์ค/C++] 20920๋ฒ: ์๋จ์ด ์๊ธฐ๋ ๊ดด๋ก์ (0) | 2022.07.17 |
๋๊ธ