[C3] 5430 - AC

문제

세상에 할 일이 없어서 새로운 언어를 만드는 사람이 어딨나,,,,,,,

 

풀이

사실, 처음 봤을 때는 R은 뒤집기, D는 삭제라 하니...

당연히 reverse()와 shift()를 쓰면 되는거 아닌가? 라고 생각했지만

그렇게 당연하게 풀리는 문제가 골드5일리가 없다..!!!!

의심하고 또 의심하며 처음부터 다른 풀이 방법을 사용해 보기로 했다.

 

우선, 테스트케이스가 최대 100개, 주어지는 함수의 개수가 최대 10만개, 배열의 요소가 최대 10만개이다.

reverse()의 시간 복잡도는 O(n)이므로, 최악의 경우 복잡도는 O(n^2).

그러므로 최대한 메서드를 쓰지 않고, 1차원 for문 안에서 해결하는 것을 목표로 했다.

 

내가 생각했던 방법은 투포인터?와 비슷한 방법으로, 시작 인덱스와 끝 인덱스를 정해놓고

D 연산이 일어날 때 마다 둘중 하나를 변경하는 방법이었다.

배열이 정방향일 경우 시작 인덱스가 1 증가할 것이고, 역방향일 경우 끝 인덱스가 1 줄어들 것이다.

 

배열이 뒤집혀 있는지, 정방향인지는 boolean을 이용해 설정해 주면 된다.

만약 R 명령어가 나온다면 현재 배열의 상태의 반대 상태로 만들어주면 끝.

 

//command는 각 tc의 첫 값으로 들어오는 R, D로 이루어진 문자열을 의미한다
let isReverse = false;
for (let c of command) {
  if (c === "R") isReverse = !isReverse;
}

 

초기 상태에서 배열은 뒤집어져 있지 않기 때문에, false로 설정해 주는 것이 편하다.

그 다음은 시작 인덱스와 끝 인덱스를 어떻게 설정할 것인가를 알아보자.

 

 

어차피 slice를 해줄 것이기 때문에, end는 일부러 실제 인덱스보다 1 추가한 값으로 설정했다.

정상적인 배열의 상태일 때 D 명령어가 나온다면 배열의 맨 앞 값 = 0번 인덱스를 제거하는 것이기 때문에, start는 다음 인덱스인 1이 된다.

반대로, R 명령어가 나와 배열이 뒤집힌다면 현재 배열 맨 앞의 값이 초기 배열의 맨 끝값이 될 것이다.

이 상태에서 D 명령어가 나와 배열 맨 처음 값을 제거한다면, 초기 배열의 맨 끝값을 제거하는 것과 같다는 것이다.

그러므로 맨 끝값의 인덱스 4에서 하나 앞에 있는 인덱스인 3이 된다.

한마디로, 배열이 뒤집히지 않은 상태에서는 D 명령어가 나올시 start + 1

배열이 뒤집힌 상태에서는 D 명령어가 나올시 end - 1을 해주면 된다.

 

//num은 tc의 두번째 줄 입력으로 들어오는 배열 요소의 개수를 의미한다
let isReverse = false;
let start = 0;
let end = num;
for (let c of command) {
  if (c === "R") isReverse = !isReverse;
  if (c === "D") {
    if (isReverse) {
      end -= 1;
    } else {
      start += 1;
    }
  }
}

 

이제 마지막. 현재 배열의 상태를 결정해야 한다.

맨 처음에 isReverse를 통해 현재 배열의 뒤집힘 여부를 알 수 있었다.

그러므로 원본 배열에서 먼저 start, end를 이용해 slice를 실행하고, 그 이후 isReverse의 상태에 따라 자른 배열을 뒤집거나, 그대로 두면 된다.

 

let newArr = arr.slice(start, end);
if (isReverse) newArr = newArr.reverse();

 

여기서 잠깐!

만약 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다. 처럼 에러가 발생하는 경우는 어떻게 처리해 주느냐?

 

시작 후 첫번째 D를 실행 했을 때, end는 초기 배열의 길이인 1이고 start는 맨 앞의 요소를 제거했으므로 1이 된다.

이후 두번째 D를 실행하면 end는 변하지 않지만 start는 또 1이 늘어난다.

하지만 이 경우는, '빈 배열인 상태에서 D를 실행'했으므로 에러가 발생한다.

즉, start와 end가 같을 경우 = 배열이 빈 상태이므로, start가 end보다 커지면 에러가 발생하게 된다.

 

if (start > end) {
  ans.push("error");
} else {
  let newArr = arr.slice(start, end);
  if (isReverse) newArr = newArr.reverse();

  ans.push(`[${newArr.join(",")}]`);
}

 

코드

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];

rl.on("line", (line) => {
  input.push(line);
}).on("close", () => {
  const n = Number(input.shift());

  const ans = [];
  for (let i = 0; i < n * 3; i += 3) {
    let [command, num, arr] = input.slice(i, i + 3);
    arr = arr.split(/[\[\],]+/).filter(Boolean);
    num = Number(num);

    let isReverse = false;
    let start = 0;
    let end = num;
    for (let c of command) {
      if (c === "R") isReverse = !isReverse;
      if (c === "D") {
        if (isReverse) {
          end -= 1;
        } else {
          start += 1;
        }
      }
    }
    if (start > end) {
      ans.push("error");
    } else {
      let newArr = arr.slice(start, end);
      if (isReverse) newArr = newArr.reverse();

      ans.push(`[${newArr.join(",")}]`);
    }
  }
  console.log(ans.join("\n"));
  process.exit(0);
});