안녕하세요. 오늘은 프로그래머스의 표 편집 문제를 풀어보겠습니다. 이 문제는 2021년 카카오 채용연계형 인턴십과정에서 출제되었습니다.
1) 문제 링크
https://programmers.co.kr/learn/courses/30/lessons/81303
2) 맞은 코드 문제 풀이
✔ tableSize 변수 이용
cmd 배열에서 C가 입력되었을 경우 행이 삭제되므로 tableSize가 1 줄어들고, Z가 입력되었을 경우 이전에 삭제된 행이 복구되므로 tableSize가 1 늘어납니다. "어떤행이 삭제/복구되었는지"는 stack이 모두 저장해주므로, 변수를 활용해 table의 크기만 기억해주면 됩니다.
✔ cmd "C", cmd "Z" : stack 이용
cmd 배열에서 C가 입력되었을 경우 stack에 해당 배열의 행을 저장해줍니다. cmd 배열에서 Z가 입력되었을 경우 stack에서 가장 위에 있는 원소를 꺼내줍니다.
✔ return할 String : StringBuilder 이용
cmd 배열에 저장된 String값에 따라 로직을 모두 수행한 후 stack에 남아있는 행들은 마지막까지 복구되지 않고 삭제된 값입니다. StringBuilder를 이용해 tableSize만큼 O로 채우고, stack에 저장되어 있는 행 값에 따라 StringBuilder 사이사이에 X를 끼워넣어줍니다.
✔ Deque?
저는 Stack 클래스가 아닌 Deque 인터페이스를 사용했습니다. Java 공식문서에는 Stack의 사용을 지양하고, 대신 Deque를 사용하라고 나와있습니다. 자세한 설명은 여기를 참고해주세요.!
3) 틀린 코드 (정확성 O, 효율성 시간초과)
✔ 시간초과의 이유
LinkedList 하나를 더 둬서 문제를 풀었었고, 정확성은 모두 맞았지만 효율성에서 시간초과가 발생했습니다. LinkedList는 중간index를 찾아가는 데 O(n)시간이 소요되기 때문에 해당 로직에서 시간이 오래 걸렸습니다.
class Solution {
private static final char UP = 'U';
private static final char DOWN = 'D';
private static final char REMOVE = 'C';
private static final char RECOVER = 'Z';
private static final String YES = "O";
private static final String NO = "X";
public String solution(int n, int k, String[] cmd) {
List<Integer> list = new LinkedList<>();
Deque<Map<Integer, Integer>> stack = new LinkedList<>();
StringBuilder answer = new StringBuilder();
int pivot = k; //인덱스를 저장하고 있는 변수
for (int i = 0; i < n; i++) {
list.add(i);
answer.append(YES);
}
for (String str : cmd) {
char c = str.charAt(0);
if (c == UP) {
int go = Integer.parseInt(str.split(" ")[1]);
pivot -= go;
if (pivot <= 0) pivot = 0;
} else if (c == DOWN) {
int go = Integer.parseInt(str.split(" ")[1]);
pivot += go;
if (pivot >= list.size() - 1) pivot = list.size() - 1;
} else if (c == REMOVE) {
int key = pivot;
int value = list.get(pivot);
Map<Integer, Integer> map = new HashMap<>();
map.put(key, value);
stack.push(map);
list.remove(pivot);
answer.replace(value, value + 1, NO);
if (pivot >= list.size() - 1) pivot = list.size() - 1;
} else if (c == RECOVER) {
Map<Integer, Integer> map = stack.pop();
List<Integer> keySet = new ArrayList<>(map.keySet());
int key = keySet.get(0);
int value = map.get(key);
answer.replace(value, value + 1, YES);
list.add(key, value);
if (key <= pivot) pivot += 1;
}
}
return answer.toString();
}
}4) 맞은 코드 (정확성 O, 효율성 O)
import java.util.*;
class Solution {
private static final char UP = 'U';
private static final char DOWN = 'D';
private static final char REMOVE = 'C';
private static final char RECOVER = 'Z';
private static final String YES = "O";
private static final String NO = "X";
public String solution(int n, int k, String[] cmd) {
Deque<Integer> remove = new ArrayDeque<>();
int tableSize = n;
int pivot = k;
StringBuilder answer = new StringBuilder();
for (int i = 0; i < cmd.length; i++) {
char c = cmd[i].charAt(0);
if (c == UP) {
pivot -= Integer.valueOf(cmd[i].substring(2));
} else if (c == DOWN) {
pivot += Integer.valueOf(cmd[i].substring(2));
} else if (c == REMOVE) {
remove.push(pivot);
tableSize -= 1;
if (pivot == tableSize) pivot -= 1;
} else if (c == RECOVER) {
int r = remove.pop();
if (pivot >= r) pivot += 1;
tableSize += 1;
}
}
for (int i = 0; i < tableSize; i++) {
answer.append(YES);
}
while (!remove.isEmpty()) {
answer.insert(remove.pop().intValue(), NO);
}
return answer.toString();
}
}5) 틀린 이유/ 느낀점
✔ 결과표를 만들 필요가 없었음(LinkedList 필요없음)
"주어진 그대로 풀지 말아야 한다" 는 사실을 다시 한 번 느낄 수 있었던 문제였습니다.
문제 설명에서 표가 하도 많이 나와서 당연히 Array 혹은 LinkedList를 이용해 표를 구현해야한다고 생각했습니다.
정답을 본 후 찬찬히 생각해보니 제가 선언한 LinkedList의 역할을 이미 Stack이 수행하고 있었습니다. (문제에 낚여 불필요한 변수를 생성했습니다...)
복잡하게 생각하지 말고, 목적에 따라 필요한 만큼만 변수를 선언해서 선언한 변수를 최대한 활용하여 문제를 풀어야겠다고 느꼈습니다.
