개요

백준 1158번: 요세푸스 문제

• 입력
  첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

• 출력
  예제와 같이 요세푸스 순열을 출력한다.

접근 방식

1. 원형 연결리스트를 사용하면 쉬울 거 같아서 간단하게 구현해서 사용했다.

2. 이중 연결리스트랑은 다르게 tail 노드를 설정안하고 head로도 충분할 것 같아서 head노드만 설정해놓고 구현하였다.

코드

#include<iostream>

using namespace std;

int N, K;

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

//원형 연결리스트
class circularLinkedList {
private:
    int size;
    Node* head;

public:
    //생성자
    circularLinkedList() {
        size = 0;
        Node* tmpHead = new Node;
        tmpHead->data = -1;
        tmpHead->prev = tmpHead;
        tmpHead->next = tmpHead;
        head = tmpHead;
    }
    //소멸자
    ~circularLinkedList() {
        Node* node = new Node;
        Node* node1 = new Node;
        node = head->next;
        while (node != head) {
            node1 = node;
            node = node->next;
            delete node1;
        }
        //반복문 빠져나올시 head이므로
        delete node;
    }
    //맨 앞값 불러오기
    int front() {
        if (size == 0) return-1;
        return head->next->data;
    }
    //맨 뒷값 불러오기
    int back() {
        if (size == 0) return -1;
        return head->prev->data;
    }
    //앞으로 집어넣기
    void push_front(int amount) {
        if (size == 0) {
            Node* tmp = new Node;
            tmp->data = amount;
            head->next = tmp;
            head->prev = tmp;
            tmp->prev = head;
            tmp->next = head;
            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->prev = tmp;
            tmp->prev = head;
            tmp->next = head;
            head->next = tmp;
            size++;
        }
        else {
            Node* tmp = new Node;
            tmp->data = amount;
            tmp->next = head;
            tmp->prev = head->prev;
            head->prev->next = tmp;
            head->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 = head->prev;
            tmp->prev->next = head;
            head->prev = tmp->prev;
            delete tmp;
            size--;
        }

    }
    //특정 노드 지우기
    void pop(Node* node) {
        if (size == 0) return;
        else {
            node->next->prev = node->prev;
            node->prev->next = node->next;
            delete node;
            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->next;
        while (tmp != head) {
            tmp = tmp->next;
            cnt++;
            if (tmp->data == target) return cnt;
        }
        return -1;
    }
    //중간중간 원소들 확인용
    void Print() {
        Node* tmp = head->next;
        while (tmp != head) {
            cout << tmp->data << " ";
            tmp = tmp->next;
        }
        cout << endl;
    }
    Node* Head() {
        return head;
    }

};
circularLinkedList* cLL;

void input() {
    cin >> N >> K;
    for (int i = 1; i <= N; i++) {
        cLL->push_back(i);
    }
}
void solution() {
    Node* node = new Node;
    Node* tmp = new Node;
    node = cLL->Head()->next;
    cout << "<";
    //size가 0이상일때 반복
    while (cLL->Size() != 0) {
        int tmpK = K;
        //K번째 순서 올때까지 node 이동
        while (tmpK != 1) {
            node = node->next;
            //움직였을 때 head값이 되면 한번 더가야됨. head지울순 없으니
            if (node == cLL->Head()) {
                node = node->next;
            }
            tmpK--;
        }
        //k번째 순서인 노드값 출력 후
        if (cLL->Size() != 1)
            cout << node->data << ", ";
        else
            cout << node->data << ">";
        //임시 노드에 노드 정보 담아놓고
        if (node->next != cLL->Head())
            tmp = node->next;
        else
            tmp = cLL->Head()->next;
        //해당 노드 지우기
        cLL->pop(node);
        //임시노드에 담겼던 값 넣어줌
        node = tmp;
    }

}

int main() {
    cLL = new circularLinkedList();
    input();
    solution();
    delete cLL;
}

문풀후생

이전 문제인 백준 1021(회전하는 큐)에서 이중연결리스트를 구현해봤더니
상대적으로 원형연결리스트 구현에 시간이 많이 안 걸렸다.