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

지난번 포스팅에 이어서 ...

이번에는 STL container를 사용하여 문제를 해결해본다.

 

 

 

 

STL의 list 자료구조는 Sequence Container이다. 

Sequence Container란 내가 데이터를 넣는 순서대로  Access가 가능한 자료구조이다.

list 뿐만 아니라 array, vector, dequeue등은 sequence container이다.

 

List STL Library

#include <list>

 

List의 선언

std::list<int> list0 {1,2,3,4};

std::list는템플릿화 되어 있으므로, 저장하고싶은 원소의 타입을 지정할 수 있다.

 

List의 iterator

std::list<int>::iterator iter = list0.begin();

 

위처럼 list의 iterator를 선언하고 초기화 할 수 있다.

 

 

iterator의 advance 

std::advance 는 iterator를 특정 distance만큼 전진/후진시키는 함수이다.

#include<iterator>를 명시해주어야 한다.

사옹법 : std::advance(iterator, n);

 

 

 

List의 Sort

list container의 sort는 내장메서드를 사용한다.

std algorithm의 sort는 불가능하다... 

 

왜냐하면 std algorithm의 sort는 랜덤 액세스 이터레이터에만 사용 가능하다.

 

예를 들자면..

list iterator는 다음과 같은 표현이 불가능하다.

list0.begin() + 3; ===> 불가능

 

하지만 vector의 iterator는

v.begin()  + 3 과 같은 연산이 가능하다.

 

즉 vector의 iterator는 random access가 가능하다.

 

list의 iterator는 random access가 불가능하다.

왜냐하면 list (더블리 링크드 리스트)는 앞/뒤 노드와 연결만 구현되어 있을 뿐, 

 

전체 데이터에 대한 Access가 메모리 상에서 연속이지 않기 때문이다.

내 뒤 세 번째 노드에 대한 주소는 알 길이 없다.

다음노드의 다음 노드의 다음노드로 접근하는 방법 밖에는 없다.

 

이를 랜덤 액세스가 불가능하다고 하다. 

왜냐하면  원하는 곳에 액세스하기 위해서 순차적으로 전진/후진해야 하기 때문이다.

list0.begin() ++; 

list0.begin() --; 

같은 사용은 가능하다. 

 

결론적으로 std algorithm의 sort는 Random Access Iterator만 가능하기 때문에,

List의 Sort는 list 컨테이너의 메서드를 사용한다.

list0.sort();

 

 

 

List의 remove

list와 달리 vector는 컨테이너 중간 부분의 삽입/삭제가 느리다. 삭제 원소 뒤에 위치한 원소들을 모조리 땡겨와야하기 때문이다. 대신 push_back이나 pop 같은 연산은 빠르다.

대신 list는 중간 삽입/삭제가 빠르다. 비록 인덱싱은 못하지만. . . 

 

list0.remove(2); // 원소 2가 사라짐

// 혹은 remove_if()를 사용하면 조건에 맞는 원소들을 삭제할 수 있다.
// 조건은 함수 객체로 구현하여 넘긴다.

bool condition (const int& value){
	return value %2 == 0;
}

list0.remove_if(condition);

 

List의 merge

두 리스트를 merge 할 수 있다.

 

std::list<int> list0 = {1, 1, 3, 4};
std::list<int> list1 = {1, 2, 3, 5};

list0.merge(list1);

for (int num : list0)// 이런 access 방식을 range-based access라고 한다. 
	cout << num << endl;
    
    
list0.unique();

 

 

 

 

 

 

백준 1158 요세푸스 문제 풀이

위에서 공부한 stl list library를 사용하여 문제풀이를 해보자!

 

k개씩 전진하기 위해서는 iterator를 사용하였다.

그리고 cyclic list를 구현하기 위해 list0.end()에 도달하면 list0.begin() 이터레이터로 바꿔주었다.

 

 

한 번 터치한 노드를 지우기 위해서는 erase를 사용하였다.

remove는 해당 원소를 찾아서 지우는 작업을 하지만

erase는 iterator나 위치(주소)를 인자로 받아 데이터를 삭제한다. 

// ConsoleApplication1.cpp : 이 파일에는 'main' 함수가 포함됩니다. 거기서 프로그램 실행이 시작되고 종료됩니다.
//
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <list>


using namespace std;

int n, k;

// STL List로 다시 풀어보기... 

int main()
{

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

    // make linked list
    std::list<int> list0;
    for (int i = 1; i <= n; i++) {
        list0.push_back(i);
    }

    std::list<int>::iterator iter = list0.begin();

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k - 1; j++) {
            iter++; // 한 칸 전진
            if (iter == list0.end()) iter = list0.begin();
        }

        if (i == 0)printf("<");
        if (i != n - 1) printf("%0d, ", *iter);
        if (i == n - 1) printf("%0d>", *iter);
        iter = list0.erase(iter);
        if (iter == list0.end()) iter = list0.begin();
    }
    
    return 0;
}

 

 

 

 

STL을 사용하지 않은 풀이 바로가기!

 

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

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