[프로그래머스/자바] 표 편집 풀이 - 2021 카카오 채용연계형 인턴십

https://school.programmers.co.kr/learn/courses/30/lessons/81303

프로그래머스

 

2021 카카오 채용연계형 인턴십 Level 3 문제다.

 

 

처음엔 일반 배열 하나를 사용해서 삭제된 원소는 -1로 표시하고,

-1을 만나면 무시하는 방식으로 구현을 했었는데

이미 삭제된 원소까지 모두 접근을 해서 그런지 시간 초과가 떴다.

 

그 후에는 ArrayList를 사용했는데, 중간에 있는 원소를 삽입하고 삭제하는 속도가 느려 시간 초과가 뜬 것 같다.

그리고 java.util.LinkedList를 통해 구현을 하다가 안 풀려서

다른 분의 풀이를 참고해 배열로 구현하면 된다는 것을 깨달았다.

 

양방향 연결리스트이기 때문에

이전 노드를 저장할 pre[]와 다음 노드를 저장할 next[]를 생성하고 초기화한다.

 

즉 문제의 입출력 예시 #1 같은 경우에는 pre[]와 next[]가 아래와 같을 것이다.

pre  idx  next

-1     0     1

 0     1     2

 1     2     3

 2     3     4

 3     4     5

 4     5     6

 5     6     7

 6     7     -1

 

인덱스 i를 삭제한다고 했을 때, pre[i]의 next[i]를 next[i]로 변경하고,

next[i]의 pre[i]를 pre[i]로 변경한다.

그리고 삭제 시 스택에 pre[i], i, next[i]를 저장하고

복구 연산 시 스택에서 꺼내 삭제할 때와 반대로 수행하면 된다.

 

가장 위에 있는 원소를 삭제/복구 하려고 했을 때는 next만 지정해주고,

가장 아래에 있는 원소를 삭제/복구 하려고 했을 때는 pre만 지정해준다.

 

 

알고리즘을 풀며 연결리스트를 직접 구현한 적은 없어서 생각하기가 어려웠다.

양방향 연결리스트는 이전 노드와 다음 노드를 배열에 넣어 구현할 수 있다는 것과

StringBuilder 클래스의 setCharAt(int idx, char c) 함수를 기억해야 겠다.

 

 

import java.util.StringTokenizer;
import java.util.Stack;

class Solution {
    public String solution(int n, int k, String[] cmd) {
		StringTokenizer st;
		Stack<int[]> stack = new Stack<>();
		
		StringBuilder sb = new StringBuilder();
		sb.append("O".repeat(n));
		
		int[] pre = new int[n];
		int[] next = new int[n];
		
		for(int i=0;i<n;i++) {
			pre[i] = i - 1;
			next[i] = i + 1;
		}
		
		next[n - 1] = -1;

		for(int i=0;i<cmd.length;i++) {
			st = new StringTokenizer(cmd[i]);
			int tmp;
			
			switch(st.nextToken()) {
			case "U":
				tmp = Integer.parseInt(st.nextToken());
				while(tmp-- > 0) 
					k = pre[k];
				break;
			case "D":
				tmp = Integer.parseInt(st.nextToken());
				while(tmp-- > 0) 
					k = next[k];
				break;
			case "C":
				stack.push(new int[] {pre[k], k, next[k]});
				if(pre[k] != -1)
					next[pre[k]] = next[k];
				if(next[k] != -1)
					pre[next[k]] = pre[k];
				
				sb.setCharAt(k, 'X');

				if(next[k] == -1) 
					k = pre[k];
				else 
					k = next[k];
				break;
			case "Z":
				int[] arr = stack.pop();
				if(arr[0] != -1)
					next[arr[0]] = arr[1];
				if(arr[2] != -1)
					pre[arr[2]] = arr[1];
				
				sb.setCharAt(arr[1], 'O');
				break;
			}
		}

		return sb.toString();
    }
}