문제

문제이해하기

• 인형을 다 뽑으면 더이상 뽑을 수 없다.
• 바구니맨 위의 인형과 뽑은 인형이 같으면 answer는 2를 더한다.

문제풀기전략

b의 요소들(y)을 loop로 받아온다.
y를 a의 인덱스로 적용하기위해 x = y-1로 정한다.
 c[x]가 0이상이면 a[c[x]][x]또한 0이상이므로 이 수(a[c[x]][x])를 stack에 넣어준다.
   만약 stack의 마지막이 num과 같다면 answer에 2를 더해주고 stack의 마지막은 제거한다.
     c[x]는 +1해준다. 만약 c[x]가 5가되면 -1로 바꿔준다.
c[x]가 0이면 loop를 통해 a[i][x]가 0이 아닌 부분을 찾는다.
   만약 a[i][x]가 0이 아니라면 a[i][x]를 stack에 넣어준다.
     c[x] = i+1로 설정하며 c[x] = 5일 경우에는 -1로 바꿔준다.
c[x]가 -1로 되어버리면 상위 두개의 조건식에 부합되지않아 제외된다.

CODE

//input
let a = [
  [0, 0, 0, 0, 0],
  [0, 0, 1, 0, 3],
  [0, 2, 5, 0, 1],
  [4, 2, 4, 4, 2],
  [3, 5, 1, 3, 1],
];
let b = [1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5];
//--------------------------------------------------
let c = [0, 0, 0, 0, 0];
let answer = 0;
let stack = [];
for (let y of b) {
  let x = y - 1;  
  if (c[x] > 0) {
    if (stack.length > 0 && stack[stack.length - 1] === a[c[x]][x]) {
      stack.pop();
      answer += 2;
      c[x]++;
      if (c[x] === 5) c[x] = -1;
    } else {
      stack.push(a[c[x]][x]);
      c[x] += 1;
      if (c[x] === 5) c[x] = -1;
    }    
  } else if (c[x] === 0) {
    for (let i = 0; i < 5; i++) {
      if (a[i][x] !== 0) {
        if (stack.length > 0 && stack[stack.length - 1] === a[i][x]) {
          stack.pop();
          answer += 2;
          c[x] = i + 1;
          if (c[x] === 5) c[x] = -1;
        } else {
          stack.push(a[i][x]);
          c[x] = i + 1;
          if (c[x] === 5) c[x] = -1;
        }        
        break;
      }
    }
  }  
}
console.log(answer);

Refactoring

c[x]++;
if (c[x] === 5) c[x] = -1;

c[x] = i + 1;
if (c[x] === 5) c[x] = -1;
위 두 부분의 중복을 제거해준다.

//input
let a = [
  [0, 0, 0, 0, 0],
  [0, 0, 1, 0, 3],
  [0, 2, 5, 0, 1],
  [4, 2, 4, 4, 2],
  [3, 5, 1, 3, 1],
];
let b = [1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5];

let c = [0, 0, 0, 0, 0];
let answer = 0;
let stack = [];
for (let y of b) {
  let x = y - 1;  
  if (c[x] > 0) {
    if (stack.length > 0 && stack[stack.length - 1] === a[c[x]][x]) {
      stack.pop();
      answer += 2;      
    } else stack.push(a[c[x]][x]);
    c[x]++;
    if (c[x] === 5) c[x] = -1;
  } else if (c[x] === 0) {
    for (let i = 0; i < 5; i++) {
      if (a[i][x] !== 0) {
        if (stack.length > 0 && stack[stack.length - 1] === a[i][x]) {
          stack.pop();
          answer += 2;          
        } else stack.push(a[i][x]);                        
        c[x] = i + 1;
        if (c[x] === 5) c[x] = -1;        
        break;
      }
    }
  }  
}
console.log(answer);

Refactoring

기존코드 문제점

• 배열 c를 만들어 a에서 0이 아닌 위치를 파악하는건 좋지만 시간복잡도 측면에서는 많은 효과를 내지 못함.
  -> 어차피 O(n^2)이므로
  

개선

• c를 만들어 위치파악을 하지 않고 a에서 0이 아닌곳을 찾는다.

//loop로 moves의 요소(mov)들을 받아온다.
// loop로 board[i][mov-1]에서 i를 돌려보며 0이 아닐때를 찾는다.
// board[i][mov-1]를 stack에 넣어주고 0으로 바꿔준다.
//  만약 stack의 마지막 요소가 board[i][mov-1]와 같다면 stack의 마지막요소를 제거해주고 answer+=2를 해준다.

CODE

//input
let board = [
  [0, 0, 0, 0, 0],
  [0, 0, 1, 0, 3],
  [0, 2, 5, 0, 1],
  [4, 2, 4, 4, 2],
  [3, 5, 1, 3, 1],
];
let moves = [1, 5, 3, 5, 1, 2, 1, 4];

let answer = 0;
let stack = [];
for (let mov of moves) {
  for (let i = 0; i < board.length; i++) {
    if (board[i][mov - 1] !== 0) {
      if (stack[stack.length - 1] === board[i][mov - 1]) {
        answer += 2;
        stack.pop();
      } else {
        stack.push(board[i][mov - 1]);
      }
      board[i][mov - 1] = 0;
      break;
    }
  }
}
console.log(answer);

이 코드 또한 O(n^2)이므로 결국 시간복잡도 측면에서는 이전의 코드와 같다.
그러나 가독성이 훨씬 좋다.