3회 테코테코

 

---

≣ 목차

• 요약
• Stack
  • 첫 번째 문제
    • 접근 방법
    • 고민 포인트
    • 최종 코드 및 회고
    • 1. 최상단 인덱스를 list 로 만드는 방법
    • 2. board 를 stack 으로 만드는 방법

---

요약

- stack 을 사용할 수 있다.

---

Stack

첫 번째 문제

https://school.programmers.co.kr/learn/courses/30/lessons/64061

프로그래머스

접근 방법

- 바구니를 stack 으로 저장하고, 바구니에 동일한 인형이 연속해서 들어올 경우 삭제한다.

고민 포인트

- 값이 1 이상일 때만 인형을 뽑을 수 있다.

- board 의 최대 범위 30, moves 의 최대 범위 1,000이므로, O(N^2) 문제 풀이가 가능하다.

최종 코드 및 회고

- 직관적으로 인형을 바구니에 담는 건 stack 자료 구조를 이용했다.

- O(n^2) 30*1,000 = 30,000 으로 시간 복잡도가 측정된다.

import java.util.*;

class Solution {
    public int solution(int[][] board, int[] moves) {
        
        Stack<Integer> basket = new Stack<>();
        int answer = 0;
        
        //뽑기 횟수만큼 진행
        for (int move : moves) {
            for (int i = 0; i < board.length; i++) {
                int tmp = board[i][move - 1];
                //인형이 있는 경우만 뽑기 진행
                if (tmp > 0) {
                    //인형 1개만 뽑아서 바구니에 넣음
                    basket.push(tmp);
                    board[i][move - 1] = 0;
                    break;
                }
            }
            //바구니에 연속해서 쌓인 인형이 있을 경우 제거
            if (basket.size() > 1) {
                int pop = basket.pop();
                if (pop == basket.peek()) {
                    answer += 2;
                    basket.pop();
                }
                else basket.push(pop);
            }
        }
        return answer;
    }
}

1. 최상단 인덱스를 list 로 만드는 방법

 

2. board 를 stack 으로 만드는 방법