๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
โœจ Algorithm

[๋ฐฑ์ค€/C++] 18115๋ฒˆ: ์นด๋“œ ๋†“๊ธฐ

by nitronium102 2022. 7. 24.

๋ฌธ์ œ

์ˆ˜ํ˜„์ด๋Š” ์นด๋“œ ๊ธฐ์ˆ ์„ ์—ฐ์Šตํ•˜๊ณ  ์žˆ๋‹ค. ์ˆ˜ํ˜„์ด์˜ ์†์— ๋“ค๋ฆฐ ์นด๋“œ๋ฅผ ํ•˜๋‚˜์”ฉ ๋‚ด๋ ค๋†“์•„ ๋ฐ”๋‹ฅ์— ์Œ“์œผ๋ ค๊ณ  ํ•œ๋‹ค. ์ˆ˜ํ˜„์ด๊ฐ€ ์“ธ ์ˆ˜ ์žˆ๋Š” ๊ธฐ์ˆ ์€ ๋‹ค์Œ 3๊ฐ€์ง€๋‹ค.

  1. ์ œ์ผ ์œ„์˜ ์นด๋“œ 1์žฅ์„ ๋ฐ”๋‹ฅ์— ๋‚ด๋ ค๋†“๋Š”๋‹ค.
  2. ์œ„์—์„œ ๋‘ ๋ฒˆ์งธ ์นด๋“œ๋ฅผ ๋ฐ”๋‹ฅ์— ๋‚ด๋ ค๋†“๋Š”๋‹ค. ์นด๋“œ๊ฐ€ 2์žฅ ์ด์ƒ์ผ ๋•Œ๋งŒ ์“ธ ์ˆ˜ ์žˆ๋‹ค.
  3. ์ œ์ผ ๋ฐ‘์— ์žˆ๋Š” ์นด๋“œ๋ฅผ ๋ฐ”๋‹ฅ์— ๋‚ด๋ ค๋†“๋Š”๋‹ค. ์นด๋“œ๊ฐ€ 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();
    }

}

๋Œ“๊ธ€