[백준 / BOJ] 5397 키로거 [이중 연결 리스트]

문제

출처 : www.acmicpc.net/problem/5397

5397번: 키로거

주어진 문자열에서 비밀번호를 찾아 출력하는 알고리즘이다.

'<' 를 입력받으면 커서를 한칸 왼쪽으로 움직인다.

'>' 를 입력받으면 커서를 한칸 오른쪽으로 움직인다.

'-' 를 입력받으면 커서뒤의 글자를 지운다.

예를들어,

A<B<C

를 입력받으면,

CBA

가 출력되어야한다.

 

풀이

배열은 문자를 중간에 삽입 삭제하기에 좋은 자료구조가 아니다.

(배열의 크기가 N일때, i번째위치에 원소를 하나 삽입하기위해선, 총 N-i개의 원소를 뒤로 미뤄야한다. 따라서 한번의 삽입으로 N-i번 움직여야함..)

문제를 풀려면 이중연결리스트를 사용해야한다.

 

구현할때 커서는 문자의 사이를 생각하며 구현했다. 

예를들어

 

A ~ B ~ C ~ D ~ E 처럼 표현되는 연결구조에 안보이지만, 커서는 있다.

              ↑

              커서    

위 커서의 위치를 기준으로 추가 삭제를 해준다.

 

구현

1. < 일때는 커서를 왼쪽으로 움직일수있는지 확인해준다. (구조체의 왼쪽이 NULL인지 봐줌)

2. 움직일수있다면, 커서를 왼쪽으로 움직여준다.

3. > 일때는 커서를 오른쪽으로 움직일수있는지 확인해준다. (구조체의 오른쪽이 NULL인지 봐줌)

4. 움직일수있다면 오른쪽으로 움직여준다.

5. - 를 입력받았을때는,

5-1. 커서의 왼쪽이 비어있는지 확인한다. (비어있으면 continue;)

5-2. 커서를 두번 왼쪽으로 움직였을때 비어있는지 확인한다.(비어있다면, 커서의 왼쪽에 해당하는 주소를 NULL로 바꿈)

5-2-1. 이때, 커서의 오른쪽이 비어있지 않다면, 커서의 오른쪽주소가 갖고있는 왼쪽 주소의 값을 NULL로 바꾼다. (코드를 보면 이해가 잘될것이다)

5-3. 커서를 두번 왼쪽으로 움직여도 비어있지 않다면, (커서를 왼쪽으로 두번 움직인 주소가 갖고있는 오른쪽 주솟값을 커서의 오른쪽주솟값과 연결)

5-3-1. 이때, 커서의 오른쪽이 비어있지 않다면, 커서의 오른쪽 주소가 갖고있는 왼쪽 주솟값을 커서를 왼쪽 왼쪽 움직인 주솟값으로 바꾼다.

6. 이외에 문자를 입력받으면, 새로운 구조체를 선언하여 문자를 저장해준다. 이후, 현재 커서의 왼쪽, 오른쪽에 해당하는 주솟값들과 새로운 구조체를 연결해준다. 그후 커서의 왼쪽주솟값을 새로운 구조체로 바꾼다.

 

위 과정을 반복한후, 만들어진 주솟값들을 순서대로 출력하면 답.

 

 

구조체 해체를 안해줬더니 메모리가 터질려한다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/5397%20%ED%82%A4%EB%A1%9C%EA%B1%B0/main.cpp

devxb/JJUNalgo