📖저자님의 책 소개 영상: https://www.youtube.com/watch?v=Q13Uj_5bH9M

▪️ 한 번 풀어보고, 시간 복잡도 계산해보기
▪️ 문제 주어진 시간 이내 해결 못 하면, 해설을 통해 해결.
단, 오답노트처럼 기록
👍 문제를 푸는데 <풀이 그림> 덕분에 이해가 쉽다. 완전!!

🔷 6. 스택 ⭐⭐

6-1 개념

1. 쌓는다.
2. 먼저 들어간 것이 마지막에 나오는 규칙 = 선입후출, First In Last Out(FILO)
3. 삽입(push), 꺼냄(pop)
4. 스택의 ADT(abstract data type)
   ✅ 좀 더 찾아보기
   - push
   - pop
   - isFull
   - isEmpty
   - top(최근에 삽입한 데이터 위치를 저장할 변수)

6-4 문제

1. 괄호 회전하기

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

• 그림 실제로 그리기

def solution(s):
    answer = 0
    n = len(s)
    for i in range(n):
        stack = []
        for j in range(n):
            c = s[(i+j) % n] # 인덱스 활용
            if c == "(" or c == "{" or c == "[":
                stack.append(c)
            else:
                if not stack:
                    break

                if c == ")" and stack[-1] == "(":
                    stack.pop()
                elif c == "]" and stack[-1] == "[":
                    stack.pop()
                elif c == "}" and stack[-1] == "{":
                    stack.pop()
                else:
                    break
        else:
            if not stack:
                answer += 1
        return answer

✅ 책 풀이 체크

짝지어 제거하기

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

• 문자열을 붙이는 연산은 팝 연산으로 자연스럽게 해결할 수 있으므로 구현 시 고려할 필요가 없다.
• 문자열의 짝을 전부 제거할 수 있는지 체크하는 게 중요
• 현재 가리키고 있는 문자가 i번째라면 다음 문자는 i+1번째이므로 이 둘을 비교.

def solution(s):
    stack = []   
    for i in s:
        if stack and stack[-1] == i:
            stack.pop()          
        else:
            stack.append(i)
            
    return int(not stack) #비어 있으면 1, 안 비어 있으면 0

• 시간복잡도: 모든 문자를 한 번씩 거쳐가므로 $O(n)$

3.주식 가격

https://school.programmers.co.kr/learn/courses/30/lessons/42584
✅ $O(N)$으로 푸는 방법

def solution(prices):
    n = len(prices)
    answer = [0] * n
    
    stack = [0]
    for i in range(1,n):
        while stack and prices[i] < prices[stack[-1]]:
            j = stack.pop()
            answer[j] = i - j
        stack.append(i)
    while stack:
        j = stack.pop()
        answer[j] = n - 1 - j
    
    return answer 

⌛ $O(N)$

• stack으로 생각하고 구현하기가 어렵..
• 100,000 이하라는 조건 때문에 $O(N^2)$으로 문제를 풀 수 없음.

4.크레인 인형 뽑기

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

5.표 편집(hard)

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

🔷7. 큐(queue) ⭐⭐

7-1 개념

1. 줄을 서다
2. 선입선출, FIFO(first in first out)
3. 맛집에 줄 입장, 이벤트 처리, 작업 대기열
4. 큐의 ADT
   • push
   • pop
   • isFull
   • isEmpty: front/rear 값이 같은지 확인 후, 원소가 없는데 팝하지 않도록 방지함.
   • front
   • rear

• 데이터가 없는 상태에서는 front, rear 모두 -1.
• 큐는 front의 다음부터 rear까지를 큐가 관리하는 데이터로 생각해야 한다. data는 $n$개인데, 큐가 관리하는 데이터는 $n-1$이므로 메모리 공간을 낭비한 상황. 이렇게 되는 이유는 큐를 한 방향으로 관리하고 있기 때문이다.
  ✒️ 메모리 낭비를 개선하려고 만든 게 원형 큐(코테에서는 메모리 때문에 굳이 할 필요는 없다.)
• DEQ: Double Ended Queue, 양 끝에서 삽입이나 삭제할 수 있는 큐

7-2 문제

1. 요세푸스 문제

✅ 문제 이해 ok, 어떻게 풀 것인가?
-> 세그먼트 트리 사용하면 $O(NlogN)$으로 개선 가능함.

from collections import deque

def solution(N, K):
    queue = deque(range(1, N+1))
    
    while len(queue) > 1:
        for _ in range(K-1):
            queue.append(queue.popleft()) # 앞의 것을 뒤에 추가(한 칸 돌려돌려)            
            queue.popleft() #맨 앞 제거
        return queue[0]
    
print(solution(5,2))
            

2. 기능 개발

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

3. 카드 뭉치

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