[BOJ] 10845번 - 큐 (Swift, C++)

문제

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

• push X: 정수 X를 큐에 넣는 연산이다.
• pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 큐에 들어있는 정수의 개수를 출력한다.
• empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
• front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

<문제 링크>

10845번: 큐

---

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

---

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

---

문제 풀이

단순히 큐를 구현해보는 문제입니다. 큐는 FIFO 방식을 따르는 자료구조로 선착순 줄서기를를 생각하시면 됩니다!

(Queue의 개념이헷갈리신다면 제가 설명한 글 참고해주세요~)

 

Swift에서는 자료구조를 라이브러리로 지원해주지 않지만 C++에서는 지원을 해주기 때문에Swift와 C++, 두 개의 언어로 구현을 해보았습니다.

 

Queue 배열은 dequeue 과정에서 오버헤드가 발생하여 시간 복잡도가 O(n)이 될 수 있기 때문에

처음 인덱스를 변수로 저장하여 실제 데이터를 삭제하지 않고 해당 변수를 통해 처음 데이터를 관리하였습니다.

풀이 순서

1. Swift의 경우 Queue 배열과 처음 인덱스를 저장할 변수를 만들어주고, C++의 경우 라이브러리에서 지원해주는 Queue를 정의해줍니다.

2. 문제에서 요구하는 값을 조건에 맞게 콘솔에 출력해줍니다.

---

풀이 코드

< Swift>

// Swift
var queue = [Int]()
var firstIndex = 0  // 처음 데이터를 가리키는 인덱스
var size = 0  // 데이터 개수

let n = Int(readLine()!)!

for _ in 1...n {
    let cmd = readLine()!
    
    switch cmd {
    case "pop":
        if size != 0 {
            print(queue[firstIndex])
            firstIndex += 1
            size -= 1
        } else {
            print(-1)
        }
    case "size":
        print(size)
    case "empty":
        size == 0 ? print(1) : print(0)
    case "front":
        size == 0 ? print(-1) : print(queue[firstIndex])
    case "back":
        size == 0 ? print(-1) : print(queue.last!)  // 가장 마지막에 들어온 데이터
    default:
        let arr = cmd.split(separator: " ")
        let num = Int(String(arr.last!))!
        queue.append(num)
        size += 1
    }
}

---

< C++>

// C++
#include <bits/stdc++.h>
using namespace std;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    queue<int> Q;
    
    int n;
    cin >> n;
    
    while(n--){
        string str;
        cin >> str;
        
        if(str=="push"){
            int n;
            cin >> n;
            Q.push(n);
        }
        else if(str=="pop"){
            if(Q.empty()) cout << -1 << '\n';
            else{
                cout << Q.front() << '\n';
                Q.pop();
            }
        }
        else if(str=="size") cout << Q.size() << '\n';
        else if(str=="empty") cout << Q.empty() << '\n';  // true는 1, false는 0
        else if(str=="front"){
            if(Q.empty()) cout << -1 << '\n';
            else{
                cout << Q.front() << '\n';
            }
        }
        else{ // back
            if(Q.empty()) cout << -1 << '\n';
            else{
                cout << Q.back() << '\n';
            }
        }
        
    }
    
}

---

마무리

해당 문제에서는 굳이 오버헤드 문제를 처리해주지 않아도 문제는 풀리지만,
큐에서 가장 큰 문제 상황이라고 생각되는 오버헤드를 해결하기 위해 인덱스 변수를 활용하여 코드를 작성해보았습니다.