문제
https://school.programmers.co.kr/learn/courses/30/lessons/81303
프로그래머스
SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
풀이 과정
이 문제는 연결 리스트 문제이다. 처음에는 자바에서 제공해주는 LinkedList로 접근했었는데, 효율성 테스트에서 실패했다.
이 문제는 리스트의 삽입/삭제를 효율적으로 처리할 수 있는 자료구조를 사용해야 한다.
왜 자바의 LinkedList는 실패하는 것일까?
기본적으로 연결 구조는 삽입/삭제는 빠르고, 읽는 속도가 느리다.
자바의 LinkedList는 노드 연결 구조를 가진다. 기본적으로 삽입/삭제 연산만을 보면 빠르지만, 삽입/삭제 시 해당 위치까지 이동해야 하므로 최악의 경우 시간복잡도가 O(N) 이다.
그러므로, LinkedList는 remove/add는 시간복잡도가 O(N)이기 때문에 최악의 경우 명령어 최대 200,000개, n이 최대 1,000,000개 이므로 시간초과가 발생한다.
문제 접근 방식
이중 연결 리스트 구조를 직접 구현해서 풀어보았다.
자료구조를 직접 구현해보았다면, 해볼만한 문제인 것 같다.
- 각 행을 Node로 표현한다.
- 각 Node는 prev(이전노드), next(다음노드)를 가진다.
- 헤드노드는 prev는 null이고, 꼬리노드는 next가 null이다.
- 그 외의 모든 노드는 prev, next로 연결된 구조이다.
- 이동(U, D)의 경우 연결된 노드를 따라 이동하면 된다.
- 삭제(C)의 경우 이전/다음 노드를 서로 연결 해준다. 삭제된 노드는 복구를 위해 Stack에 저장한다.
- 복구(Z)의 경우 복구할 노드를 Stack에서 꺼낸 다음 해당 노드를 연결해준다.
코드
class Solution {
static class Node {
Node prev;
Node next;
boolean removed;
// 이전 노드로 이동
public Node moveUp(int movement) {
Node temp = this;
for (int i = 0; i < movement; i++) {
temp = temp.prev;
}
return temp;
}
// 다음 노드로 이동
public Node moveDown(int movement) {
Node temp = this;
for (int i = 0; i < movement; i++) {
temp = temp.next;
}
return temp;
}
// 삭제(이전, 다음 노드를 서로 연결해준다.)
public Node remove() {
// 이전, 다음 노드를 서로 연결해준다.
this.removed = true;
// 헤드 노드
if (this.prev == null) {
this.next.prev = null;
return this.next;
}
// 꼬리 노드
if (this.next == null) {
this.prev.next = null;
return this.prev;
}
this.prev.next = this.next;
this.next.prev = this.prev;
return this.next;
}
// 복구
public void reStore() {
this.removed = false;
if (this.prev != null) {
this.prev.next = this;
}
if (this.next != null) {
this.next.prev = this;
}
}
}
public String solution(int n, int k, String[] cmds) {
Node[] nodes = new Node[n];
for (int i = 0; i < n; i++) {
nodes[i] = new Node();
if (i == 0) {
continue;
}
// 노드 연결
nodes[i - 1].next = nodes[i];
nodes[i].prev = nodes[i - 1];
}
Stack<Node> history = new Stack<>();
Node current = nodes[k];
for (String cmd : cmds) {
StringTokenizer st = new StringTokenizer(cmd);
String command = st.nextToken();
if (command.equals("U")) { // 위로 이동
int movement = Integer.parseInt(st.nextToken());
current = current.moveUp(movement);
} else if (command.equals("D")) { // 아래로 이동
int movement = Integer.parseInt(st.nextToken());
current = current.moveDown(movement);
} else if (command.equals("C")) { // 삭제
history.push(current);
current = current.remove();
} else if (command.equals("Z")) { // 복구
Node target = history.pop();
target.reStore();
}
}
StringBuilder answer = new StringBuilder();
for (int i = 0; i < n; i++) {
if (nodes[i].removed) {
answer.append("X");
} else {
answer.append("O");
}
}
return answer.toString();
}
}
'Algorithm' 카테고리의 다른 글
| [백준] 2346. 풍선 터뜨리기 (0) | 2025.08.29 |
|---|---|
| [Programmers] 2019 KAKAO BLIND RECRUITMENT 후보키 - JAVA (1) | 2025.08.28 |
| [백준] 27971. 강아지는 많을수록 좋다 - JAVA (1) | 2025.08.26 |
| [Programmers] 2021 KAKAO BLIND RECRUITMENT 순위 검색 - JAVA (0) | 2025.08.21 |
| [백준] 6497. 전력난 - JAVA (2) | 2025.08.20 |