백준 - 5397 키로거 (C++, Cpp) 연결리스트 풀이

0. 주의사항

• 연결리스트를 연습하기 위해서 해당 문제를 연결리스트를 구현하여 풀었습니다.
• Cpp의 STL을 사용한 코드를 보기 위해서는 다른 블로그를 참조하시기 바랍니다.!

1. 문제소개

1-1.  요구사항

• 강산이가 입력한 길이 L 문자열(비밀번호)이 주어짐
• 입력 받은 비밀번호를 분석하여 정확한 비밀번호를 찾는 문제

1-2.  입력값과 출력값

//예제 입력
2
<<BP<A>>Cd-
ThIsIsS3Cr3t

//예제 출력
BAPC
ThIsIsS3Cr3t

• 첫째줄에 테스트 케이스의 개수가 주어짐
• 백스페이스를 누를 경우 "-"가 입력됨
• 방향키를 누를경우 "<"나 ">"가 입력됨

1-3.  문제조건

• "-"가 입력될 경우 커서 앞글자를 하나 지움, 만약 앞에 글자가 없다면 무시됨
• "<"나 ">"가 입력될 경우 커서를 왼쪽, 또는 오른쪽으로 1만큼 움직임 만약 커서가 줄의 마지막이라면 무시됨
• 나머지 글자는 정상정으로 입력됨, 단 백스페이스로 지워질 수 있음

2.문제풀이

2-1.  준비물

• 연결리스트로 문제를 풀 것이기 때문에 "글자"를 data로 하고 이전 노드와 다음 노드의 값이 있는 구조체 - (구조체명 : q)

typedef struct t_list
{
  char data;
  struct t_list *next;
  struct t_list *before;
} q;

• 해당 구조체를 연결리스트로 사용할 것이므로 "구조체 포인터" 변수가 필요함
• 1 - 노드의 시작을 알릴 시작노드 -> 변수명 : head
• 2 - 노드를 왔다갔다 하는 커서의 역할을 하는 노드 -> 변수명 : cursur
• 3 - 노드의 삭제나 삽입 이동을 위해 임시적으로 주소를 담아주는 도우미 노드 -> 변수명 : tmp

  q *head;
  q *tmp;
  q *cursur;
  /*
  something
  .
  .
  .
  */ 
 head = list_new(0); //head 노드의 data를 0으로 초기화하여 시작을 알린다.
 cursur = head; //커서의 시작은 head에서 시작한다.

• 4 - 테스트 케이스 갯수를 저장할 정수형 변수 N
• 5 - 테스트 케이스 문장을 입력받을 문자열 변수 line
• 6 - 노드의 data를 매개변수로 초기화하여 만들어주는 함수 -> 함수명 : list_new

q *list_new(char data)
{
  q *new_q;

  new_q = (q *)malloc(sizeof(q));
  new_q->data = data;
  new_q->next = NULL;
  new_q->before = NULL;
  return (new_q);
}

2-2.  풀이방법

• 1) 문자열을 입력받으면 헤드노드를 만들고 커서를 헤드노드에서 시작시킴
• 2) 문자열을 첫글자부터 순회하면서 switch case문을 활용하여 "<",">","-"와 그 외의 상황(글자)에 따른 코드를 작성
• 3) 커서의 위치는 해당 글자의 오른쪽에 위치한다고 가정

//3번 보충설명

ab|cde
커서가 위처럼 b와 c사이에 있다고 한다면 커서노드는 b노드와 같다.

|abcde
커서가 문자열의 가장 앞에 위치한다면 커서노드는 헤드노드와 같다.

abcde|
커서가 문자열의 가장 뒤에 위치한다면 커서노드는 e노드와 같다.

• 4) 글자가 들어올 경우 해당 글자를 data로 하는 노드를 만들고 기존에 있던 앞 뒤 글자노드와 연결
• 5) -가 들어올 경우 앞에 글자가 있을 경우 제거
• 6) <나 >가 들어올 경우 커서의 값을 이동한 노드의 주소로 할당
• 7) 문자열 순회가 끝나면 헤드노드의 next부터 끝까지 순회하며 노드의 data를 출력
• (head 노드의 값은 0이고 head의 next가 결과값의 시작이므로)

3.코드설명

3-1.  전체 구조

• 변수선언부, N번 반복, 문자열 순회, 결과값 출력으로 구성

#include <iostream>
#include <string>
#include <stdlib.h>
using namespace std;
//헤더파일들

typedef struct t_list
{
} q;

q *list_new(char data)
{
}

//구조체 선언과 구조체 생성 함수

int main()
{
  int N, i = 0;
  string line;
  cin >> N;
  
  q *head;
  q *tmp;
  q *cursur;
//변수 선언부

  while (i < N) //N번 반복
  {
    for (int j = 0; j < line.length(); j++)
    {
      switch (line[j])
      {
      case '<':
      case '>':
      case '-':
      default:
      }
    }
    i++;
    //문자열 순회, switch case문 사용
    
    while (head->next)
    {
      cout << head->next->data;
      head = head->next;
    }
    cout << '\n';
    //출력 부분. head의 next부터 끝까지 돌면서 data를 출력
  }
}

3-2.  변수선언부

typedef struct t_list {} q

• 1) struct q  구조

HEAD노드와 CURSOR노드 초기화

• 반복문 시작시 HEAD와 CURSOR

문자열 순회 때 A가 들어올 경우

• 연결리스트 연결 방식

3-3.  문자열순회

• 문자열 첫글자 부터 끝 글자까지 순회

for (int j = 0; j < line.length(); j++)
    {
      switch (line[j])
      {
      case '<':
        
      case '>':
        
      case '-':
       
      default:     
      }
    }

---

• case "<"

      case '<':
        if (cursur != head)
          cursur = cursur->before;
        break;

---

• case ">"

      case '>':
        if (cursur->next != NULL)
          cursur = cursur->next;
        break;

---

• case "-"

      case '-':
        if (cursur != head)
        {
          tmp = cursur;
          cursur = cursur->before;
          if (tmp->next != NULL)
          {
            cursur->next = tmp->next;
            tmp->next->before = cursur;
          }
          else
            cursur->next = NULL;
        }
        break;

이미 빈문자열이라 삭제할 문자가 없음

tmp노드 생성 후 커서 뒤로 한 칸 이동

• 기존의 tmp노드는 더 이상 연결리스트에 next와 before에 연결되어 있는 곳이 없어서 삭제됨

tmp가 마지막 노드였을 경우

• 기존 tmp노드가 원래 연결리스트의 마지막 노드였을 경우 Cursor의 next를 NULL로 변경하여 현재 Cursor를 마지막 노드로 변경

---

• default : 문자 입력

    default:
        tmp = list_new(line[j]);
        if (cursur->next != NULL)
        {
          tmp->next = cursur->next;
          cursur->next->before = tmp;
        }
        cursur->next = tmp;
        tmp->before = cursur;
        cursur = tmp;
        break;

3-4.  노드 출력

    while (head->next)
    {
      cout << head->next->data;
      head = head->next;
    }

4.전체 소스 코드

#include <iostream>
#include <string>
#include <stdlib.h>
using namespace std;

typedef struct t_list
{
  char data;
  struct t_list *next;
  struct t_list *before;
} q;

q *list_new(char data)
{
  q *new_q;

  new_q = (q *)malloc(sizeof(q));
  new_q->data = data;
  new_q->next = NULL;
  new_q->before = NULL;
  return (new_q);
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int N, i = 0;
  string line;
  cin >> N;

  q *head;
  q *tmp;
  q *cursur;

  while (i < N)
  {
    cin >> line;
    head = list_new(0);
    cursur = head;
    for (int j = 0; j < line.length(); j++)
    {
      switch (line[j])
      {
      case '<':
        if (cursur != head)
          cursur = cursur->before;
        break;
      case '>':
        if (cursur->next != NULL)
          cursur = cursur->next;
        break;
      case '-':
        if (cursur != head)
        {
          tmp = cursur;
          cursur = cursur->before;
          if (tmp->next != NULL)
          {
            cursur->next = tmp->next;
            tmp->next->before = cursur;
          }
          else
            cursur->next = NULL;
        }
        break;
      default:
        tmp = list_new(line[j]);
        if (cursur->next != NULL)
        {
          tmp->next = cursur->next;
          cursur->next->before = tmp;
        }
        cursur->next = tmp;
        tmp->before = cursur;
        cursur = tmp;
        break;
      }
    }
    i++;
    while (head->next)
    {
      cout << head->next->data;
      head = head->next;
    }
    cout << '\n';
  }
}