본문 바로가기
<알고리즘 문제풀이&연습>/[C,C++] Hackerrank

[C 자료구조] Stack - Simple Text Editor

by 사용자 BlockDMask 2017. 7. 14.
반응형

0) 제목

  • Hackerrank 의 Stacks 부분의 Simple Test Editor 문제입니다.
    (simple하지 않았습니다. 생각을 많이했어야 하는 문제였습니다 저한테는..)

  • C언어를 이용하여 풀었습니다.

1) 문제설명

  • Quary의 갯수 q를 받고, q만큼의 쿼리(line)을 받습니다.

  • 1입력시 append.

  • 2입력시 delete.

  • 3입력시 print

  • 4입력시 undo

  • 입니다.

  • append는 문자열 str 을 받고, 기존에 문자열에 새 문자열을 붙입니다.

  • delete는 int 타입의 변수 k를 받는데, 문자열의 맨 끝에서부터 k 만큼 문자를 삭제합니다.

  • print는 int 타입의 변수 k를 받는데, 현재 문자열에서 k번째 인자를 출력합니다.

  • undo는 인자로 받는것은 없고, 바로 전에 했던 append나 delete를 실행취소합니다.


2) 풀이과정


처음에는 char타입을 일일히 하나씩 대입하는 방법을 생각했었습니다.....

그러다가... 고민하고 틀리고 하기를 여러번....

스택을 두개 구현해서 

append할때 push, delete할때 pop을 기존 스택에 넣고 

그런 기록을 undo전용 스택에 넣는 방식도 생각해봤습니다.


다른 방법으로 접근을 해보았습니다. 

포인터 배열을 이용할 생각을 했습니다.

 char * 타입(Data)의 포인터 배열을 선언 그 포인터 배열의 갯수를 n을 받아서 동적할당했습니다.

또한, 문자열을 받을때마다 포인터 배열을 가지고 있는 Stack에 push합니다.


  • append - Stack의 Top 문자열을 뽑아서(peek) 새로운 문자열과 합친 다음 다시 Stack에 push 합니다.

  • delete - Stack의 Top 문자열을 뽑아서(peek) 맨뒤에서 k갯수 만큼 지우고 

  • 문자열 끝을 가리키는 널문자('\0')를 넣고 다시 Stack에 push합니다.

  • print - Stack의 Top 문자열을 뽑아서 k번째 인자를 출력합니다

  • undo - Stack를 pop하고 할당한 메모리를 해제 합니다.

  • 제가 생각한 구조를 그림으로 표현해보았습니다.


append를 할때마다 새로 동적할당을 하여서 기존의 문자열과 새 문자열을 합하여 stack에 push함을 볼 수 있습니다. -1,2

delete를 하면 기존의 문자열에서 k만큼의 갯수를 뒤에서부터 삭제하고 다시 stack에 push함을 볼 수 있습니다. -3

print를 하면 k번째 인자(1부터 시작)를 출력함을 볼 수 있습니다. -4

undo를 하면 stack에서 pop을 함을 볼 수 있습니다. -5.


3) 함수설명

  • 타입 " Data "는 " char * " 을 typedef 한 것입니다.

  • StackInit - 스택의 포인터 배열 크기를 동적할당하고, top을 -1로 만듭니다.

  • isEmpty - 스택이 비었는지 확인하는 함수입니다.

  • push - 스택에 Data 타입(char *)의 변수를 동적할당하여서 해당 길이만큼의 문자열을 삽입하고, top의 갯수를 하나 올립니다.

  • pop - 스택의 top의 Data 타입의 변수를 반환하고, top의 갯수를 하나 줄입니다.


4) 코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
 
#define TRUE 1
#define FALSE 0
enum {APPEND=1, DELETE, PRINT, UNDO };
//////////////////////////////////////////stack.////////////////////////////////////////////////
typedef char * Data;
typedef struct _stack{
    Data *arr;
    int top;
} Stack;
 
int isEmpty(Stack *sp){
    if(sp->top ==-1return TRUE;
    return FALSE;
}
 
void push(Stack * sp, Data data){
    int len = strlen(data) + 1;
    sp->arr[++(sp->top)] = (Data)malloc(sizeof(char* len);
    strcpy(sp->arr[sp->top], data);
}
 
void StackInit(Stack * sp,int n){
    sp->arr = (Data *)malloc(sizeof(Data) * n);
    sp->top = -1;
}
 
Data pop(Stack * sp){
    if(isEmpty(sp) == TRUE) return " ";
    return sp->arr[(sp->top)--];
}
 
Data peek(Stack *sp){
    if(isEmpty(sp) == TRUE) return " ";
    return sp->arr[sp->top];
}
 
////////////////////////////////////////////main////////////////////////////////////////////////
int main(void){
    int i, j;       //i, j 는 for문을 위한 변수 
    int n, q;     //n, q 는 n개의 갯수만큼 queary를 받기 위한 변수 
    int k;        //delete, print인 경우 몇개인지 세기 위한 변수 
    int len=0;  //str의 길이를 알기 위한 변수.
 
    char str[1000000];     //append 인 경우 문자열을 받기 위한 변수 
    char * tmp;     //현재 stack의 top 문자열에, 지금 받은 str을 append 하기 위한 변수.
 
    Stack stack//각각의 문자열를 저장하기 위한 stack 
        
    scanf("%d"&n);    
    StackInit(&stack, n);
 
    for(i=0; i<n; i++){
        scanf("%d"&q); 
        switch(q){
            case APPEND:
                scanf("%s", str);
//stack이 비었을때는 지금 받은 str을 바로 push합니다.                
                if(isEmpty(&stack)){
                    push(&stack, str);
                    len =0;
                    break;
                }
//peek한것의 길이와 str의 길이를 더한만큼 문자열을 동적할당 한 후에(tmp변수에), 문자열 두개를 붙입니다.
//그것을 push합니다.
                len = strlen(peek(&stack));
                len += strlen(str);
                tmp = (char *)malloc(sizeof(char* len + 1);
                strcpy(tmp,peek(&stack));
                strcat(tmp, str);
                push(&stack, tmp);
                free(tmp);                 
                break;
                
            case DELETE:
                scanf("%d"&k);
                strcpy(str,peek(&stack));
                len = strlen(str) - k;     //받은 문자열에서 k만큼 뻅니다.
                str[len] = '\0';            //문자열 끝 알려줍니다.
                push(&stack, str);
                break;
                
            case PRINT:
                scanf("%d"&k);
                tmp = peek(&stack);
                printf("%c\n",tmp[k-1]);
                break;
                
            case UNDO:
                pop(&stack);
                free(stack.arr[stack.top +1]); //pop했던 포인터배열인자(문자열) 하나를 메모리 해제 합니다.
                break;
        }
        
    }
//메모리 해제
    free(stack.arr);
    return 0;
}
 
cs


5) 인증

경로 : Dashboard>Data Structures>Stacks>Simple Text Editor

출처 : [HackerRank] https://www.hackerrank.com/challenges/simple-text-editor/

더 나은 코드로 보완 할 곳이 있으면 말씀해주세요.

부족한 코드 많은 지적 부탁드립니다.

반응형

댓글0