백준 1158 요세푸스 문제 시간초과 오답노트 (1)

백준 알고리즘 1158 요세푸스 문제 오답노트 

문제 : 시간초과

 

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

 

알고리즘 설계

요세푸스 문제는 N개 수열을 K 개씩 건너 뛰어가며 삭제하는 동작을 구현해야한다.

 

나는 이 문제를 보자마자 Linked List로 구현을 하고 싶어졌다.

 

왜냐하면 Linked List의 Head와 Tail을 연결하면 Cyclic한 자료구조를 구현 가능하고

 

또한 K번째 노드마다 삭제가 쉽고 빠르기 때문이다. (Linked List는 자료의 중간부분의 삭제나 삽입 효율이 좋다.)

 

 

그러나... 첫번째 Try 는 시간초과에 직면한다...

내가 시간초과에 직면했던 코드를 살펴보자...

나는 STL Container와 Iterator 사용법을 공부하기 전이라..

Linked List 자체를 쌩으로 구현했다.

 

 

 

코드 설명

사전준비 - library include, define, 변수 선언 등등

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <stdlib.h>

using namespace std;

int n, k;

링크드리스트를 쌩으로 구현할 생각이었어서 STL container 라이브러리를 인클루드하지 않았다.

 

Linked List의 구현

구현하고 보니 더블리 링크드 리스트가 아니라 싱글 링크드 리스트였다능.... 

공부를 똑바로 하기도 전에 문제부터 풀었더니; ㅎㅎ

그래도 문제 푸는데에는 지장 없다.

// Node
typedef struct _node {
    int data;
    struct _node* next; // Node Pointer
} Node;


// Linked List
typedef struct _List {
    Node* head;
    Node* tail;
    Node* curr;
    Node* before;
} List;


List myList;

void insert_node(int num) {
    Node* node;
    node = (Node*)malloc(sizeof(Node)); // Adress공간 할당.
    
    node->data = num;
    node->next = NULL;

    // Linked List가 비어 있으면?
    if (myList.head == NULL) {
        myList.head = node;
        myList.tail = node;
    }
    else {
        myList.tail->next = node;
        myList.tail = node;
    }

}

Node* remove_node(Node* prevnode) { // Doubly Linked List가 아니라 Single 을 구현했기 때문에 prev node를 인자로 준다. 
    Node* temp = prevnode->next;
    prevnode->next = temp->next;
    delete temp;
    return prevnode->next;
}

 

우선 node와 list 구조체를 정의해줬다.

그리고 insert node를 통해 list에 새로운 노드를 추가하며, 

새로 추가된 node는 list의 tail이 된다.

 

 

remove node는 삭제하고자 하는 노드의 이전 노드를 인자로 주어야 한다.

이는 singly linked list이기 때문이다.

singly linked list에서는 node를 삭제하게 되면 previous 노드를 가리키는 포인터가 없기 때문에... previous 노드를 잃어버리게 된다.  

따라서 previous node를 인자로 받아서 prev노드의 next를 prev->next->next로 바꿔치기 해준다.

 

즉 prev - curr - next 에서

 

curr와의 연결을 끊고

 

next와 직접 연결하는 것이다.

 

Main 함수의 구현

int main()
{

    scanf("%d", &n);
    scanf("%d", &k);

    // make linked list
    for (int i = 1; i <= n; i++) {
        insert_node(i);
    }

    myList.tail->next = myList.head; // Cyclic Linked List.

    // Delete every other K Node ...
    int cnt = 0; // K step
    int n_cnt = 0; // removed node count
    Node* iter;
    Node* prev;
    iter = myList.head;
    while (n_cnt < n) {
        prev = iter;
        iter = iter->next;
        cnt++;
        if (cnt == k - 1) {

            if (n_cnt == 0) printf("<");
            if (n_cnt != n - 1) printf("%0d, ", iter->data);
            if (n_cnt == n - 1) printf("%0d>", iter->data);
            cnt = 0;
            // Remove Node ...
            n_cnt++;
            iter = remove_node(prev);
            continue;
        }
    }

    //std::cout << "Hello World!\n";
    
    return 0;
}

시간 초과의 원인은 바로 while문에 있다.

N개 노드를 없애기 위해서 N 번의 for-loop만 돌리면 되는데, 

while문을 사용해 cnt를 매번 증가시켰고, 매 loop마다 n_cnt <n 인지 조건 검사를 했다.

K개를 세는 cnt도 마찬가지이다.

 

 

 

 

 

정답 코드 설명

위 main 코드를 아래처럼 수정하면 시간초과를 해결할 수 있다.

while문을 n번의 for-loop으로 대체하였다. 

int main()
{

    scanf("%d", &n);
    scanf("%d", &k);

    // make linked list
    for (int i = 1; i <= n; i++) {
        insert_node(i);
    }

    myList.tail->next = myList.head; // Cyclic Linked List.

    // Delete every other K Node ...

    Node* iter;
    Node* prev;
    iter = myList.head;
    prev = myList.tail;

    for (int i = 0; i < n; i++) { // N개를 없앨거야
        for (int j = 0; j < k - 1; j++) {
            prev = iter;
            iter = iter->next; // 한 칸 전진
        }
        if (i == 0) printf("<");
        if (i != n - 1) printf("%0d, ", iter->data);
        if (i == n - 1) printf("%0d>", iter->data);
        iter = remove_node(prev);

    }

    //std::cout << "Hello World!\n";
    
    return 0;
}

 

 

 

 

 

 

 

다음 게시글은 

list STL 라이브러리를 사용한 풀이이다.

STL container list 자료구조 :: 백준 알고리즘 1158 요세푸스 문제 오답노트 (2)

STL container list 자료구조 :: 백준 알고리즘 1158 요세푸스 문제 오답노트 (2)