코딩테스트 연습 - 표 편집
8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z"] "OOOOXOOO" 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"] "OOXOXOOO"
programmers.co.kr
문제 설명
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
업무용 소프트웨어를 개발하는 니니즈웍스의 인턴인 앙몬드는 명령어 기반으로 표의 행을 선택, 삭제, 복구하는 프로그램을 작성하는 과제를 맡았습니다. 세부 요구 사항은 다음과 같습니다
위 그림에서 파란색으로 칠해진 칸은 현재 선택된 행을 나타냅니다. 단, 한 번에 한 행만 선택할 수 있으며, 표의 범위(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
- 주어진 조건 외 추가 제한사항 없습니다.
| n | k | cmd | result |
| 8 | 2 | ["D 2","C","U 3","C","D 4","C","U 2","Z","Z"] | "OOOOXOOO" |
| 8 | 2 | ["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"] | "OOXOXOOO" |
입출력 예 설명
입출력 예 #1
문제의 예시와 같습니다.
입출력 예 #2
다음은 9번째 명령어까지 수행한 후의 표 상태이며, 이는 입출력 예 #1과 같습니다.
10번째 명령어 "U 1"을 수행하면 "어피치"가 적힌 2행이 선택되며, 마지막 명령어 "C"를 수행하면 선택된 행을 삭제하고, 바로 아래 행이었던 "제이지"가 적힌 행을 선택합니다.
따라서 처음 주어진 표의 상태와 최종 표의 상태를 비교하면 다음과 같습니다.
제한시간 안내
- 정확성 테스트 : 10초
- 효율성 테스트 : 언어별로 작성된 정답 코드의 실행 시간의 적정 배수
풀이
실제 시험 때도 효율성에서 막혀서 풀지 못했던 문제. (요거만 맞췄으면 면접 갔는데...ㅠ)
첫 시도는 단순하게 구현 문제라고 생각하고 접근하였다.
answer에 n만큼 "O"를 담아두고, C명령어가 오는 경우 해당 위치를 "X"로 변경하고 복구를 위해 Stack에 위치 값을 저장하였다. 이렇게 구현하는 경우 정확도는 문제가 없었으나 효율성에서 문제가 발생했다.
U이나 D 명령어가 오는 경우 이동하는 범위 내에 지워진 데이터라는 표시인 "X"가 있다면 발견된 만큼 더 이동해야한다.
예를 들어 OXXXXXO 인 상황이고 현재 위치가 0일 때 "D 1" 명령어가 들어오면 사실상 6번 이동하는 셈인 것이다.
문제를 처음 접하고 반년이 지난 지금, 다시 문제를 보니 연결리스트 문제라는 것이 보였다. 그래서 덜컥 Java에서 제공하는 LinkedList를 이용하여 구현을 시도했지만 여전히 해결되지 않았다.
LinkedList는 List 인터페이스의 구현체 중 하나이고, List 인터페이스는 get() 메소드를 통해서 인덱스를 통한 접근을 가능하게 하는데 LinkedList는 자료구조 특성상 인덱스를 통한 접근을 한다고 해도 O(n)의 시간이 걸린다. (앞에서부터 i번째까지 차례로 접근해야 하기 때문)
해당 문제의 의도는 연결리스트 자료구조를 이해하고 있고 직접 구현할 수 있는지를 물어보는 것이었다.
아래 블로그를 참고하여 코드를 작성하였다.
[프로그래머스] 표 편집 / 2021 카카오 채용연계형 인턴십 - JAVA
🖇️ 문제 링크 코딩테스트 연습 - 표 편집 업무용 소프트웨어를 개발하는 니니즈웍스의 인턴인 앙몬드는 명령어 기반으로 표의 행을 선택, 삭제, 복구하는 프로그램을 작성하는 과제를 맡았습
ltk3934.tistory.com
우선 연결리스트에 사용되는 Node를 클래스로 구현하였다.
class Node {
Node prev = null;
Node next = null;
boolean removed;
...
}Node는 이전 노드를 가리키는 prev와 다음 노드를 가리키는 next를 가진다. 그리고 해당 노드가 제거되었는지 여부를 나타내는 removed 필드를 갖는다.
Node는 cmd의 명령어에 따라 동작할 기능을 갖는다.
class Node {
...
public Node movePrev(int movement) {
Node node = this;
for (int i = 0; i < movement; i++) {
node = node.prev;
}
return node;
}
public Node moveNext(int movement) {
Node node = this;
for (int i = 0; i < movement; i++) {
node = node.next;
}
return node;
}
...
}
movePrev()는 입력받은 int값만큼 이전 노드로 이동하고 해당 노드를 리턴한다. 마찬가지로 moveNext()는 입력받은 int값만큼 다음 노드로 이동하고 해당 노드를 리턴한다. 이동 자체는 n값을 벗어날 일이 없다고 문제에서 전제를 했으므로 관련 예외 처리는 생략했다.
class Node {
...
public Node delete() {
this.removed = true;
Node prev = this.prev;
Node next = this.next;
if (prev != null) {
prev.next = next;
}
if (next != null) {
next.prev = prev;
return next;
}
return prev;
}
public void restore() {
this.removed = false;
Node prev = this.prev;
Node next = this.next;
if (prev != null) {
prev.next = this;
}
if (next != null) {
next.prev = this;
}
}
}delete()는 해당 Node를 제거하는 메소드다. removed를 true로 변경하고 본인의 앞, 뒤 Node들을 이어준다. 문제의 조건에 따라 해당 Node가 지워지면 현재 가리키는 Node를 다음 Node로 지정하기위해 next를 리턴한다. 단, next == null은 해당 노드가 마지막 노드라는 의미이므로 이 경우에는 prev를 리턴해야 한다.
restore()는 해당 Node를 복구하는 메소드다. removed를 false로 변경하고, 해당 노드의 앞, 뒤 Node들이 다시 해당 노드를 바라보도록 한다.
여기서 조금 헷갈리는 부분이 있었는데 지금 구현한 연결리스트는 이중 연결리스트로 양쪽 노드가 서로 접근이 가능하다. this.prev != this.prev.next 일 수도 있단 것이다. 삭제, 복구시키는 메소드는 그러한 특징을 이용한 것이다. 삭제할 때는 prev와 next에서의 참조를 변경한 것이고, 복구시키는 경우에는 원래 Node에 남아있는 prev와 next를 참조하여 다시 돌려놓는 것이다.
본격적으로 solution() 코드를 살펴보자.
Stack<Node> deletedRows = new Stack<>();
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];
}명령어를 통해 지워지는 Node는 Stack으로 보관을 하는데, 복구 시 가장 최근에 삭제된 값부터 복구하기 때문에 Stack 자료구조를 이용하였다.
nodes는 Node가 담긴 1차원 배열로 인덱스를 통한 O(1)의 접근이 가능하게 하기 위함 + 결과 리턴을 위함이다. n번 for문을 순회하며 배열의 각 원소들을 초기화시키는데 Node들의 prev와 next도 지정해준다.
Node current = nodes[k];
for (String command : cmd) {
char operation = command.charAt(0);
switch (operation) {
case UP:
int movement = Integer.parseInt(command.split(" ")[1]);
current = current.movePrev(movement);
break;
case DOWN:
movement = Integer.parseInt(command.split(" ")[1]);
current = current.moveNext(movement);
break;
case CLEAR:
deletedRows.add(current);
current = current.delete();
break;
case RESTORE:
Node node = deletedRows.pop();
node.restore();
break;
}
}시작은 k번째 데이터. 즉, k번째 Node에서 시작한다.
cmd를 읽어 switch문으로 명령어에 따른 동작을 하도록 작성하였다.
기능 자체를 Node의 메소드로 구현해두어 비교적 가독성 좋은 코드를 작성한 것 같아서 만족스럽다:)
StringBuilder answer = new StringBuilder();
for (int i = 0; i < n; i++) {
if (nodes[i].removed) {
answer.append("X");
continue;
}
answer.append("O");
}
return answer.toString();answer를 도출해내는 과정이다. StringBuilder를 이용하여 for문을 순회하면서 Node의 removed 상태에 따라 "O", "X"를 append()한다.
코드
import java.util.Stack;
public class Solution {
private static final char UP = 'U';
private static final char DOWN = 'D';
private static final char CLEAR = 'C';
private static final char RESTORE = 'Z';
public String solution(int n, int k, String[] cmd) {
Stack<Node> deletedRows = new Stack<>();
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];
}
Node current = nodes[k];
for (String command : cmd) {
char operation = command.charAt(0);
switch (operation) {
case UP:
int movement = Integer.parseInt(command.split(" ")[1]);
current = current.movePrev(movement);
break;
case DOWN:
movement = Integer.parseInt(command.split(" ")[1]);
current = current.moveNext(movement);
break;
case CLEAR:
deletedRows.add(current);
current = current.delete();
break;
case RESTORE:
Node node = deletedRows.pop();
node.restore();
break;
}
}
StringBuilder answer = new StringBuilder();
for (int i = 0; i < n; i++) {
if (nodes[i].removed) {
answer.append("X");
continue;
}
answer.append("O");
}
return answer.toString();
}
class Node {
Node prev = null;
Node next = null;
boolean removed;
public Node movePrev(int movement) {
Node node = this;
for (int i = 0; i < movement; i++) {
node = node.prev;
}
return node;
}
public Node moveNext(int movement) {
Node node = this;
for (int i = 0; i < movement; i++) {
node = node.next;
}
return node;
}
public Node delete() {
this.removed = true;
Node prev = this.prev;
Node next = this.next;
if (prev != null) {
prev.next = next;
}
if (next != null) {
next.prev = prev;
return next;
}
return prev;
}
public void restore() {
this.removed = false;
Node prev = this.prev;
Node next = this.next;
if (prev != null) {
prev.next = this;
}
if (next != null) {
next.prev = this;
}
}
}
}
'Tech > Problem Solving' 카테고리의 다른 글
| [프로그래머스] 월간 코드 챌린지 시즌3 - 금과 은 운반하기 (Java) (1) | 2022.02.02 |
|---|---|
| [프로그래머스] 2020 카카오 인턴십 - 보석 쇼핑 (Java) (0) | 2022.01.25 |
| [프로그래머스] 카카오 블라인드 리쿠르트 2018 - 셔틀 버스 (Java) (0) | 2022.01.21 |
| [프로그래머스] 카카오 블라인드 리쿠르트 2019 - 후보키 (Java) (0) | 2022.01.20 |
| [프로그래머스] 카카오 블라인드 리크루트 2020 -자물쇠와 열쇠 (Java) (0) | 2022.01.19 |
