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

프로그래머스

---

❓ 문제

업무용 소프트웨어를 개발하는 니니즈웍스의 인턴인 앙몬드는 명령어 기반으로 표의 행을 선택, 삭제, 복구하는 프로그램을 작성하는 과제를 맡았습니다. 세부 요구 사항은 다음과 같습니다.

위 그림에서 파란색으로 칠해진 칸은 현재 선택된 행을 나타냅니다. 단, 한 번에 한 행만 선택할 수 있으며, 표의 범위(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"

---

✍🏻 풀이 과정

• 문제를 읽고 입출력 예시를 보면, 해당 인덱스 정보만 알면 된다는 것을 알 수 있다.
• 그래서 표나 연결리스트가 아닌 인덱스로 문제를 풀면 쉽게 풀릴 거라고 생각했다.
• 또한 최근에 삭제된 행을 복구한다는 것으로 미루어 볼 때 Stack을 이용하면 될 것 같았다.
• 가장 먼저 삭제된 값을 담아줄 Stack을 delete로 선언해주었다.
• 그리고 전체 사이즈의 값을 비교해주기 위해 size라는 변수를 선언한 후 n 값으로 초기화 해주었다.

import java.util.Stack;

public String solution(int n, int k, String[] cmd) {
   Stack<Integer> delete = new Stack<>();
   int size = n;
}

---

• 주어진 조건에 맞게 문자열 배열 cmd를 돌면서 비교할 수 있도록 반복문을 사용해주었다.
• 가장 맨 앞에 오는 문자에 따라 명령이 다르므로 맨 앞 글자를 비교해주기 위해 변수를 선언해주었다.
• swich-case문을 이용해 각 조건에 따른 동작을 분류해주었다.
• U이면 위로 올라가므로 인덱스 값이 작아지니 빼주었고, D이면 아래로 내려가므로 인덱스 값이 커지니 더해주었다.
• C이면 해당 행이 지워지므로 해당 인덱스 값을 스택에 넣어주고, 전체 사이즈를 줄였다.
• C일 경우, 해당 행이 지워지고 아래 행을 선택하는데, 이 행의 인덱스는 결국 지워진 인덱스이기 때문이다.
• 만약에 삭제 행이 마지막 행이면 k의 값을 한 번 더 빼주어, 현재의 마지막 행의 인덱스 값으로 만들어주었다.
• Z일 경우, 최근에 삭제된 행이 복구되므로 전체 사이즈를 늘려주었다.
• 만약 삭제된 행의 값이 k보다 작으면, 인덱스가 한 칸 밀려나므로 k의 값을 하나 더해주었다.
• 그리고 만약 k의 값이 0보다 작으면, 0 값으로 만들어주었다.

import java.util.Stack;

public String solution(int n, int k, String[] cmd) {
   
   ...
   
   for (String s : cmd) {
      char ch = s.charAt(0);
      switch (ch) {
         case 'U' -> k -= Integer.parseInt(s.substring(2));
         case 'D' -> k += Integer.parseInt(s.substring(2));
         case 'C' -> {
            delete.push(k);
            size--;
            if (k == size) k--;
         }
         case 'Z' -> {
            if (delete.pop() <= k) k++;
            size++;
         }
      }

      if (k < 0) k = 0;
   }
}

---

• StringBuilder를 이용하여 현재의 행의 크기만큼 "O"를 반복해주었다.
• 그리고 스택이 비어있지 않으면, 반복문을 돌며 해당 인덱스 위치에 "X"를 추가해주었다.

import java.util.Stack;

public String solution(int n, int k, String[] cmd) {
   
   ...

   StringBuilder ans = new StringBuilder();
   ans.append("O".repeat(Math.max(0, size)));
   while (!delete.isEmpty()) ans.insert(delete.pop(), "X");
   return ans.toString();
}

---

✍🏻 최종 풀이

import java.util.Stack;

public String solution(int n, int k, String[] cmd) {
   Stack<Integer> delete = new Stack<>();
   int size = n;

   for (String s : cmd) {
      char ch = s.charAt(0);
      switch (ch) {
         case 'U' -> k -= Integer.parseInt(s.substring(2));
         case 'D' -> k += Integer.parseInt(s.substring(2));
         case 'C' -> {
            delete.push(k);
            size--;
            if (k == size) k--;
         }
         case 'Z' -> {
            if (delete.pop() <= k) k++;
            size++;
         }
      }

      if (k < 0) k = 0;
   }

   StringBuilder ans = new StringBuilder();
   ans.append("O".repeat(Math.max(0, size)));
   while (!delete.isEmpty()) ans.insert(delete.pop(), "X");
   return ans.toString();
}

 

✍🏻 다른 사람이 푼 풀이 (노드로 연결시켜 푼 풀이)

public static String solution(int n, int k, String[] cmd) {
   Node[] node = new Node[1000001];
   Stack<Node> stack = new Stack<>();
   node[0] = new Node();

   for (int i = 1; i < n; i++) {
      node[i] = new Node();
      node[i].pre = node[i - 1];
      node[i - 1].next = node[i];
   }

   Node now = node[k];

   for (String s : cmd) {
      char ch = s.charAt(0);

      switch (ch) {
         case 'U' -> { // 위로 이동
            int num = Integer.parseInt(s.substring(2));
            for (int i = 0; i < num; i++) now = now.pre;
         }
         case 'D' -> { // 아래로 이동
            int num = Integer.parseInt(s.substring(2));
            for (int i = 0; i < num; i++) now = now.next;
         }
         case 'C' -> { // 삭제
            now.isDelete = true;
            stack.push(now);

            Node pre = now.pre;
            Node next = now.next;

            if (pre != null) pre.next = next;
            if (next != null) {
               next.pre = pre;
               now = next;
            } else now = pre;
         }
         case 'Z' -> { // 복구
            Node delete = stack.pop();
            Node pre = delete.pre;
            Node next = delete.next;
            delete.isDelete = false;

            if (pre != null) pre.next = delete;
            if (next != null) next.pre = delete;
         }
      }
   }

   StringBuilder ans = new StringBuilder();
   for (int i = 0; i < n; i++) {
      if (node[i].isDelete) ans.append("X");
      else ans.append("O");
   }
   return ans.toString();
}

static class Node {
   Node pre = null;
   Node next = null;
   boolean isDelete;
}

---

잊지말아야 할, 이 문제를 풀며 한 실수들..ㅎ(제한 사항 제대로 읽자...)

1️⃣ X에 들어가는 숫자는 두 자리 이상일 수 있음.

• 처음에 Character.getNumericValue()를 사용하였는데, 계속 틀렸음.
• 문제를 다시 읽어보니 X는 1이상 300,000 이하의 수였음.
• 그리하여 문자열을 잘라서 정수형으로 변환하였음.

2️⃣ 마지막 행이면 해당 행의 위의 값이 되고, 0보다 아래로 갈 수 없음.

• 주어진 두 번째 예시를 수행하다보면, 마지막 행을 삭제하였다가 다시 추가하게 됨.
• 여기서 마지막 행을 지우고 k값을 안바꿔주면, 입력되는 인덱스 값이 달라지게 됨.
• 때문에 답이 달라졌음.
• 그리고 0보다 작아지는 경우 0 값을 다시 넣어주었다.
• 이 코드를 쓰지 않고 문제를 채점했더니 효율성 2번에서 실패가 되었다.
• 계속해서 업하다보면 k의 값이 마이너스가 될 수 있지 않을까 해서 해당 코드를 넣어주었더니 해결됨.

 

 

 결론은... 제한 사항을 잘 읽자...