220904 TIL Stack을 활용해보자

원래는 금요일에 풀었어야 했던 금요 코딩 테스트 문제인 프로그래머스 크레인 인형 뽑기 문제를 오늘 해결했다.

 

금요일에 풀지 못했던 이유는 오늘 풀었던 방법인 push와 pop을 몰라서 다른 방법으로 풀다가 시간이 오버돼서 못 풀었다.

분명 push와 pop을 안 써도 풀 수는 있겠지만 금요일의 나는 그걸 하지 못했고...

금요일에 삽질을 너무 많이 해서 풀기 싫어서 계속 미루다가 오늘은 어떻게든 풀어낸다는 마음으로 시작했다.

 

금요일에 풀었던 방법에 문제가 있다고 생각해서 이전에 풀었던 방법들은 다 지우고 처음부터 했다.

여러 가지 방법을 모색하던 중 Stack이라는 새로운 개념을 접했고 stack을 적용해서 풀 수 있었다.

 

 

Stack

우선 Stack이란 마지막에 저장한 데이터를 가장 먼저 가져오는 LIFO(Last In First Out) 구조로 되어 있다.

이 stack에는 push와 pop이라는 메서드를 이용해서 데이터를 저장(push)하고 가져올 수(pop) 있다.

 

예를 들어서 어떤 리스트에 0, 1, 2 순서대로 저장(push)했다면 가져올 때는 2, 1, 0 순서대로 가져오게(pop) 된다.

 

말보다는 이미지가 더 이해하기 쉬운 것 같아서 이미지를 가져왔다.

https://devuna.tistory.com/22

 

 

그럼 크레인 인형뽑기 문제에 stack이라는 개념을 어떻게 활용을 했는지 알아보자.

 

크레인 인형 뽑기 문제의 요구사항

크레인을 좌우로 움직여서 멈춘 위치의 가장 위에 있는 인형이 무조건 뽑히고, (만약 해당 라인에 인형이 하나도 없으면 아무것도 뽑지 않는다) 뽑은 인형은 바구니에 쌓게 되는 데, 이때 바구니의 가장 아래 칸부터 인형이 순서대로 쌓인다.

그리고 바구니에 같은 인형이 연속으로 2개 있으면 터져서 사라진다.

뽑기 판 board이 주어지고 뽑는 라인의 순서인 moves이 주어질 때, 터져서 사라진 인형의 개수를 구해야 한다.

 

문제 풀이

여기서 맨 처음에 뽑은 인형이 바구니의 맨 밑에 가야 하니까 push 메서드로 저장할 수 있다.

이후에 push로 저장되는 인형들은 문제 요구사항에 맞게 바구니에 순서대로 차곡차곡 쌓인다.

if (board[j][moves[i] - 1] != 0) {
    dolls.push(board[j][moves[i] - 1]); // dolls = 인형 담을 바구니
    board[j][moves[i] - 1] = 0;
    break;
}

우선 인형이 숫자로 구분되다 보니까 0일 때는 없는 걸로 판단이 되어 0이 크레인이 뽑으려는 자리가 0이 아닐 때만 뽑게 조건문을 먼저 걸고, 0이 아니면 바구니에 인형을 push로 담았다.

그 이후 뽑은 인형은 없어져야 하니까 그 자리의 배열 숫자를 0으로 만들어 줬다.

 

이렇게 순서대로 push를 해주다가 

바구니에 같은 인형이 연속으로 있을 때 사라지게 하기 위해 pop을 사용했다.

if (dolls.size() > 0) {
  if (board[j][moves[i] - 1] == dolls.get(0)) {
     answer += 2;
     board[j][moves[i] - 1] = 0;
     dolls.pop();
     break;
  }
}

뽑으려는 인형이 바구니에 가장 최근에 뽑은 인형(배열의 맨 첫 번째 요소)과 같으면 터져서 사라지는 인형의 수(2)를 늘려주고 인형을 뽑았다고 가정했기 때문에 그 자리를 0으로 만들어 준 뒤, 바구니에서 가장 최근에 뽑은 인형을 pop을 이용해서 제거해줬다.

 

삭제할 생각만 했지 인형을 뽑았다는 것을 인지하지 못하고 그 자리를 0으로 만들어 주는 과정을 해주지 않아서 30분 넘게 다른 데서 삽질을 했다..

 

전체 코드

import java.util.LinkedList;

public class ClawMachineGame {
  public int solution(int[][] board, int[] moves) {
    int answer = 0;
    LinkedList<Integer> dolls = new LinkedList<>();

    for (int i = 0; i < moves.length; i += 1) {
      for (int j = 0; j < board.length; j += 1) {
        if (dolls.size() > 0) {
          if (board[j][moves[i] - 1] == dolls.get(0)) {
            answer += 2;
            board[j][moves[i] - 1] = 0;
            dolls.pop();
            break;
          }
        }

        if (board[j][moves[i] - 1] != 0) {
          dolls.push(board[j][moves[i] - 1]);
          board[j][moves[i] - 1] = 0;
          break;
        }
      }
    }

    return answer;
  }
}

뭔가 for문 안에 for문 안에 if 문안에 또 if문이 있어서 depth가 최악인 것 같지만 내 머리로 풀 수 있는 최선이었다..

 

 

 

오랜만에 코딩 테스트 풀면서 논리 하나하나 따져가면서 약간 소소한 재미도 느끼면서 제대로 푼 것 같다. 

솔직히 이전에는 시간이 없다는 핑계로 1시간 정도 제한 걸고 못 풀면 답지 보고 풀어서 풀어도 푼 것 같지 않은 찝찝함이 있었는데, 이번에는 시간제한 두지 않고 무조건 푼다는 마인드로 끝까지 혼자 힘으로 풀어야겠다고 다짐하고 푼 문제여서 맞췄을 때 더 성취감이 있었다.

 

 

코딩테스트를 푸는 실력이 언제쯤 늘지는 모르겠지만 오늘같이 어떻게든 끝까지 풀어내는 과정이 반복되다 보면 오늘 같은 수준의 문제는 금방 푸는 날이 오지 않을까??

 

프로그래머스 레벨1 수준은 금방 푸는 수준까지 매일매일 수련하자!