백준/ Gold 5 문제 , 백준 Node.js 자바스크립트 5430 , AC [자료구조, 스택]

백준/ Gold 5 문제 , 백준 Node.js 자바스크립트 5430 , AC [자료구조, 스택]

 

 

✔️Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감 🧑‍💻
1. 최상
2. 상
3. 중
4. 하


이해도 🙆‍♂️
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


덧붙일 말 🏷️
배열 앞 원소를 빼는 과정은 매우 비효율적인 코드이라는 것을 깨달았다.
질문 게시판을 통해서 해당 문제가 특정 언어에서만 잘못 통과되고 있다는 것을 알았음. 
추후 이 문제 다른 풀이들의 통과 여부가 달라질 수도 있음.

 

 

문제 출처 🏠

 

https://www.acmicpc.net/problem/5430

5430번: AC

 

 

 

 

요구사항 📋

R : 배열에 있는 수의 순서를 뒤집음.
D : 배열의 첫 번째 수를 버림.
- 빈 배열에 D를 사용하면 'error' 출력.
- 주어진 함수를 실행하고 남은 배열이나 error 출력

 

 

 

해결 전략 📝

일단 이 문제는 메모리 초과때문에 파이썬으로 해결 했다.

 

이전에 자바스크립트로 풀었다는 코드들을 봤는데 내 로직이랑 별 차이가 없었다. 

 

질문 게시판에도 자바스크립트로 안된다는 글도 올라온거 보면 최근에 업데이트로 메모리 관련해서 통과 불가 한건가 싶다.

 

(확실치 않으니 아시는 분은 댓글 부탁드립니다.)

 

다른 사람들 코드를 내가 직접 제출해볼수는 없으니, 내가 푼 코드 대로 파이썬으로 돌려서 제출해봤다.

 

결과는 바로 통과. 로직 자체는 맞으니 설명 하겠다.

 

https://www.acmicpc.net/board/view/102355

글 읽기 - Node.js 는 통과 불가능한가요?

 

혹시 몰라 질문게시판에도 질문을 남겨두었다. 추후 확인해보겠다.

 

 

+) 바로 답변이 왔다.

 

본의 아니게 (?) 내가 올린 코드로 문제 출제자님도 생각하지 못한 로직이 파이썬이라는 특정 언어에서만 통과가 되어버리는 경우를 알게 되었다고 하셔서 데이터 추가 요청을 한 상태이다.

 

https://www.acmicpc.net/board/view/102359

 

애초에 앞의 원소를 지우는 행위는 그 뒤 원소들을 앞으로 땡기는 비효율적인 과정이라 메모리 초과가 발생하고 있던 것이다.

 

파이썬은 이걸 못잡아주고 있던 상황... 아마 조만간 해당 로직대로도 파이썬 또한 통과가 안될까 싶다.

 

풀이는 다시 수정한 내용으로 올렸다.

 

맨 앞자리를 지우지 않고, 인덱스 위치만 확인해가다가 마지막에 인덱스 위치에 맞춰서 자르는 식으로 코드를 제출하였더니 Node.js 로도 문제없이 통과하였다.

 

 

이렇게 또 배워갑니다.

 

---

 

 

처음에는 스택을 사용했는데 굳이굳이 사용할 필요가 없었다.

 

우선, 이 문제의 함정은 R이 나오더라도 진짜 돌릴 필요가 없다.

 

우리가 확인해야 할 것은 D가 나왔을때, 배열이 돌아간 상태인지 아닌지 체크만해주고 해당하는 방향에서 빼주기만 하면 된다.

 

예를들어 R이 한 번 나온다음에 D 가 나오면 그냥 배열 앞에서 빼주면 된다. 

 

왜냐하면, 뒤집어서 뒤에서 하나 빼든, 그냥 앞에서 빼고 최종적으로 배열을 돌려서 출력하면 되기 때문에,

 

문제를 해결하면서 계속적으로 돌릴 필요가 전혀 없는 것이다.

 

만약, 10만 개의 R 이 주어지고 배열이 10만 크기라면 조금만 생각해봐도 왜 하면 안되는지 알것이다.

 

아마도, 이걸 캐치하는 것이 이 문제의 포인트 같다.

 

 

 

그럼 이걸 어떻게 확인하느냐?

 

불린 값을 사용하면 된다.

 

R 이 나온 횟수가 홀수라면 불린 값을 true 로 설정해 마지막에 이 값이 true 라면 돌려서 출력하면 되고

 

짝수라면 불린 값을 false 로 설정해 돌릴 필요없이 출력시키면된다.

 

다시 말해 짝수 갯수로 나온다면, 연산 처음부터 끝까지 reverse 를 사용하지 않고도 문제를 해결할 수 있다.

 

+) 

맨 앞 원소를 하나씩 빼면 뒤의 원소들을 앞으로 땡겨야 하기 때문에 비효율적인 코드가 되어버린다.

 

뒷자리는 pop()으로 빼버리고 맨앞자리를 빼야할때는 인덱스 번호만 +1 해가면서 체크만 해주자.

 

이후, 마지막에 인덱스 번호부터 시작해서 잘라 출력시키면 된다.

 

 

 

여기서, 추가적으로 조심해야하는게

 

정답 출력 때 공백없이 출력 시켜줘야 한다. 또한 배열 형태로 출력해야 하므로 주의하자.

 

---

 

 

 

이 로직대로 파이썬 풀이를 진행하면 잘 풀린다.

 

다음은 파이썬 풀이다. 

 

https://bmy1320.tistory.com/entry/%EB%B0%B1%EC%A4%80-Gold-5-%EB%AC%B8%EC%A0%9C-%EB%B0%B1%EC%A4%80-%ED%8C%8C%EC%9D%B4%EC%8D%AC-5430-AC

백준/ Gold 5 문제 , 백준 파이썬 5430 , AC

 

 

 

정답 💯

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map((v) => v.trim());

for (let i = 1; i <= Number(input[0]); i++) {
  let [S, N, Nums] = [
    input[i * 3 - 2],
    Number(input[i * 3 - 1]),
    input[i * 3].slice(1, input[i * 3].length - 1).split(","),
  ];
  let [RUR, check, startIdx, delCnt] = [false, true, 0, 0];
  if (N === 0) Nums = [];
  S.split("").map((v) => {
    if (v === "R") {
      RUR = !RUR;
    } else if (v === "D") {
      if (startIdx + delCnt >= Nums.length) check = false;
      if (RUR) {
        Nums.pop();
        delCnt += 1;
      } else startIdx += 1;
    }
  });
  Nums = Nums.slice(startIdx, Nums.length);
  if (RUR) Nums.reverse();
  console.log(check === true ? "[" + Nums.join(",") + "]" : "error");
}