[크래프톤 정글] 13일 - Stack

wnajsldkf·2023년 4월 15일

TIL algorithm

정글

목록 보기

7/14

오늘 한 일🌴

Stack 공부

Algorithm 문제 풀이(2470, 11053, 1629, 10828, 10773, 9012, 17608, 2493)

Stack

데이터를 임시 저장할 때 사용하는 자료구조이다. 데이터의 입력과 출력 순서는 후입선출(LIFO: Last In First Out) 방식이다.

고정 길이 Stack

class FixedStack:
    """고정 길이 스택 클래스"""

    class Empty(Exception):
        """비어 있는 FixedStack에 팝 또는 피크할 때 내보낸다."""
        pass

    class Full(Exception):
        """가득 찬 FixedStack에 푸시할 때 내보내는 예외 처리"""
        pass

    def __init__(self, capacity):
        """스택 초기화"""
        self.stk = [None]*capacity  # 스택 본체
        self.capacity = capacity    # 스택의 크기
        self.ptr = 0                # 스택 포인터

    def __len__(self):
        """스택에 쌓여 있는 데이터 개수 반환"""
        return self.ptr

    def is_empty(self):
        return self.ptr <= 0

    def is_full(self):
        return self.ptr >= self.capacity

    def push(self, value):
        """스택에서 value를 푸시(데이터를 넣음)"""
        if self.is_full():          # 스택이 가득 차 있는 경우
            raise FixedStack.Full
        self.stk[self.ptr] = value
        self.ptr += 1

    def pop(self):
        """스택에서 데이터를 팝(꼭대기를 꺼냄)"""
        if self.is_empty():         # 스택이 비어 있는 경우
            raise FixedStack.Empty
        self.ptr -= 1
        return self.stk[self.ptr]

    def peek(self):
        """스택에서 데이터를 피크: 보기만 한다."""
        if self.is_empty():         # 스택이 비어 있는 경우
            raise FixedStack.Empty
        return self.stk[self.ptr - 1]

    def clear(self):
        """스택을 비움: 모든 데이터를 삭제"""
        self.ptr = 0

    def find(self, value):
        """스택에서 value를 찾아 인덱스를 반환: 없으면 -1 반환"""
        for i in range(self.ptr - 1, -1, -1):   # 꼭대기부터 선형 검색
            if self.stk[i] == value:
                return i
        return -1

    def count(self, value):
        """스택에 있는 value 개수를 반환"""
        c = 0
        for i in range(self.ptr):
            if self.stk[i] == value:
                c += 1
        return c

    def __contains__(self, value):
        """스택에 value가 있는지 판단"""
        return self.count(value) > 0

    def dump(self):
        """덤프: 스택 안의 모든 데이터를 바닥부터 꼭대기 순으로 출력"""
        if self.is_empty():
            print('스택이 비어 있습니다.')
        else:
            print(self.stk[:self.ptr])

Deque를 사용한 Stack

from typing import Any
from collections import deque

class Stack:
    """고정 길이 스택 클래스(collections.deque 사용)"""

    def __init__(self, maxlen):
        """스택 초기화"""
        self.capacity = maxlen
        self.__stk = deque([], maxlen)

    def __len__(self):
        """스택에 쌓여 있는 데이터 개수를 반환"""
        return len(self.__stk)

    def is_empty(self):
        """스택이 비어 있는지 판단"""
        return not self.__stk

    def is_full(self):
        """스택이 가득 차 있는지 판단"""
        return len(self.__stk) == self.__stk.maxlen

    def push(self, value):
        """스택에 value 푸시"""
        self.__stk.append(value)

    def pop(self):
        """스택에서 데이터 팝"""
        return self.__stk.pop()

    def peek(self):
        """스택에서 데이터를 피크"""
        return self.__stk[-1]

    def clear(self):
        self.__stk.clear()

    def find(self, value):
        """스택에서 value를 찾아 인덱스를 반환(찾지 못하면 -1을 반환)"""
        try:
            return self.__stk.index(value)
        except ValueError:
            return -1

    def count(self, value):
        """스택에 포함되어 있는 value의 개수를 반환"""
        return self.__stk.count(value)

    def __contains__(self, value):
        """스택에 value가 포함되어 있는지 판단"""
        return self.count(value)

    def dump(self):
        """스택 안에 있는 모든 데이터를 나열(바닥에서 꼭대기 순으로 출력한다.)"""
        print(list(self.__stk))

Algorithm

2470: 두 용액

계속 시간 초과나서 확인해보니 elif가 문제였다.
아래 부분에서 else 대신 elif로 판단하기 계속 시간 초과가 났다. 평소에 공부 차원에서 else 보다 elif로 구분하는 편인데, 알고리즘에서는 하지 않는게 좋겠다.

if abs(total) < answer:
	answer = abs(total)
    left_value = liquid[left]
    right_value = liquid[right]
    if answer == 0:
        break 
	# 양수이면
    if total > 0:
        right -= 1
    # 음수이면
    else:
        left += 1

11053: 가장 긴 증가하는 부분 수열

dp와 이진탐색 모두 풀이할 수 있는 문제다.
dp만 사용하면 n*n의 복잡도를 갖기 때문에 범위가 커지면 적절하지 않다. dp에 이진탐색을 사용하면 nlogn으로 풀이할 수 있다.
가장 인접한 원소 중에 큰 값을 찾는 과정에서 어제 공부한 인접한 원소 찾는 코드를 사용할 수 있었다.