LinkedList 구현하기
프로그래머스 2021 카카오 인턴 Level 3 문제 표 편집을 Java를 이용하여 풀어보았다.
처음 풀었던 풀이는 정확성 테스트만 통과하고 효율성 테스트를 다 실패했다. 빅-O 가 얼마인지 계산해보고 싶은데 난 아직 이걸 어떻게 계산하는지 잘 모른다. 알고리즘을 무작정 풀어 제끼고 맞으면 좋고 아님 마는 식의 풀이가 아닌 숲을 보고 풀 줄 아는 안목을 기르고 싶은데 아직까지 좀 막연한 듯 싶다.
어쨌든 문제 링크 첨부한다.
https://programmers.co.kr/learn/courses/30/lessons/81303
LinkedList 직접 구현해서 사용하기
처음에는 LinkedList를 갖다 썼다. LinkedList<Integer> 로 선언해서 0부터 8까지 집어넣고 다른 변수들을 선언해서 이동 및 삭제와 복구를 진행했다. 그랬더니 상당히 변수가 많아지고 나도 내 코드에 말려버리는 일이 발생했다. 어찌저찌 그림으로 다 그려가며 정확성은 다 통과했지만 결국 효율성에서 다 막혔다.
다른 사람들의 풀이를 참고해서 LinkedList를 직접 구현하는 방식으로 풀면 된다는 것을 알게 됐다. 이전에 풀었던 호텔 방 배정 문제와 유사한 아이디어라고 느껴졌다.
호텔 방 배정 문제에서는 현재 방 -> 다음 빈 방 의 정보를 함께 저장해주었다.
이번 문제에서는 prev -> cur -> next 의 정보를 한 덩어리로 묶어 보는 관점으로 풀면 해결이 가능하다. 
위 그림만으로 무슨 말인지 알아먹기는 좀 어렵겠지만,,, 전체적인 구조만 한 번 살펴보기 바란다. 중요한 점은 가장 첫 번째 녀석의 prev는 -1, 가장 마지막 녀석의 next도 -1로 표시함으로써 구분해주는 것이 중요하다.
삭제 연산
위 그림에서 4를 삭제한다고 가정하자. 이 때 해줘야 할 작업은 다음과 같다.
1.
4의 앞에 있는3의 다음 녀석을5로 잡아주는 것
2.4의 뒤에 있는5의 이전 녀석을3으로 잡아주는 것
3. 만약 삭제 타겟의 앞이-1이면 1의 작업은 무시
4. 만약 삭제 타겟의 뒤가-1이면 2의 작업은 무시
5. 커서를 한 칸 내려주는데, 만약 막칸이면 위로 한 칸 올리기
이를 코드로 표현하면 다음과 같다.
stack.add(new int[]{prevPos[curPos], curPos, nextPos[curPos]});
if(prevPos[curPos]!=-1) nextPos[prevPos[curPos]] = nextPos[curPos]; // 1의 작업
if(nextPos[curPos]!=-1) prevPos[nextPos[curPos]] = prevPos[curPos]; // 2의 작업
sb.setCharAt(curPos, 'X'); // 삭제될 때마다 해당 위치를 X 로 갱신
if(nextPos[curPos]!=-1) curPos = nextPos[curPos];
else curPos = prevPos[curPos]; // 막칸이면 위로 올리기복구 연산
위 그림에서 4 -> 3 순서로 삭제를 마치고 가장 마지막에 삭제된 3을 복구한다고 가정하자. 이때 해줘야 할 작업은 다음과 같다.
1. 삭제된
3의 앞 칸이었던2의 다음 녀석을3으로 되돌리는 것
2. 삭제된3의 뒷 칸이었던5의 이전 녀석을3으로 되돌리는 것
3. 만약 복구 대상이 맨 윗칸이었으면 1의 작업은 무시
4. 만약 복구 대상이 막칸이었으면 2의 작업은 무시
이를 코드로 표현하면 다음과 같다.
int[] restore = stack.pop(); // 0: prev, 1: cur, 2: next
if(restore[0]!=-1) nextPos[restore[0]] = restore[1];
if(restore[2]!=-1) prevPos[restore[2]] = restore[1];
sb.setCharAt(restore[1], 'O');위 아래 이동
위로 이동할 때는 prev를 통해 입력으로 들어온 수치만큼 거슬러 올라가면 되고 아래로 이동할 때는 반대로 하면 된다. 이를 코드로 표현하면 다음과 같다.
case "U":
howFar = Integer.parseInt(stk.nextToken());
while(howFar-- > 0) curPos = prevPos[curPos];
break;
case "D":
howFar = Integer.parseInt(stk.nextToken());
while(howFar-- > 0) curPos = nextPos[curPos];
break;전체를 다 살펴보고 나면 LinkedList를 가져다 바로 쓰는 게 아니라, 직접 구현하는 방식으로 사용한 걸 알 수 있다.
내가 처음부터 바로 풀지 못했던 가장 큰 이유는 아마 문제를 보고 LinkedList를 쓰면 되겠구나 라는 생각만 했지, 이걸 구현하는 관점으로 써야겠다는 생각은 전혀 하지 못했기 때문이 아닐까 싶다.
아래는 내가 제출한 코드다.
import java.io.*;
import java.util.Stack;
import java.util.StringTokenizer;
public class TableEditing {
static Stack<int[]> stack = new Stack<>();
static int curPos;
static int[] prevPos, nextPos;
static StringBuilder sb = new StringBuilder();
static String solution(int n, int k, String[] cmd) {
init(n, k);
operateOrder(cmd);
return sb.toString();
}
static void operateOrder(String[] cmd){
for(String order: cmd){
StringTokenizer stk = new StringTokenizer(order);
int howFar = 0;
switch(stk.nextToken()){
case "C":
stack.add(new int[]{prevPos[curPos], curPos, nextPos[curPos]});
if(prevPos[curPos]!=-1) nextPos[prevPos[curPos]] = nextPos[curPos];
if(nextPos[curPos]!=-1) prevPos[nextPos[curPos]] = prevPos[curPos];
sb.setCharAt(curPos, 'X');
if(nextPos[curPos]!=-1) curPos = nextPos[curPos];
else curPos = prevPos[curPos]; // 맨 밑 칸이면 위로 올리기
break;
case "Z":
int[] restore = stack.pop();
if(restore[0]!=-1) nextPos[restore[0]] = restore[1];
if(restore[2]!=-1) prevPos[restore[2]] = restore[1];
sb.setCharAt(restore[1], 'O');
break;
case "U":
howFar = Integer.parseInt(stk.nextToken());
while(howFar-- > 0) curPos = prevPos[curPos];
break;
case "D":
howFar = Integer.parseInt(stk.nextToken());
while(howFar-- > 0) curPos = nextPos[curPos];
break;
}
}
}
static void init(int n, int k){
curPos = k;
prevPos = new int[n]; nextPos = new int[n];
for(int i=0; i<n; i++){
prevPos[i] = i-1;
nextPos[i] = i+1;
sb.append('O');
}
nextPos[n-1] = -1;
}
public static void main(String args[]) throws IOException {
BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = 8; int k = 2;
String[] cmd = { "D 2", "C", "U 3", "C", "D 4", "C", "U 2", "Z", "Z", "U 1", "C" };
bfw.write(solution(n,k,cmd));
bfw.close();
}
}오늘 배운 것
- 커서를 계속 움직여가며 삭제 및 삽입이 일어나는 문제는 prev, next 정보를 함께 다뤄주면 훨씬 연산 횟수가 줄어든다는 것!
- StringBuilder 에는
setCharAt()메소드가 있다. 잘 사용하자.
2021.03.02 재시도 ( 실패 )
다시 풀었는데 분명히 로직은 맞는데도 계속 틀려서 3시간을 헤맸는데 원인을 찾기는 했다. 그런데 이 원인이 왜 틀리는 건지는 도저히 모르겠다. 돌아버리겠다. 3시간을...!! 씨바....
기존에 UP 또는 DOWN 명령을 받았을 때 몇 칸이나 움직여야 하는지를 Integer.parseInt(stk.nextToken())를 통해서 얻었다.
그런데 다시 풀 때는 Character.getNumericValue(cmd[i].charAt(2))를 통해서 얻었다.
딱 이 한 줄만 달랐는데 getNumericValue() 메소드를 썼을 때는 틀리고 Integer.parseInt() 메소드를 쓰면 맞는다. 시발 개빡치네
아래는 새롭게 풀은 코드다. 진즉부터 맞았는데 2시간을 더 썼네. 험하다 험해
import java.io.*;
import java.util.ArrayList;
import java.util.Stack;
import java.util.StringTokenizer;
public class TableEditing {
static ArrayList<Info> list = new ArrayList<>();
static String solution(int n, int k, String[] cmd) {
init(n);
StringBuilder sb = new StringBuilder();
Stack<Integer> deleted = new Stack<>();
for(String thisCmd: cmd){
StringTokenizer stk = new StringTokenizer(thisCmd);
String order = stk.nextToken();
switch (order) {
case "C": // 삭제
list.get(k).status = 0;
deleted.add(k);
if (list.get(k).prev != -1) list.get(list.get(k).prev).next = list.get(k).next;
if (list.get(k).next != -1) list.get(list.get(k).next).prev = list.get(k).prev;
k = (list.get(k).next == -1 ? list.get(k).prev : list.get(k).next); // 마지막 셀이면 그 전으로, 아니면 그 후로
break;
case "Z": // 복구
int restoredPos = deleted.pop();
list.get(restoredPos).status = 1;
if (list.get(restoredPos).prev != -1)
list.get(list.get(restoredPos).prev).next = restoredPos;
if (list.get(restoredPos).next != -1)
list.get(list.get(restoredPos).next).prev = restoredPos;
break;
case "U": {
int distance = Integer.parseInt(stk.nextToken());
while (distance-- > 0)
k = list.get(k).prev;
break;
}
default: {
int distance = Integer.parseInt(stk.nextToken());
while (distance-- > 0)
k = list.get(k).next;
break;
}
}
}
for(int i=0; i<n; i++)
sb.append((list.get(i).status==1 ? 'O' : 'X'));
return sb.toString();
}
static void init(int n){
for(int i=0; i<=n-2; i++)
list.add(new Info(i-1, i+1, 1));
list.add(new Info(n-2, -1, 1));
}
static class Info{
int prev, next, status;
Info(int prev, int next, int status){
this.prev = prev;
this.next = next;
this.status = status;
}
}
public static void main(String args[]) throws IOException {
BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = 8; int k = 2;
String[] cmd = { "D 2", "C", "U 3", "C", "D 4", "C", "U 2", "Z", "Z", "U 1", "C" };
String res = solution(n,k,cmd);
bfw.write(res);
bfw.close();
}
}아.... 쓰면서 깨달았다.....
getNumericValue() 메소드를 쓸 때 param 으로 넘겨주는 놈이 charAt(2)이기 때문에... 만약 U 12라는 명령어가 넘어오면 1만 받게 되는 거다.... 12를 받아야 하는데.... 진짜 개빡치네....... 정말 병신이다 ^^
