[algorithm] 백준 18258번 큐 2

 

백준 15845번 문제와 내용은 같지만

차이는 입력 값의 크기와 시간 제한 차이이다

 

간단하게 풀 수 있는 방법은

15845번 해답에

ios::sync_with_stdio(false);
cin.tie(NULL);

 

이 두 줄을 main함수 맨 위에 추가하는 것이다

 

ios::sync_with_stdio(false)의 의미는

c의 printf/scanf와 c++의 cin/cout의 동기화를 해제하는 명령으로

사용 시 printf/scanf를 사용하면 안된다

 

cin.tie(NULL)은 간단히 말해서

입력 명령 전에 출력 버퍼를 비우지 않도록 하는 명령이다

온라인 저지 사이트같은 곳에서는 입력과 출력이

콘솔 상에 보이는 순서가 중요하지 않기에

굳이 입력 전 출력 버퍼를 비우지 않아도 된다는 의미다.

 

#include <iostream>
#include <queue>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    int x;
    cin >> n;
    string s;

    queue<int> q;
    for(int tmp=0; tmp<n; tmp++)
        {
            cin >> s;
            if(s == "push")
            {
                cin >> x;
                q.push(x);
            }

            if(s == "pop")
            {
                if(q.size() == 0) cout << -1 << "\n";
                else
                {
                    cout << q.front() << "\n";
                    q.pop();
                }
            }

            if(s == "size")
            {
                cout << q.size() << "\n";
            }

            if(s == "empty")
            {
                if(q.empty()) cout << 1 << "\n";
                else cout << 0 << "\n";
            }

            if(s == "front")
            {
                if(q.size() == 0) cout << -1 << "\n";
                else cout << q.front() << "\n";
            }

            if(s == "back")
            {
                if(q.size() == 0) cout << -1 << "\n";
                else cout << q.back() << "\n";
            }

            
        }
    return 0;
}

 

이 방법 외에 큐를 직접 구현하는 방법도 있다

구현 난이도는 조금 있지만

한 번 구현해봐야 늘 것 같아서

구현해보았다

 

#include <iostream>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    string str;
    int q[2000000] = {};
    int n;
    int s = 0;
    int e = 0;
    int i;
    cin >> n;
    
    for(int tmp=0; tmp<n; tmp++)
        {
            cin >> str;
            if(str == "push")
            {
                cin >> i;
                q[e] = i;
                e++;
            }
            else if(str == "pop")
            {
                cout << (s == e ? -1 : q[s++]) << "\n";
            }
            else if(str == "size")
            {
                cout << e-s << "\n";
            }
            else if(str == "empty")
            {
                cout << (s == e) << "\n"; // 1 or 0 출력
            }
            else if(str == "front")
            {
                cout << (s == e ? -1 : q[s]) << "\n";
            }
            else if(str == "back")
            {
                cout << (s == e ? -1 : q[e-1]) << "\n";
            }
        }
    return 0;
}

 

직접구현할 때에도 마찬가지로

ios::sync_with_stdio(false);
cin.tie(NULL);
해주어야한다

 

변수 s,e는 start,end를 의미한다고 보면된다

변수 i는 굳이 선언할 필요없이

cin >> q[e++];

이런식으로 한 줄로 구현도 가능하다

 

여러 기능들을 삼항 연산자를 활용하여 구현해봤고

empty 부분도 다르게 구현해봤다

back 부분에서 e-1번째 원소를 출력하는 것에 주의해야한다.

 

처음에 큐 배열의 크기를 2천만개로 지정했어서

계속 오류가 나다가 뒤늦게 알아차렸다