[Algorithm] 선형 자료구조 #230212

선형 자료구조

배열은 메모리의 연속된 위치에 각 원소들이 저장되어있고, 연결 리스트는 여기저기 흩어져있는 원소들의 특정 위치에서 삽입과 삭제를 상수 시간에 수행하기 위해 이전 원소에서 다음 원소를 가리키는 “포인터”로 구현한다.

struct ListNode {
    int element; 
    ListNode *prev, *next;
}

C++에서는 연결리스트를 list라는 STL을 사용해서 구현한다.

조세푸스 문제

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

void josephus(int n, int k) {
    list<int> survivors;
    for (int i = 1; i <= n; i++)
        survivors.push_back(i);

    list<int>::iterator kill = survivors.begin();
    while (n > 2) {
        kill = survivors.erase(kill);
        if (kill == survivors.end()) kill = survivors.begin();
        --n;

        for (int i = 0; i < k - 1; i++) {
            kill++;
            if (kill == survivors.end()) kill = survivors.begin();
        }
    }
    cout << survivors.front() << " " << survivors.back() << endl;
}

(1) 클린 코딩

• 나는 여기서 0부터 n -1까지 입력을 받아 처리하였는데 실제로 원하는 출력은 1부터 n까지의 범위이다. 처음부터 이 조건을 맞춰서 입력을 받으면 더 깔끔한 코드가 될 것.
• 그리고 출력 부분에서도 soldier는 항상 정렬되어있는 상태임에도 굳이 정렬해서 front와 pop_front를 번갈아가며 수행하였다. 이런 것도 깔끔한 출력문을 사용할 수 있기!

(2) 문제 해결 아이디어

• while문 안에서, 아래를 수행하는 구문이 soldier.back()이 erase에 포함이 되지 않아 버그를 생성하였음. (주석 참고)이를 if else문을 사용해서 해결할 수 있었지만, for문을 erase보다 “뒤에” 둠으로써 버그를 간단히 해결할 수 있었다.

if (*iter == soldier.back()) { // 마지막 원소인 경우 iter = soldier.begin(); }