[프로그래머스/Level3] 표 편집 (JAVA)

📖 문제

프로그래머스

 

 

 

💡  풀이 방식

• 스택

필요 자료구조
- 이전 노드 위치 기억용 배열 preArr
- 다음 노드 위치 기억용 배열 nextArr
- 삭제한 위치의 노드 정보 저장용 스택 ⭐

 

. preArr, nextArr 배열을 사용한다.

  - 각 인덱스에 해당하는 위치의 이전 노드 위치, 다음 노드 위치를 기억한다.

  - 맨 마지막 노드의 다음 노드는 -1로 설정해둔다.

 

. 크기 n만큼 'O' 문자열을 만든다.

 

. 각 명령에 맞는 작업을 수행한다.

1. 위로 이동하는 경우, 값만큼 현재 위치 k를 위로 이동한다.

int v = Integer.parseInt(cmd[i].substring(2));
while(v --> 0) {
    k = preArr[k];
}

 

 

2. 아래로 이동하는 경우, 값만큼 k를 아래로 이동한다.

else if(c == 'D') {
    int v = Integer.parseInt(cmd[i].substring(2));
    while(v --> 0) {
        k = nextArr[k];
    }
}

 

 

3. 현재 위치를 삭제하는 경우

- 삭제하는 노드의 정보를 스택에 저장한다. (복구 시 가장 최근 삭제된 값부터 복구하므로)

- 만약 현재 위치 k의 이전 위치가 맨 마지막 (-1)이 아니라면, 현재 노드를 삭제한 후 앞뒤를 연결한다. (연결 리스트가 필요한 이유)

- 만약 현재 위치 k의 다음 위치가 맨 마지막( -1)이 아니라면, 현재 노드를 삭제한 후 앞뒤를 연결한다.

- k 위치에서 삭제가 발생했으므로, StringBuilder의 k 위치를 X 표시로 변경한다.

- 만약 삭제된 행이 가장 마지막 행인 경우 바로 윗 행을 선택한다. 마지막 행이 아니라면, 다음 행을 선택하도록 한다.

 

4. 가장 최근 삭제된 행을 되돌린다.

 - 스택에서 가장 최근에 저장된 노드 정보를 가져온다. 

 - 이전 위치 배열의 다음 값, 다음 위치 배열의 이전 값으로 현재 값을 저장해 연결 정보를 복구한다.

 - 'O' 문자로 변경한다.

 

 

stack.push(new Node(preArr[k], k, nextArr[k]));  // 삭제하는 노드 정보 스택에 추가하기
                
if(preArr[k] != -1)    nextArr[preArr[k]] = nextArr[k]; // 현재 노드 삭제 후 앞뒤 연결
if(nextArr[k] != -1)   preArr[nextArr[k]] = preArr[k];

sb.setCharAt(k, 'X');

if(nextArr[k] != -1)   k = nextArr[k];
else                   k = preArr[k];   // 마지막 행인 경우에 바로 윗 행 선택

 

 

 

💥 유의사항

- 현재 인덱스의 이전 행과 다음 행 정보를 모두 저장해 둬야 한다.

- 마지막 행과 첫 행은 연결되어 있다.

 

 

🔺 코드

import java.util.*;
 
class Solution {
    public String solution(int n, int k, String[] cmd) {
        int[] preArr = new int[n];  // 이전 노드 위치 기억용 배열
        int[] nextArr = new int[n]; // 다음 노드 위치 기억용 배열
        
        for(int i = 0 ; i < n ; i++) {
            preArr[i]  = i-1;
            nextArr[i] = i+1;
        }
        nextArr[n-1] = -1;
        
        Stack<Node> stack = new Stack<>(); // ☀️ 삭제한 위치의 노드 정보 저장용 스택
        StringBuilder sb = new StringBuilder("O".repeat(n));    // 크기 n만큼 'O' 문자열 만들기
                
        for(int i = 0 ; i < cmd.length ; i++) {
            char c = cmd[i].charAt(0);
            
            // 위로 이동
            if(c == 'U') {
                int v = Integer.parseInt(cmd[i].substring(2));
                while(v --> 0) {
                    k = preArr[k];
                }
            }
            // 아래로 이동
            else if(c == 'D') {
                int v = Integer.parseInt(cmd[i].substring(2));
                while(v --> 0) {
                    k = nextArr[k];
                }
            }
            // 현재 위치 삭제
            else if(c == 'C') {
                stack.push(new Node(preArr[k], k, nextArr[k])); // 삭제하는 노드 정보 스택에 추가하기
                
                if(preArr[k] != -1)    nextArr[preArr[k]] = nextArr[k]; // 현재 노드 삭제 후 앞뒤 연결
                if(nextArr[k] != -1)   preArr[nextArr[k]] = preArr[k];
                
                sb.setCharAt(k, 'X');
                
                if(nextArr[k] != -1)   k = nextArr[k];
                else                   k = preArr[k];   // 마지막 행인 경우에 바로 윗 행 선택
            }
            // 가장 최근 삭제된 행 되돌리기
            else if(c == 'Z') {
                Node now = stack.pop(); // 가장 최근 삭제한 노드 정보 가져오기
                
                if(now.pre != -1)  nextArr[now.pre] = now.cur;  // 연결 정보 복구
                if(now.next != -1) preArr[now.next] = now.cur;
                sb.setCharAt(now.cur, 'O');
            }
        }
              
        return sb.toString();
    }
}
 
class Node {
    int pre, cur, next;
    
    public Node(int pre, int cur, int next) {
        this.pre = pre; // 이전 노드
        this.cur = cur; // 현재 위치
        this.next = next; // 다음 노드
    }
}

 

 

➕ 다른 풀이 방식

- 삭제 여부를 boolean형으로 나타내서 출력할 때 활용하는 방식을 사용하셨다. (내가 처음에 생각했던  방식)

Programmers - 표 편집(Java)

 

 

- 멋진 풀이,,

프로그래머스 level 3 ) 표 편집

---

💦 어려웠던 점

- 현재 위치 삭제(C)와 가장 최근 삭제된 행 되돌리기(Z) 가 어려웠다.

 

🧐 새로 알게 된 내용

- 가장 마지막으로 삭제된 위치의 정보를 저장할 때 스택을 사용할 아이디어를 얻게 되었다.

- LinkedList의 원소 탐색 시 시간 복잡도 O(N) * 1차원 배열 사용해 인덱스로 접근 시 시간 복잡도 O(1)

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 풀이 참고

[프로그래머스]표 편집 - JAVA

[프로그래머스] 2021 카카오 채용연계형 인턴십 - 표 편집 (Java)

 

 

✔ 그림 참고

Programmers - 표 편집(Java)