[99클럽] 코딩테스트 스터디, 12일차 TIL - 비기너 (백준, 2161)

 

1. 문제풀이

1) 문제

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다.

우선, 제일 위에 있는 카드를 바닥에 버린다. 그다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

 

예를 들어 N=4인 경우를 생각해 보자.

카드는 제일 위에서부터 1234 의 순서로 놓여있다.

1을 버리면 234가 남는다.

여기서 2를 제일 아래로 옮기면 342가 된다.

3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다.

마지막으로 2를 버리고 나면, 버린 카드들은 순서대로 1 3 2가 되고, 남는 카드는 4가 된다.

 

N이 주어졌을 때, 버린 카드들을 순서대로 출력하고, 마지막에 남게 되는 카드를 출력하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 정수 N(1 ≤ N ≤ 1,000)이 주어진다.

 

출력

첫째 줄에 버리는 카드들을 순서대로 출력한다. 제일 마지막에는 남게 되는 카드의 번호를 출력한다.

2) 해석

- 버린 카드를 순서대로 + 마지막에 남게 되는 카드 출력

- 카드가 한장 남을 때까지 반복

- 제일 위에 있는 카드를 바닥에 버림

- 제일 위에 있는 카드를 제일 밑으로 옮김

 

확실히 문제를 어떻게 구현할지 해석하고 시작하니까 구현할 때 덜 헷갈리는 느낌이다.

 

 

3) 풀이

const fs = require("fs");
const input = fs.readFileSync("./index.txt").toString().trim();

const N = Number(input);
const answer = [];
const arr = Array.from({ length: N }, (_, i) => i + 1);

const handleShuffle = (arr) => {
  if (arr.length === 1) {
    answer.push(arr[0]);
    return;
  }

  answer.push(arr[0]);

  //값을 바꿔서 다시 호출
  const nextArr = arr.slice(2);
  nextArr.push(arr[1]);
  handleShuffle(nextArr);
};

handleShuffle(arr);

console.log(answer.join(" "));

 

코딩테스트 연습을 할 때 재귀로 푸는 게 익숙해져서 그런지 자꾸 재귀를 생각하게 된다.

이 문제도 반복해서 호출하라길래 재귀로 접근했다.

 

 

const N = Number(input);
const answer = [];
const arr = Array.from({ length: N }, (_, i) => i + 1);

 

우선 input에서 받아온 값을 숫자로 바꿔주었다.

vscode에선 형변환을 하지 않아도 에러가 나지 않는데, 백준에서는 종종 에러가 나더라ㅠ

그래서 Number을 이용해서 받아온 값을 수정해 줬다.

 

그 후, 버릴 카드를 담아둘 answer 배열을 만들어줬다.

그리고 1부터 7까지의 숫자를 담은 arr 배열도 만들었다.

 

 

const handleShuffle = (arr) => {
  if (arr.length === 1) {
    answer.push(arr[0]);
    return;
  }

  answer.push(arr[0]);

  //값을 바꿔서 다시 호출
  const nextArr = arr.slice(2);
  nextArr.push(arr[1]);
  handleShuffle(nextArr);
};

 

이제 handleShuffle이란 함수를 만들어서 arr를 계속 받아오도록 구현했다.

 

해당 배열의 길이가 1이라면, return 하도록 만들고,

그렇지 않으면 첫 번째 값을 삭제 한 뒤, 그 뒤에 있는 값을 맨 뒤로 넣어서 다시 handleShuffle 함수를 호출하도록 만들었다.

 

 

 

- 걸린 시간

 

2. 리팩토링

const fs = require("fs");
const input = fs.readFileSync("./index.txt").toString().trim();

const N = Number(input);
const answer = [];
const arr = Array.from({ length: N }, (_, i) => i + 1);

while (arr.length > 0) {
  answer.push(arr.shift());
  if (arr.length) arr.push(arr.shift());
}

console.log(answer.join(" "));

 

처음에는 겹치는 부분만 없애다가 아예 다른 방식으로 접근할 수 있지 않을까 하고 생각해 봤다.

바뀐 점은 크게 두 가지다.

 

1. 재귀 대신 while문 사용

 

재귀 대신 while문을 사용하니 더 깔끔하게 작성할 수 있었다.

쓸데없이 함수를 따로 만들지 않아도 된다!

 

 

2. 새로운 배열 생성 대신 배열 직접 접근 

 

다음으로 수정한 것은 배열 수정 방식이었다.

기존에는 slice를 사용해서 배열을 복사한 뒤 넘겼었는데, 이를 직접 수정하도록 바꿨다.

 

react 쓰는 것에 익숙해져서 나도 모르게 배열을 복사해서 사용했던 것 같다ㅠ

복사하게 되면, 다음 반복으로 넘어갈 때마다 메모리가 늘어나게 되니 직접 접근해서 수정하는 것이 좋다.

 

위 방식대로 리팩터링 하자 공간복잡도가 반이나 줄었다!

시간복잡도는 O(N^2)으로 비슷했지만, 백준에서 보니 시간도 더 적게 들었다. 

 

무엇보다 코드가 정말 깔끔해진 게 마음에 든다ㅎ

다음부턴 재귀 말고 while문을 활용하는 방식을 먼저 생각하도록 해봐야겠다ㅠ

 

처음

 

 

리팩토링 후

 

 

3. 기타

1) 백준, 런타임 에러

문제를 풀고 제출하려는데 런타임 에러가 발생했다.

이미 vscode에서 제대로 출력되는 걸 검증하고 한 것이라 어디서 에러가 발생하는지 찾을 수가 없었다.

 

구글에 검색해 보니 입력값을 불러오는 것에서 발생하는 에러였다ㅠ

Node.js에서 fs 모듈을 사용하다 보면 가끔 런타임 에러가 발생할 때가 있다.

이때는 경로를 수정해서 출력해 주면 된다.

 

//기존
const fs = require("fs");
const input = fs.readFileSync("/div/stdin").toString().trim();

 

기존에는 이렇게 경로를 "/div/stdin"으로 불러왔을 것이다.

 

//수정
const fs = require("fs");
const input = fs.readFileSync(0, 'utf-8').toString().trim();

 

그 경로를 이런 식으로 바꿔주면 된다. 

그럼 런타임에러(EACCES)가 발생하지 않게 된다!

 

앞으로도 이 경로로 작성해야겠다,,