[2021 카카오 채용연계형 인턴십][구현] 표 편집 - Java

문제 바로가기

코딩테스트 연습 - 표 편집

 

휴 한시간 넘게 걸렸다...^^;;;

 

효율성이 걸린 문제길래 특별한 알고리즘을 요구하는줄 알았는데 그런건 아니었습니다.

 

근데 첨 푼 방법으로는 효율성 하나도 못맞춤

 

class Solution {

//  static class Info {
//    int row;
//    int name;
//
//    public Info(int row, int name) {
//      this.row = row;
//      this.name = name;
//    }
//  }

  public String solution(int n, int k, String[] cmd) {
    StringBuilder sb = new StringBuilder();
//    List<Integer> table = new ArrayList<>();
//    Stack<Info> deleteStack = new Stack<>();
    Stack<Integer> stack = new Stack<>();     // 행 번호 저장
    int tableSize = n;

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

      if (op == 'C') {
//        deleteStack.push(new Info(k, table.get(k)));
        stack.push(k);
        tableSize--;
        if (k == tableSize) {
          k--;
        }
      } else if (op == 'Z') {
//        Info undo = deleteStack.pop();
        int undoRow = stack.pop();
//        table.add(undo.row, undo.name);
        if (k >= undoRow) {
          k++;
        }
        tableSize++;
      } else if (op == 'D') {
        k = (k + Integer.parseInt(s.split(" ")[1])) % tableSize;
      } else {
        k = (k - Integer.parseInt(s.split(" ")[1])) % tableSize;
      }
    }

    for(int i = 0; i < tableSize; i++) {
      sb.append("O");
    }

    while(!stack.isEmpty()) {
      sb.insert(stack.pop(), "X");
    }

    return sb.toString();
  }

 

맨처음에는 List 로 테이블도 표현하고, 삭제하는 행도 {행 번호, 이름} 으로 표현해서 저장했었습니다. 이렇게 하니깐 정확도는 맞는데 효율성에서 자꾸 걸리더라구요. 아무래도 C가 나올 때마다 인스턴스도 새로 생성하고.. List 에도 계속 넣고.. 또 그렇게 했기 때문에 마지막 answer를 만들때 스택을 갖고 삭제된 행의 집합(Set)을 만들고 0~n 까지 돌면서 이 Set 에 해당 이름이 있는지 여부로 정답을 만들어줘서 여기서도 시간을 많이 잡아먹지 않았나 싶습니다.

 

그래서 어쩌지 하다가 결국 이름은 고려하지 않아도 된다는걸 깨닫고 커서의 위치와 계속 변동하는 테이블의 크기 변수만 갖고 문제를 풀었습니다.

 

한시간 넘게 걸렸다 호호

감사합니다~!