백준 24511번 [queuestack](C++) -yes6686- 티스토리

백준 문제 풀이: 24511 [queuestack]

---

문제 링크: https://www.acmicpc.net/problem/24511

문제 설명:

입력된 데이터를 처리하기 위해 큐와 스택의 특징을 활용하는 문제입니다. 주어진 연산은 다음과 같습니다:

1. 입력 데이터 중, 특정 조건을 만족하는 요소만 deque에 추가합니다.
2. 이후, 새로운 데이터를 앞에서 삽입하고, 기존 데이터를 뒤에서 꺼내는 연산을 반복합니다.

---

문제 해결 코드

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

deque<int> d; // deque 자료구조를 활용

int arr[100001]; // 초기 상태 배열

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n; // 입력 개수
    cin >> n;

    // 초기 상태 배열 입력
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    // 값 입력 및 deque 초기화
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (arr[i] == 0) {
            d.push_back(x); // 조건에 맞는 값만 deque에 삽입
        }
    }

    int m; // 추가 연산 개수
    cin >> m;

    // m개의 추가 연산 처리
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        d.push_front(x); // 새로운 값을 deque 앞에 삽입
        cout << d.back() << ' '; // deque 뒤에서 값 출력
        d.pop_back(); // deque 뒤의 값 제거
    }

    return 0;
}

예제 입력:

4
0 1 0 1
1 2 3 4
3
5 6 7

예제 출력:

3 1 5

---

코드 설명

• 핵심 알고리즘: deque 자료구조를 활용하여 조건에 따라 데이터를 삽입하거나 삭제합니다.
• 구현 세부사항:
  • arr[i]가 0인 경우만 deque에 값을 추가합니다.
  • 새로운 데이터는 deque의 앞에 삽입하며, 기존 데이터는 뒤에서 꺼내 출력합니다.
• 시간 복잡도:
  • 입력 초기화: O(n)
  • 연산 처리: O(m)
  • 전체 시간 복잡도: O(n + m)

---

결과

조건에 따라 데이터를 삽입, 출력, 삭제하는 작업을 정확히 수행합니다. 문제는 deque 자료구조의 활용과 입력 처리 능력을 연습하기에 적합합니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 알려주세요!