[코드포스 Practice15] D. Queue

 

처음에 문제 이해 못하고 92 뒤에 31 있는거 아녀? 그런데 왜 답이 저렇지?? 생각했는데 

임의의 사람 앞에 있는게 92 뒤에 있는 게 31이었다. 

 

더 모르겠다.. 

이걸 풀 수 있다고?

 

아 약간 링크드리스트처럼 앞-뒤 비교하면서 연결하는게 생각나긴 하는데 배고파서 내일 해야겠다.

 

지금 생각나는건 일단 O(N2^2)번 돌고..

queue 배열을 n개 만듬

그 다음 N^2번 돌면서 queue의 front랑 back이랑 같은지 비교함.

같다면 연결하고 queue없앰

 

이런식으로 쭉 돌면 마지막에 queue가 2개이거나 1개 남을 것 같은데 

1개라면 그대로 출력

2개라면 징검다리로 두 개 있을테니 0으로 시작하는 걸 선두로 각각 하나씩 출력~

 

문제는 이럼 제곱만큼 돌고 n은 20만이라 터질 것 같다. 음... 

일단 이거라도 구현해보고 생각해보자. 물론 내일 쏘 헝그리

 

 

---

모르겠다..

#include <iostream>
#include <queue>
#include <algorithm>
#include <functional>

using namespace std;

void swap(int *a, int *b)
{
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

int main() {
    int n;
    scanf("%d", &n);
    queue<int> q[n];
    
    for (int i = 0; i < n; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        
        q[i].push(a);
        q[i].push(b);
    }
    
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (!q[i].empty())
            {
                if (q[i].front() == q[j].back() && q[i].front() != 0)
                {
                    while (!q[i].empty())
                    {
                        q[i].pop();
                        if (!q[i].empty())
                            q[j].push(q[i].front());
                    }
                }
                else if (q[i].back() == q[j].front() && q[j].front() != 0)
                {
                    while (!q[j].empty())
                    {
                        q[j].pop();
                        if (!q[j].empty())
                            q[i].push(q[j].front());
                    }
                }
            }
        }
    }
    
    int first = -1;
    int second = -1;
    for (int i = 0; i < n; i++)
    {
        if (!q[i].empty() && first == -1)
        {
            first = i;
        }
        else if (!q[i].empty())
        {
            second = i;
        }
    }
    
    if (first == second)
    {
        int i = first;
        while (!q[i].empty())
        {
            cout << q[i].front() << " ";
            q[i].pop();
        }
        return 0;
    }
    
    if (q[first].front() != 0)
    {
        swap(&first, &second);
    }
    
    q[first].pop();
    for (int i = 0; i < (n + 1) / 2; i++)
    {
        if (q[second].front() != 0 && !q[second].empty())
        {
            cout << q[second].front() << " ";
            q[second].pop();
        }
        if (q[first].front() != 0 && !q[first].empty())
        {
            cout << q[first].front() << " ";
            q[first].pop();
        }
    }
}

 

연결하는 부분 문제인 것 같은데 내일 생각해봐야겠다

 

 

 

---

결국 북님 코드 봤다. 

 

하지만 어렵다 컹..

내일 설명들어야겠다

 

 

 

---

 

다시 재도전

 

 

짝수 / 홀수 나눠서 따로 구현했다. 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
 
using namespace std;
using i64 = long long;
 
int main() {
    int n;
    scanf("%d", &n);
    
    vector<int> pre(1000005, -1);
    vector<int> nxt(1000005, -1);
    vector<int> count(1000005, 0);
    
    for (int i = 0; i < n; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        nxt[a] = b;
        pre[b] = a;
        count[a]++;
        count[b]++;
    }
    
    vector<int> pseq, nseq;
    
    int now = pre[0];
    while (now > 0)
    {
        pseq.push_back(now);
        now = pre[now];
    }

    int end = 0;
    if (n % 2 == 1)
    {
        for (int i = 0; i < count.size(); i++)
        {
            if(count[i] == 1 && nxt[i] != -1)
            {
                end = i;
            }
        }
    }
    now = nxt[end];
    if (n % 2 == 1)
        nseq.push_back(end);
    while (now > 0)
    {
        nseq.push_back(now);
        now = nxt[now];
    }
    
    vector<int> ans(n);
    if (n % 2 == 1)
    {
        for (int i = 0; i < nseq.size(); i++)
            ans[i*2] = nseq[i];
        for (int i = 0; i < pseq.size(); i++)
            ans[(pseq.size()-1-i)*2 + 1] = pseq[i];
    }
    else
    {
        for (int i = 0; i < nseq.size(); i++)
            ans[i*2 + 1] = nseq[i];
        for (int i = 0; i < pseq.size(); i++)
            ans[(pseq.size()-1-i)*2] = pseq[i];
    }
    
    
    
    
    for (int i = 0; i < ans.size(); i++)
        printf("%d ", ans[i]);
    
    return 0;
}

 

예아

짜고 나니깐 북님 코드가 뭘 했는지 알겠음