개요

백준1021번: 회전하는 큐

• 입력
  첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

• 출력
  첫째 줄에 문제의 정답을 출력한다.

접근방식

1. 앞과 뒤에서 접근해야하므로 덱(deque)를 사용했다.
2. 사실 vector 클래스 사용하면 만사 ok지만 덱을 이중연결리스트 형식으로
   간략하게 직접 구현해봤다.
3. 각각의 원소의 순서와 전체 덱 사이즈를 비교해서 덱의 앞쪽에 위치하는지 뒷쪽에 위치하는지 판별해서 2번연산을 수행할건지, 3번연산을 수행할건지 판단한다.
4. 중요한건 원소 방출시킬때 무조건!! 맨앞 원소만 방출 가능하다.
   맨뒤는 x

코드

#include<iostream>

using namespace std;

int N, M;
int inputArr[51];

//연결리스트에서 사용하는 노드
struct Node {
    int data;
    Node* prev;
    Node* next;
};

//이중 연결리스트
class doubledLinkedList {
private:
    int size;
    Node* head;
    Node* tail;

public:
    //생성자
    doubledLinkedList() {
        size = 0;
        Node* tmpHead = new Node;
        Node* tmpTail = new Node;
        tmpHead->data = -1;
        tmpTail->data = -1;
        tmpHead->prev = tmpHead;
        tmpHead->next = tmpTail;
        tmpTail->prev = tmpHead;
        tmpTail->next = tmpTail;
        head = tmpHead;
        tail = tmpTail;
    }
    //소멸자
    ~doubledLinkedList() {
        Node* node = new Node;
        Node* node1 = new Node;
        node = head;
        while (node != tail) {
            node1 = node;
            node = node->next;
            delete node1;
        }
        //반복문 빠져나올시 tail이므로
        delete node;
    }
    //맨 앞값 불러오기
    int front() {
        return head->next->data;
    }
    //맨 뒷값 불러오기
    int back() {
        return tail->prev->data;
    }
    //앞으로 집어넣기
    void push_front(int amount) {
        if (size == 0) {
            Node* tmp = new Node;
            tmp->data = amount;
            head->next = tmp;
            tmp->prev = head;
            tmp->next = tail;
            tail->prev = tmp;
            size++;
        }
        else {
            Node* tmp = new Node;
            tmp->data = amount;
            head->next->prev = tmp;
            tmp->next=head->next;
            tmp->prev = head;
            head->next = tmp;
            size++;
        }
    }
    //뒤로 집어넣기
    void push_back(int amount) {
        if (size == 0) {
            Node* tmp = new Node;
            tmp->data = amount;
            head->next = tmp;
            tmp->prev = head;
            tmp->next = tail;
            tail->prev = tmp;
            size++;
        }
        else {
            Node* tmp = new Node;
            tmp->data = amount;
            tail->prev->next = tmp;
            tmp->prev = tail->prev;
            tmp->next = tail;
            tail->prev = tmp;
            size++;
        }
    }
    //앞에거 빼기
    void pop_front() {
        if (size == 0)
            return;
        else {
            Node* tmp = head->next;
            head->next = tmp->next;
            tmp->next->prev = head;
            delete tmp;
            size--;
        }
    }
    //뒤에거 빼기
    void pop_back() {
        if (size == 0)
            return;
        else {
            Node* tmp = tail->prev;
            tmp->prev->next = tail;
            tail->prev = tmp->prev;
            delete tmp;
            size--;
        }

    }
    //크기 반환
    int Size() {
        return size;
    }
    
    /// <summary>
    /// target이 있는지 찾아내는 함수
    /// </summary>
    /// <param name="target"></param>
    /// <returns>몇번째 인덱스, 없다면 -1</returns>
    int Find(int target) {
        int cnt = 0;
        Node* tmp = head;
        while (tmp != tail) {
            tmp = tmp->next;
            cnt++;
            if (tmp->data == target) return cnt;
        }
        return -1;
    }
    //중간중간 원소들 확인용
    void Print() {
        Node* tmp = head;
        while (tmp != tail) {
            cout << tmp->data<<" ";
            tmp = tmp->next;
        }
        cout << endl;
    }

};

doubledLinkedList* dLL;

/// <summary>
/// target뺄때 2,3번 몇번 돌려야하는지 체크하는 함수
/// </summary>
/// <param name="target"></param>
/// <returns>사용한 2,3번 갯수</returns>
int check(int target) {
    int targetCnt, differ, tmp,retCnt=0;
    //타겟이 덱에 몇번째로 들어있는지 순서
    targetCnt = dLL->Find(target);
    if (targetCnt < 0) return -1;
    //덱 전체 사이즈 - 타겟의 순서
    differ = dLL->Size() - targetCnt;
    //전체 리스트에서 왼쪽에 있다면
    if (differ >= (dLL->Size() / 2)) {
        for (int i = 0; i < targetCnt-1; i++) {
            tmp = dLL->front();
            dLL->pop_front();
            dLL->push_back(tmp);
            retCnt++;
        }
        //target값은 방출
        dLL->pop_front();

        return retCnt;
    }

    //전체 리스트에서 오른쪾에 있다면
    else {
        for (int i = 0; i < differ+1; i++) {
            tmp = dLL->back();
            dLL->pop_back();
            dLL->push_front(tmp);
            retCnt++;

        }
        //target값은 방출
        dLL->pop_front();

        return retCnt;
    }
   
}

void input() {
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        cin >> inputArr[i];
    }
    for (int i = 1; i <= N; i++) {
        dLL->push_back(i);
    }
}
void solution() {
    int ans = 0;
    for (int i = 0; i < M; i++) {
        ans += check(inputArr[i]);
    }
    cout << ans;
}

int main() {
    dLL = new doubledLinkedList();
    input();
    solution();
    delete dLL;
}

문풀후생

문제를 첨에 제대로 안보고 무조건 맨앞의 원소를 방출해야하는데 뒤에것도 방출할수 있다고 풀었다가 예제가 안풀렸었다,,

꼼꼼해지자