[코딩테스트 이론] 스택/큐

※ 코딩테스트 합격자 되기 - 파이썬 편 (골든 래빗) 교재 참조

스택

: 먼저 들어간 것이 마지막에 나오는 규칙 (FILO)

• 스택과 세부구현

  1. 푸시 : 데이터 넣기
     1) 데이터가 가득 찼는지 확인
     2) 공간이 남아있다면 top을 +1 하고 top위치에 데이터 저장
  2. 팝 : 데이터 빼기
     1) 데이터가 비었는지 확인
     2) 데이터가 있다면 top을 -1 하고 top위치의 데이터를 반환
  3. 가득찼는지 확인
  4. 비었는지 확인
  5. top : 가장 최근에 삽입한 데이터 위치 저장 변수

  세부 구현을 알면 어떤 문제에 알고리즘을 활용할지 이해하기 쉽다!

큐

: 먼저 들어간 것이 먼저 나오는 규칙 (FIFO)

• 큐의 특성을 활용하는 분야
  • 작업 대기열 : 네트워크 통신할 때 다수의 클라이언트에서 서버에 작업을 요청하면 서버는 요청이 들어온 순서대로 작업을 처리
  • 이벤트 처리 : 어떤 애플리케이션이나 시스템에서 사용자의 이벤트 (키보드 입력이나 마우스 움직임) 처리

---

문제1

[주식 가격]

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

[프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr](https://school.programmers.co.kr/learn/courses/30/lessons/42584)

** 나의 풀이법

1) 길이 지정 후, answer 이라는 0 배열 만들기

2) prices를 차례대로 돌며 stk[-1] <= prices[i] 인 경우에 stk에 넣기

stk에 index를 넣기!

3) 만약 stk[-1] > prices[i] (주식가격이 떨어질 경우) :

stk에서 top에 해당하는 인덱스값에 i-top인덱스 (기준인덱스 - top인덱스)를 넣기

4) prices의 마지막 인덱스까지 진행 후, stk에 남은 값도 배정

def solution(prices):
    ans = [0]*len(prices)
    stk = []
    for i in range(len(prices)):
        if not stk:
            stk.append(i)
        else:
            if prices[stk[-1]] <= prices[i]:
                stk.append(i)
            else:
                while stk and prices[stk[-1]] > prices[i]:
                    a = stk.pop()
                    ans[a] = i-a
                stk.append(i)
    while stk:
        a = stk.pop()
        ans[a] = len(prices)-1-a
    return ans

문제2

[표 편집]

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

[프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr](https://school.programmers.co.kr/learn/courses/30/lessons/81303)

** 나의 풀이법 --> 시간 초과 ㅠㅠ while문에서 시간초과가 떠서 인덱스만으로 하는 풀이법 필요!

1) 삭제된 값을 넣는 stk, 각 인덱스가 삭제 되었는지 확인하는 ans 리스트 정의

2) 각 명령어마다 X일 인덱스는 뛰어넘고 현재 위치의 인덱스 k 조정

def solution(n, k, cmd):
    ans = ['O'] * n
    stk = []  # 삭제된 값
    for cd in cmd:
        c = cd.split()
        if c[0] == 'D':
            cnt = 0
            while cnt != int(c[1]):
                k += 1
                if ans[k] == 'O':
                    cnt += 1
        elif c[0] == 'U':
            cnt = 0
            while cnt != int(c[1]):
                k -= 1
                if ans[k] == 'O':
                    cnt += 1
        elif c[0] == 'C':
            stk.append(k)
            ans[k] = 'X'
            tmp = 0
            while k != (n-1) and ans[k] != 'O':
                k += 1
                tmp += 1
            if tmp == 0:
                while ans[k] != 'O':
                    k -= 1

        elif c[0] == 'Z':
            recent = stk.pop()
            ans[recent] = 'O'

    return ''.join(ans)