[자료구조]-[리스트]-문제

1. 에디터 (백준 1406)

2. 조세퍼스 문제(백준 1158)

----------------

1. 에디터(백준 1406)

한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.

이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.

이 편집기가 지원하는 명령어는 다음과 같다.

L 커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)

D 커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)

B 커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨)

      삭제로 인해 커서는 한 칸 왼쪽으로 이동한 것처럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임

P $ $라는 문자를 커서 오른쪽에 추가함 커서는 $의 오른쪽에 위치함

초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 때, 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오. 단, 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 한다.

입력

첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수를 나타내는 정수 N(1≤N≤500,000)이 주어진다. 셋째 줄부터 N개의 줄에 걸쳐 입력할 명령어가 순서대로 주어진다. 명령어는 위의 네 가지 중 하나의 형태로만 주어진다.

출력

첫째 줄에 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 출력한다.

예제 입력  

abcd

3

P x

L

P y예제 출력  

abcdyx

풀이

- 전형적인 리스트 문제

- 직접 양방향 리스트를 만들고, left, right, insert, remove 함수를 만들어 풀 수도 있고,

- stl의 리스트를 사용해도 무방 (리스트 사용법에 대해 유의)

소스1-리스트 직접 제작

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

 

typedef struct _node{

    _node *prev;

    _node *next;

    char val;

} node;

 

node *head, *tail, *cur;

 

void init(){

    head = (node*)malloc(sizeof(node));

    tail = (node*)malloc(sizeof(node));

     

    head->prev = head;

    head->next = tail;

    head->val = 'H';

     

    tail->prev = head;

    tail->next = tail;

    tail->val = 'T';

     

    cur = tail;

}

 

void left(){

    if(cur->prev==head) return;

    cur = cur->prev;

}

 

void right(){

    if(cur==tail) return;

    cur = cur->next;

}

 

//cur 앞쪽에 삽입

void insert(char c){

    node *n = (node*)malloc(sizeof(node));

    n->prev=cur->prev;

    n->next=cur;

    n->val = c;

     

    cur->prev->next=n;

    cur->prev=n;

     

}

 

//cur 앞쪽에 있는 것 삭제

void remove(){

    if(cur->prev==head) return;

    node *n = cur->prev;

    n->prev->next=cur;

    cur->prev=n->prev;

    free(n);

}

 

void printList(){

    node *n = head;

    while(1){

        n = n->next;

        if(n==tail) break;

        printf("%c",n->val);

    }

    printf("\n");

}

 

char str[100001];

int N;

int main(){

    scanf("%s",str);

    init();

    int len = strlen(str);

    for(int i=0;i<len;++i)   insert(str[i]);

         

    scanf("%d\n",&N);

    char c;

    while(N--){

        scanf(" %c",&c);

        if(c=='L'){

            left();

        }else if(c=='D'){

            right();

        }else if(c=='B'){

            remove();

        }else if(c=='P'){

            scanf(" %c",&c);

            insert(c);

        }

    }

     

    printList();

    return 0;

}

소스2-stl::list 사용

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <list>

 

using namespace std;

 

int N;

list<char> li;

char str[100001];

int main(){

    scanf("%s",str);       

    for(int i=0;str[i];++i) li.push_back(str[i]);

     

    list<char>::iterator it = li.end();  

    scanf("%d\n",&N);

    char c;

    while(N--){

        scanf(" %c",&c);

        if(c=='L'){

            if(it!=li.begin())it--;

        }else if(c=='D'){

            if(it!=li.end())it++;

        }else if(c=='B'){

            if(it!=li.begin())  it=li.erase(--it);                                     

        }else if(c=='P'){

            scanf(" %c",&c);

            li.insert(it,c);

        }

    }

    for(it=li.begin();it!=li.end();it++) printf("%c",*it);

    return 0;

}

2. 조세퍼스 문제(백준 1158)

조세퍼스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 M(≤ N)이 주어진다. 이제 순서대로 M번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, M)-조세퍼스 순열이라고 한다. 예를 들어 (7, 3)-조세퍼스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 M이 주어지면 (N,M)-조세퍼스 순열을 구하는 프로그램을 작성하시오.

입력

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

출력

예제와 같이 조세퍼스 순열을 출력한다.

예제 입력  복사

7 3

예제 출력  복사

<3, 6, 2, 7, 5, 1, 4>

풀이

- 리스트로 푼다. (그냥 배열 혹은 원형 큐로도 가능하나, 그 경우 해당 수 하나를 삭제한 후, 그 후에 있는 값들을 한 칸 앞으로 당기는 오버헤드 발생함)

- 리스트에서 M만큼 이동 후, 그 위치값을 지우고, 다시 M만큼 이동

소스

#include <stdio.h>

#include <list>

#include <vector>

using namespace std;

int N,M;

list<int> li;

vector<int> v;

int main(){

int i,j;

scanf("%d %d",&N,&M);

for(i=0;i<N;++i) li.push_back(i+1);

j=-1;

for(i=0;i<N;++i){

j = (j+M) % li.size();

v.push_back(li[j]);

}

return 0;

}

#include <stdio.h>

#include <list>

#include <vector>

using namespace std;

int N,M;

list<int> li;

vector<int> v;

int main(){

int i,j,k;

scanf("%d %d",&N,&M);

for(i=0;i<N;++i) li.push_back(i+1);

list<int>::iterator it=li.begin();

for(i=0;i<N;++i){

for(j=0;j<(M-1);++j) it++;

printf("%d ",*it);

v.push_back(*it);

li.erase(it);

}

printf("<");

j = v.size();

for(i=0;i<j-1;++i) printf("%d, ",v[i]);

printf("%d>\n",v[j-1]);

return 0;

}

-끝-