[프로그래머스] 표 편집 - Java
문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/81303
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
업무용 소프트웨어를 개발하는 니니즈웍스의 인턴인 앙몬드는 명령어 기반으로 표의 행을 선택, 삭제, 복구하는 프로그램을 작성하는 과제를 맡았습니다. 세부 요구 사항은 다음과 같습니다
위 그림에서 파란색으로 칠해진 칸은 현재 선택된 행을 나타냅니다. 단, 한 번에 한 행만 선택할 수 있으며, 표의 범위(0행 ~ 마지막 행)를 벗어날 수 없습니다. 이때, 다음과 같은 명령어를 이용하여 표를 편집합니다.
- "U X": 현재 선택된 행에서 X칸 위에 있는 행을 선택합니다.
- "D X": 현재 선택된 행에서 X칸 아래에 있는 행을 선택합니다.
- "C" : 현재 선택된 행을 삭제한 후, 바로 아래 행을 선택합니다. 단, 삭제된 행이 가장 마지막 행인 경우 바로 윗 행을 선택합니다.
- "Z" : 가장 최근에 삭제된 행을 원래대로 복구합니다. 단, 현재 선택된 행은 바뀌지 않습니다.
예를 들어 위 표에서 "D 2"를 수행할 경우 아래 그림의 왼쪽처럼 4행이 선택되며, "C"를 수행하면 선택된 행을 삭제하고, 바로 아래 행이었던 "네오"가 적힌 행을 선택합니다(4행이 삭제되면서 아래 있던 행들이 하나씩 밀려 올라오고, 수정된 표에서 다시 4행을 선택하는 것과 동일합니다).
다음으로 "U 3"을 수행한 다음 "C"를 수행한 후의 표 상태는 아래 그림과 같습니다.
다음으로 "D 4"를 수행한 다음 "C"를 수행한 후의 표 상태는 아래 그림과 같습니다. 5행이 표의 마지막 행 이므로, 이 경우 바로 윗 행을 선택하는 점에 주의합니다.
다음으로 "U 2"를 수행하면 현재 선택된 행은 2행이 됩니다.
위 상태에서 "Z"를 수행할 경우 가장 최근에 제거된 "라이언"이 적힌 행이 원래대로 복구됩니다.
다시한번 "Z"를 수행하면 그 다음으로 최근에 제거된 "콘"이 적힌 행이 원래대로 복구됩니다. 이때, 현재 선택된 행은 바뀌지 않는 점에 주의하세요.
이때, 최종 표의 상태와 처음 주어진 표의 상태를 비교하여 삭제되지 않은 행은 "O", 삭제된 행은 "X"로 표시하면 다음과 같습니다.
처음 표의 행 개수를 나타내는 정수 n, 처음에 선택된 행의 위치를 나타내는 정수 k, 수행한 명령어들이 담긴 문자열 배열 cmd가 매개변수로 주어질 때, 모든 명령어를 수행한 후 표의 상태와 처음 주어진 표의 상태를 비교하여 삭제되지 않은 행은 O, 삭제된 행은 X로 표시하여 문자열 형태로 return 하도록 solution 함수를 완성해주세요.
제한사항
- 5 ≤ n ≤ 1,000,000
- 0 ≤ k < n
- 1 ≤ cmd의 원소 개수 ≤ 200,000
- cmd의 각 원소는 "U X", "D X", "C", "Z" 중 하나입니다.
- X는 1 이상 300,000 이하인 자연수이며 0으로 시작하지 않습니다.
- X가 나타내는 자연수에 ',' 는 주어지지 않습니다. 예를 들어 123,456의 경우 123456으로 주어집니다.
- cmd에 등장하는 모든 X들의 값을 합친 결과가 1,000,000 이하인 경우만 입력으로 주어집니다.
- 표의 모든 행을 제거하여, 행이 하나도 남지 않는 경우는 입력으로 주어지지 않습니다.
- 본문에서 각 행이 제거되고 복구되는 과정을 보다 자연스럽게 보이기 위해 "이름" 열을 사용하였으나, "이름"열의 내용이 실제 문제를 푸는 과정에 필요하지는 않습니다. "이름"열에는 서로 다른 이름들이 중복없이 채워져 있다고 가정하고 문제를 해결해 주세요.
- 표의 범위를 벗어나는 이동은 입력으로 주어지지 않습니다.
- 원래대로 복구할 행이 없을 때(즉, 삭제된 행이 없을 때) "Z"가 명령어로 주어지는 경우는 없습니다.
- 정답은 표의 0행부터 n - 1행까지에 해당되는 O, X를 순서대로 이어붙인 문자열 형태로 return 해주세요.
- 5 ≤ n ≤ 1,000
- 1 ≤ cmd의 원소 개수 ≤ 1,000
- 주어진 조건 외 추가 제한사항 없습니다.
입출력 예 설명
입출력 예 #1
문제의 예시와 같습니다.
입출력 예 #2
다음은 9번째 명령어까지 수행한 후의 표 상태이며, 이는 입출력 예 #1과 같습니다.
10번째 명령어 "U 1"을 수행하면 "어피치"가 적힌 2행이 선택되며, 마지막 명령어 "C"를 수행하면 선택된 행을 삭제하고, 바로 아래 행이었던 "제이지"가 적힌 행을 선택합니다.
따라서 처음 주어진 표의 상태와 최종 표의 상태를 비교하면 다음과 같습니다.
제한시간 안내
- 정확성 테스트 : 10초
- 효율성 테스트 : 언어별로 작성된 정답 코드의 실행 시간의 적정 배수
풀이 방법
- 초기 풀이에는 ArrayList를 사용하여 값을 넣어 명령어에 맞게 처리를 하려고 했다.
- "C'명령어인 삭제시에는 Stack에 해당 인덱스 번호를 저장하고, "Z"명령어가 나오면 pop을 이용해 복구하여 찾으려했다.
초기 코드
import java.util.Stack;
import java.util.ArrayList;
class Solution {
public String solution(int n, int k, String[] cmd) {
//정답 문자열
StringBuilder answer = new StringBuilder();
//배열 생성 및 초기화
ArrayList<Integer> arr = new ArrayList<>();
for(int i = 0; i < n; i++){
arr.add(i);
}
//삭제 기록할 스택
Stack<Integer> del = new Stack<>();
int num = 0;
//cmd의 내용을 하나하나 실행한다.
for(String command : cmd){
String[] split = command.split(" ");
String op = split[0];
switch(op){
case "U":
num = Integer.parseInt(split[1]);
k -= num;
break;
case "D":
num = Integer.parseInt(split[1]);
k += num;
break;
case "C":
//스택에 삭제 기록 저장
del.push(arr.remove(k));
//마지막 행이라면, 한칸 전으로 이동
if(k == arr.size()){
k--;
}
break;
case "Z":
int recover = del.pop();
int idx = 0;
//복구할 idx를 찾아서 값을 계속 증가시켜준다.
while(idx < arr.size() && arr.get(idx) < recover){
idx++;
}
//찾은 항에 값 추가
arr.add(idx, recover);
//이때 k가 복구된 곳 뒤에 있으면, 뒤로 밀리므로 1추가 해줌
if(recover <= arr.get(k)){
k++;
}
break;
default:
break;
}
}
for(int i = 0; i < n; i++){
//삭제 안됐으면 O추가
if(arr.contains(i)){
answer.append("O");
}
else{
answer.append("X");
}
}
return answer.toString();
}
}발견한 문제점
- 이런식으로 풀이를 하니, n이 최대 100만까지 가는 상황에서 삭제 및 복구 명령어를 수행할 때 idx를 찾는 과정에서 0부터 해당 원소까지 찾는 과정을 반복하다보니, 정확성은 있으나 효율성이 떨어지는 것을 발견했다.
- 시간 초과를 해결하기 위해, Double Linked List를 사용하기로 하였다.
Double Linked List란?
- Linked List의 한 종류로, 노드가 두 개의 포인터를 가지고 있는 데이터 구조로, 각각 이전과 다음 노드를 가리킨다.
출처 - https://itwiki.kr/w/%EC%9D%B4%EC%A4%91_%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8#google_vignette
특징
- Single Linked List와 다르게, 노드에서 이전, 다음 양방향으로 이동이 가능
- 특정 위치에서 노드 삽입, 삭제가 효율적으로 이루어짐
- 하지만 그 만큼, 변수가 더 생성되기 때문에 메모리를 잡아먹는 단점도 있음
- 포인터를 관리해야하기 때문에 구현에 복잡성이 추가
Double Linked List를 사용한 이유
- ArrayList 요소 삭제시 해당 요소를 삭제한 뒤 다른 요소를 앞으로 가져와야하는 작업이 필요한데, O(n)이 소요된다. n이 100만인 경우에 0 번을 삭제했을 때 999,999번을 수행해야 한다는 뜻
- 또한 복구시에도 요소를 찾아 원래 위치에 전달을 해야하는데 이것 또한 O(n)의 복잡도를 가지기 때문에 비효율적이었다.
- Double Linked List의 경우, 요소 삭제 또는 복구시 이전 노드 혹은 다음 노드만 변경하면 되기 때문에, O(1)의 시간 복잡도를 가짐
- 따라서, 시간적인 측면에서 생각했을 때 Double Linked List가 효율적이라고 판단했고 사용하였다.
개선된 풀이 코드
import java.util.Stack;
class Solution {
public String solution(int n, int k, String[] cmd) {
// 이중 연결 리스트
int[] prev = new int[n];
int[] next = new int[n];
boolean[] removed = new boolean[n]; // 삭제 여부 확인
// 초기화
for (int i = 0; i < n; i++) {
prev[i] = i - 1;
next[i] = i + 1;
}
next[n - 1] = -1; // 마지막 행은 next가 없음
// 삭제된 행 저장
Stack<Integer> stack = new Stack<>();
// 명령어 처리
for (String command : cmd) {
char op = command.charAt(0);
if (op == 'U') { // 위로 이동
int x = Integer.parseInt(command.substring(2));
for (int i = 0; i < x; i++) {
k = prev[k];
}
} else if (op == 'D') { // 아래로 이동
int x = Integer.parseInt(command.substring(2));
for (int i = 0; i < x; i++) {
k = next[k];
}
} else if (op == 'C') { // 현재 행 삭제
stack.push(k); // 삭제된 행 저장
removed[k] = true; // 삭제 상태 기록
if (prev[k] != -1) {
next[prev[k]] = next[k];
}
if (next[k] != -1) {
prev[next[k]] = prev[k];
}
// 삭제 후 다음 행으로 이동
k = (next[k] != -1) ? next[k] : prev[k];
} else if (op == 'Z') { // 삭제된 행 복구
int restored = stack.pop(); // 복구할 행
removed[restored] = false; // 삭제 상태 해제
if (prev[restored] != -1) {
next[prev[restored]] = restored;
}
if (next[restored] != -1) {
prev[next[restored]] = restored;
}
}
}
// 결과 문자열 생성
StringBuilder answer = new StringBuilder();
for (int i = 0; i < n; i++) {
answer.append(removed[i] ? 'X' : 'O');
}
return answer.toString();
}
}결과
회고
- 자료구조에 대해 아직 부족함을 알 수 있었고... 시간 복잡도 정보에 대해서 좀 알아야겠다는 생각을 했다.
- Lv1이나 Lv2 문제도 좀 풀면서, 코딩테스트에 대한 감좀 살려야겠다!