[PCCP] Lv3: 표 편집(81303) 해설

문제

- 문제 링크: 표 편집

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1)

solution 1

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

- N: 표의 행 길이

- 벡터를 초기화할 때 시간 복잡도는 O(N)

- 제약사항을 보면 명령어 뒤의 X의 모든 합이 100만을 넘지 않으므로 명령어 처리시 시간복잡도는 O(1,000,000)_

- 최종 시간 복잡도: O(N)

#include <stack>
#include <string>
#include <vector>

using namespace std;

string solution(int n, int k, vector<string> cmd) {
    // 삭제된 행의 인덱스 저장
    stack<int> deleted;
    // 각 행의 위아래 행의 인덱스 저장
    vector<int> up;
    vector<int> down;
    
    for (int i = 0; i < n + 2; ++i) {
        up.push_back(i - 1);
        down.push_back(i + 1);
    }
    // 임시 공간을 고려한 현재 위치
    k++;
    
    // 주어진 명령을 순회
    for (int i = 0; i < cmd.size(); ++i) {
      // 현재 위치를 삭제하고 그 다음 위치로 이동
      if (cmd[i][0] == 'C') {
          deleted.push(k);
          down[up[k]] = down[k];
          up[down[k]] = up[k];
          
          if (down[k] == n + 1)
              k = up[k];
          else
              k = down[k];
      }
      // 가장 최근에 삭제한 행을 복원
      else if (cmd[i][0] == 'Z') {
          int r = deleted.top();
          down[up[r]] = r;
          up[down[r]] = r;
          deleted.pop();
      }
      // 현재 행을 주어진 값만큼 위로, 아래로 이동
      else {
          int sz = stoi(cmd[i].substr(2));
          
          if (cmd[i][0] == 'U') {
              for (int j = 0; j < sz; ++j) {
                  k = up[k];
              }
          }
          else if (cmd[i][0] == 'D') {
              for (int j = 0; j < sz; ++j) {
                  k = down[k];
              }
          }
      }
    }
    
    string answer;
    // 삭제된 행의 위치에 'X', 그렇지 않은 행의 위치에 'O'으로 표시한 문자열 반환
    answer.append(n, 'O');
    while (!deleted.empty()) {
        answer[deleted.top() - 1] = 'X';
        deleted.pop();
    }
    
    return answer;
}

solution 2)

#include<>

solution 3)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1)

- N: 표의 행 길이

- 초기에 리스트를 초기화할 때 시간 복잡도: O(N)

- 제약사항을 보면 명령어 뒤의 X의 모든 합이 100만을 넘지 않는다고 했으므로 명렁어를 처리할 때 시간 복잡도는 O(1,000,000)

- 최종 시간 복잡도: O(N)

import java.util.Arrays;
import java.util.Stack;

class Solution {
    public String solution(int n, int k, String[] cmd) {
        // 삭제된 행의 인덱스를 저장하는 스택
        Stack<Integer> deleted = new Stack<>();
        // 각 행을 기준으로 연산에 따른 위치를 표시하기 위한 배열
        int[] up = new int[n + 2];
        int[] down = new int[n + 2];
        
        for (int i = 0; i < n + 2; ++i) {
            up[i] = i - 1;
            down[i] = i + 1;
        }
        
        // 현재 위치를 나타내는 인덱스
        k++;
        
        // 주어진 명령어(cmd) 배열을 하나씩 처리
        for (String c : cmd) {
            // 현재 위치를 삭제하고 그 다음 위치로 이동
            if (c.startsWith("C")) {
                deleted.push(k);
                up[down[k]] = up[k];
                down[up[k]] = down[k];
                k = n < down[k] ? up[k] : down[k];
            }
            // 가장 최근에 삭제된 행을 복원
            else if (c.startsWith("Z")) {
                int restore = deleted.pop();
                down[up[restore]] = restore;
                up[down[restore]] = restore;
            }
            // U 또는 D를 사용해 현재 위치를 위, 아래로 이동
            else {
                String[] s = c.split(" ");
                int x = Integer.parseInt(s[1]);
                
                for (int i = 0; i < x; ++i) {
                    k = s[0].equals("U") ? up[k] : down[k];
                }
            }
        }
        
        
        
        // 삭제된 행의 위치에 'X'를, 그렇지 않은 행의 위치에는 'O'를 저장한 문자열 반환
        char[] answer = new char[n];
        Arrays.fill(answer, 'O');
        
        for (int i : deleted) {
            answer[i - 1] = 'X';
        }
        
        return new String(answer);
    }
}

solution 2)

#include<>

solution 3)

#include<>

 

(Python)

solution 1)

- N: 표의 행 길이

- 초기에 리스트 초기화: O(N^2)

- 명령어 뒤의 X의 모든 합이 100만을 넘지 않으므로 명령어 처리 시간복잡도: O(10^6)

- 최종시간복잡도: O(N)

def solution(n, k, cmd):
    # 삭제된 행의 인덱스를 저장하는 리스트
    deleted = []
    
    # 링크드리스트에서 각 행 위아래의 행의 인덱스를 저장하는 리스트
    up = [i - 1 for i in range(n + 2)]
    down = [i + 1 for i in range(n + 1)]
    
    # 현재 위치를 나타내는 인덱스
    k += 1
    
    # 주어진 명령어(cmd) 리스트를 하나씩 처리
    for cmd_i in cmd:
        # 현재 위치를 삭제하고 그 다음 위치로 이동
        if cmd_i.startswith("C"):
            deleted.append(k)
            up[down[k]] = up[k]
            down[up[k]] = down[k]
            k = up[k] if n < down[k] else down[k]
            
        # 가장 최근에 삭제된 행을 복원
        elif cmd_i.startswith("Z"):
            restore = deleted.pop()
            down[up[restore]] = restore
            up[down[restore]] = restore
            
        # U 또는 D를 사용해 현재 위치를 위아래로 이동
        else:
            action, num = cmd_i.split()
            if action == "U":
                for _ in range(int(num)):
                    k = up[k]
            else:
                for _ in range(int(num)):
                    k = down[k]
                    
    # 삭제된 행의 위치에 'X'를, 그렇지 않은 행의 위치에 'O'를 포함하는 문자열 반환
    answer = ["O"] * n
    
    for i in deleted:
        answer[i - 1] = "X"
        
    return "".join(answer)

solution 2)

import

solution 3)

import

 

(JavaScript)

solution 1)

- N: 표의 행 길이

- 초기에 배열 초기화: O(N^2)

- 명령어 뒤의 X의 모든 합이 100만을 넘지 않으므로 명령어 처리 시간복잡도: O(10^6)

- 최종시간복잡도: O(N)

function solution(n, k, cmd) {
    // 삭제된 행의 인덱스를 저장하는 배열
    const deleted = [];
    
    // 연결리스트에서 각 행 위아래의 행의 인덱스를 저장하는 배열
    const up = [...new Array(n + 2)].map((_, i) => i - 1);
    const down = [...new Array(n + 1)].map((_, i) => i + 1);
    
    // 현재 위치를 나타내는 인덱스
    k += 1;
    
    // 주어진 명령어(cmd) 배열 요소를 하나씩 처리
    for (const item of cmd) {
        // 현재 위치를 삭제하고 그다음 위치로 이동
        if (item[0] === "C") {
            deleted.push(k);
            up[down[k]] = up[k];
            down[up[k]] = down[k];
            k = n < down[k] ? up[k] : down[k];
        }
        
        // 가장 최근에 삭제된 행을 복원
        else if (item[0] === "Z") {
            const restore = deleted.pop();
            down[up[restore]] = restore;
            up[down[restore]] = restore;
        }
        
        // U 또는 D를 사용해 현재 위치를 위아래로 이동
        else {
            const [action, num] = item.split(" ");
            if (action === "U") {
                for (let i = 0; i < num; ++i) {
                    k = up[k];
                }
            } else {
                for (let i = 0; i < num; ++i) {
                    k = down[k];
                }
            }
        }        
    }
    
    // 삭제된 행의 위치에 'X'를 그렇지 않은 행의 위치에 'O'를 포함하는 문자열 반환
    const answer = new Array(n).fill("O");
    for (const i of deleted) {
        answer[i - 1] = "X";
    }
    return answer.join("");
}

solution 2)

import

solution 3)

import