Stack? LinkedList?
백준 1406번 에디터를 자바를 이용해 풀어보았다.
문제 링크 첨부한다.
https://www.acmicpc.net/problem/1406
LinkedList 의 삽입과 삭제는 O(1)?
자료구조를 얼마나 성의 없이 공부해왔는지 스스로 확인할 수 있는 지점이었다. 당연히 begin 과 end에서는 O(1) 이 맞다. 하지만 배열이 아니기에 타겟 인덱스를 알고 있다 하더라고 배열의 중간 지점이 타겟 인덱스라면 당연히 traverse 를 거쳐야 할테고 O(1)이 될 수 없다는 것을 알 수 있는데, 마치 내 지식인 것마냥 LinkedList의 삽입과 삭제는 O(1)이라는 굳은 믿음을 갖고 2년 전에 틀렸던 풀이를 고대로 3번이나 맞왜틀을 시전하며 혼자 샷건을 쳤다.
그러다가 화가 나서 통과되었던 2년 전 내 풀이를 살펴봤고 iterator를 사용한 것을 확인할 수 있었다. 왜 썼던 건지 iterator의 사용 이유조차 한 번에 파악을 하지 못해서 다른 사람의 풀이를 좀 살펴봤는데 나의 얄팍하고 구멍 잔뜩 뚫린 부끄러운 지식의 수준을 확인했다.
어떤 상황이든지 LinkedList의 삽입과 삭제가 항상 O(1)이 아님을..
제대로 모르는 iterator는 안 쓸래요
일단 iterator 에 대해서 당연히 공부를 하고 넘어가야 하겠지만, 당장 다시 풀어서 반드시 맞혀야겠다는 고집이 생겨서 다른 풀이를 생각해봤고 Stack으로 풀면 가능하겠다는 생각이 들었다.
Stack
스택을 두 개 놓고 이동이 필요한 원소들을 이동시키며, 삭제하며 삽입하면 주어진 연산들을 모두 O(1)로 수행 가능함을 확인했고 이를 코드로 옮겨보았다.
우선 기준이 되는 org 스택 하나를 선언하고, 보조 역할을 하는 tmp 스택을 선언했다.
org 스택의 peek 지점이 바로 현재 cursor의 위치인 것이고, 그 cursor 위치 뒤의 원소들을 tmp로 이동시켜두는 방식을 사용했다.
tmp로 이동시켜야 할 경우는 L 명령어를 만날 때다. 커서를 앞쪽으로 옮겨야 하기 때문에 커서 뒤에 존재하는 원소들을 tmp로 옮겨두는 것이다.
B 명령어를 만날 때는 org peek를 pop 해주면 되는 것이다.
D 를 만날 때는 커서를 뒤로 옮기는 것이니까 tmp에 원소가 있다면 pop 해주어 org로 넘겨주면 된다.
P는 현재 커서에 원소 하나를 추가하는 것이니까 org에 add 해주면 된다.
이를 코드로 옮기면 다음과 같다.
for(int i=0; i<M; i++){
String cmdStr = bfr.readLine().replace(" ", "");
char[] cmd = cmdStr.toCharArray();
switch(cmd[0]){
case 'P':
org.add(cmd[1]);
break;
case 'L':
if(!org.isEmpty()) tmp.add(org.pop());
break;
case 'D':
if(!tmp.isEmpty()) org.add(tmp.pop());
break;
case 'B':
if(!org.isEmpty()) org.pop();
break;
}
}출력
결국 다시 하나의 스택으로 모두 옮겨준 후에 출력해주면 된다. 어느 쪽의 스택으로 옮기든 상관 없는데 나는 org 쪽으로 옮겨준 후에 pop()을 하며 출력한 것이 아니라, enhanced for 문을 사용해서 가장 앞쪽에 있는 원소부터 출력했다. 반대로 옮긴 경우에는 위에부터 pop하며 출력하면 된다.
아래는 내가 제출한 코드다.
import java.io.*;
import java.util.*;
public class boj1406 {
public static void main(String[] args) throws IOException {
BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
String input = bfr.readLine();
int M = Integer.parseInt(bfr.readLine());
Stack<Character> org = new Stack<>();
Stack<Character> tmp = new Stack<>();
int len = input.length();
for (int i = 0; i < len; i++) org.add(input.charAt(i));
for(int i=0; i<M; i++){
String cmdStr = bfr.readLine().replace(" ", "");
char[] cmd = cmdStr.toCharArray();
switch(cmd[0]){
case 'P':
org.add(cmd[1]);
break;
case 'L':
if(!org.isEmpty()) tmp.add(org.pop());
break;
case 'D':
if(!tmp.isEmpty()) org.add(tmp.pop());
break;
case 'B':
if(!org.isEmpty()) org.pop();
break;
}
}
while(!tmp.isEmpty()) org.add(tmp.pop());
for(Character ch : org) bfw.write(ch);
bfw.close();
}
}마치며
너무나 기본적인 자료구조 지식조차 바닥을 기고 있는 상태를 발견하니 갑갑해진다. 그래도 미리 맞아서 다행이다. 알고리즘 공부를 무턱대고 카카오 기출만 풀어댈 게 아닌 것 같아서, 기초부터 다시 커버하려고 하는데 필요한 시점에 잘 시작한 것 같다...
