[항해99 취업 리부트 코스 학습일지] 본격적인 자료구조의 시작

스택, 큐, 덱을...

알고리즘 문제풀이 2주 차 6일 차

어제 공부하다 늦게 자서 그런가 몸이 너무 무거웠다.

진짜 너무 피곤해서 아침에 알람 듣고 다시 잘 뻔...

그래도 한 주 시작이니까 힘차게 달렸다!

---

0. TIL (2024.06.05)

📚오늘 진행한 문제 리스트

1. 백준 1966 프린터 큐 (실버 3) ✔️

https://www.acmicpc.net/problem/1966

풀이⬇️

# 백준 1966 프린터 큐 - 실버 3

# queue에서 중요도 확인 -> 자신보다 숫자 큰게 하나라도 있는지 -> any 사용
# 있으면 맨 뒤로 없으면 인쇄 -> 근데 내가 찾던 인덱스의 숫자다? 바로 print
# 그럼 중요도에 순서를 지정해줘야함. -> enumerate

# 34028/72
import sys
from collections import deque
input = sys.stdin.readline


T = int(input())
for _ in range(T):
    N, idx = map(int, input().strip().split())
    q = deque()
    for i, x in enumerate(map(int, input().strip().split())):
        q.append((x, i))
    cnt = 1
    while q:
        num, target = q.popleft()
        if any(num < x[0] for x in q):
            q.append((num, target))
        else:
            if idx == target:
                print(cnt)
                break
            else:
                cnt += 1

내가 찾는 인덱스가 언제 나오는지 찾는 문제

Queue에 중요도와 인덱스를 넣고 순회하면서 중요도 높은 순서로 빼주면서 내가 원하는 인덱스의 중요도가 나왔을 때, 종료하면 끝!

 

2. 백준 1021 회전하는 큐 (실버 3) ✔️

https://www.acmicpc.net/problem/1021

풀이⬇️

# 백준 1021 회전하는 큐 - 실버 3

# deque의 rotate 이용해서 해결한다.
# 내가 찾는 숫자를 기준으로 양 옆에 몇 개가 있는지 보고 개수 더 적은 방향으로 회전
import sys
from collections import deque


input = sys.stdin.readline
N, M = map(int, input().strip().split())
arr = [x for x in map(int, input().strip().split())]
q = deque([x for x in range(1, N + 1)])
cnt = 0
for n in arr:
    idx = q.index(n)
    if idx <= len(q) - idx:
        q.rotate(-idx)
        cnt += idx
    else:
        q.rotate(len(q) - idx)
        cnt += (len(q) - idx)
    q.popleft()
print(cnt)

deque의 rotate() 메서드를 오랜만에 써봐서 그런지 처음에 rotate가 바로 생각이 안 났다.

혼자 구현하려고 했다가 불현듯 스치는 기억이 날 잡아끌어서 찾아낼 수 있었다.(칭찬한다. 나 자신)

그 이후에는 조건에 따라 최솟값을 구하기 위해 회전 수가 적은 방향을 찾고 찾은 방향으로 회전시키면서 최솟값 갱신을 진행하면 된다.

 

3. 백준 9012 괄호 (실버 4) ✔️

https://www.acmicpc.net/problem/9012

풀이⬇️

# 백준 9012 괄호 - 실버 4

# 들어오는 괄호의 모양과 현재 존재하는 괄호의 모양에 따라 기준을 나누어 구현
import sys
input = sys.stdin.readline


T = int(input())
for i in range(T):
    stack = []
    PS = [x for x in input().strip()]
    for p in PS:
        if p == '(':
            stack.append(p)
        elif stack:
            stack.pop()
        else:
            stack.append(p)
            break

    print('YES') if not stack else print('NO')

대표적인 Stack 문제

사실 괄호만 있으면 굳이 Stack 사용 안 해도 되긴 하는데 그래도 Stack 문제인 만큼 써서 해결했다.

 

4. 백준 2346 풍선 터뜨리기 (실버 3) ✔️

https://www.acmicpc.net/problem/2346

풀이⬇️

# 백준 2346 풍선 터뜨리기 - 실버 3

# 첫 번째 풍선부터 터뜨리고 나온 숫자대로 로테이션해서 계속 터뜨리면 된다.

# 34016/64
import sys
from collections import deque


input = sys.stdin.readline
N = int(input())
q = deque([(x, i) for i, x in enumerate(map(int, input().split()))])
ans = []
for _ in range(N):
    mv_cnt, idx = q.popleft()
    ans.append(idx + 1)
    mv_cnt -= 1 if mv_cnt > 0 else 0
    q.rotate(-mv_cnt)
print(*ans)

이 문제도 rotate 쓰는 문제랑 동일해서 쉽게 해결할 수 있었다.

근데 회전 방향 어떻게 잡는지 헷갈려서 디버깅을 좀 오래 했다..

 

5. 백준 24511 queuestack (실버 3) ✔️

https://www.acmicpc.net/problem/24511

풀이⬇️

# 백준 24511 queuestack - 실버 3

# 각각의 자료구조를 거쳐가면서 최종 나오는 x_n을 리턴하는 queuestack 만들기
# 0이면 Queue 1이면 Stack
# 시간초과 -> O(M*N) -> Stack은 들어왔다가 다시 나가니까 고려하지 말자 -> O(M)

import sys
from collections import deque
input = sys.stdin.readline


def operate_queuestack(arr_by_type, element):
    arr_by_type.appendleft(element)
    return arr_by_type.pop()


def main():
    N = int(input())
    types = [x for x in map(int, input().split())]
    arr = [y for y in map(int, input().split())]
    arr_by_type = deque([x for t, x in zip(types, arr) if t == 0])
    M = int(input())
    q_s_arr = [x for x in map(int, input().split())]
    ans = []
    for i in range(M):
        ans.append(operate_queuestack(arr_by_type, q_s_arr[i]))
    return ans


print(*main())

문제 읽다 지친 문제...

아니 한국말을 못 알아먹겠어서 몇 번을 다시 읽어봤다.

그니까 결국 0이냐 1이냐에 따라서 Queue와 Stack이 결정되고, 해당 타입의 개수만큼 자료구조들이 생성이 되는데 이를 통합한 게 queuestack이다.

사실 이 부분만 이해하고 넘어가면 나머지는 구현하라는 대로 하면 된다.

다만, 이걸 곧이곧대로 구현하려고 하면 시간초과가 날 것이다.

방법은 Queue의 경우, 선입선출인데 Stack은 후입선출이기 때문에 넣었다 빼면 안 넣은 거랑 똑같다.

그래서 Stack을 완전히 배제해 주고 하나의 Queue로 생각해서 문제를 풀면 된다.

 

6. 백준 1080 행렬 (실버 1) ✔️

https://www.acmicpc.net/problem/1080

풀이⬇️

# 백준 1080 행렬 - 실버 1

import sys
input = sys.stdin.readline


def change_matrix(i, j, matrix):
    for x in range(i, i + 3):
        for y in range(j, j + 3):
            matrix[x][y] = 1 - matrix[x][y]


def main():
    N, M = map(int, input().split())
    matrix_A = [list(map(int, input().strip())) for _ in range(N)]
    matrix_B = [list(map(int, input().strip())) for _ in range(N)]
    cnt = 0
    for i in range(N - 2):
        for j in range(M - 2):
            if matrix_A[i][j] != matrix_B[i][j]:
                change_matrix(i, j, matrix_A)
                cnt += 1

    if matrix_A == matrix_B:
        return cnt

    return -1


print(main())

이 문제도 좀 재밌었는데

3X3의 부분 행렬을 바꿔주면서 목표로 한 행렬과 일치하는지 여부를 판별하는 문제였다.

행렬을 뒤집는 기준은 (0,0)부터 시작해서 최대 길이 - 3만큼의 범위를 갖고 원래 행렬과 목표 행렬의 동일 부분이 일치하는가를 보고 일치하지 않다면 무조건 뒤집어야 한다는 의미이다.

이게 결국 최소를 보장해준다고 한 것 같다.

 

7. 백준 2493 탑 (골드 5) ✔️

https://www.acmicpc.net/problem/2493

풀이⬇️

# 백준 2493 탑 - 골드 5

# O(N^2) = 2500억
# 최대 O(NlogN)
# 탑들을 뒤에서 부터 순회하면서 자신보다 큰 타워가 있다면 스택이 비워질 때까지 해당 타워의 인덱스 + 1 기록
# 없다면 스택에 저장하고 다음 타워 순회
import sys
input = sys.stdin.readline


N = int(input())
towers = [(i, x) for i, x in enumerate(map(int, input().split()))]
stack = []
answer = [0] * N
for i in range(N - 1, -1, -1):
    idx, target = towers[i]
    if not stack:
        stack.append((idx, target))
        continue

    while stack and stack[-1][1] < target:
        answer[stack[-1][0]] = idx + 1
        stack.pop()
    stack.append((idx, target))

print(0) if all(x == 0 for x in answer) else print(*answer)

탑의 레이저 방향으로 순회하면서 나보다 큰 타워를 만나면 Stack에 있는 요소들 전부 해당 타워의 인덱스를 기록해 주고 아니라면 Stack에 저장해 놓는 방식으로 구현했다.

그리고 출력 방식에 대해서 만약 전부 0이라면 0 하나만 출력해야 하는데 그 부분에서 출력 초과가 4번이나 일어나서 뭐가 문제인지 한참 찾았다.... ;(

 

8. 백준 9935 문자열 폭발 (골드 4) ✔️

https://www.acmicpc.net/problem/9935

풀이⬇️

# 백준 9935 문자열 폭발 - 골드 4

# 특정 문자열이 발견되면 모든 폭발 문자열이 폭발한다.
# 슬라이싱 사용해서 하면 O(N^2) = 10^12 예상 -> 무조건 터짐
# 괄호 문제랑 비슷하게 접근 -> stack에 한 글자씩 보내면서 stack의 뒤의 두 자리가 폭발 문자열이 됐을 때, pop해주는 방법
import sys
input = sys.stdin.readline


def search_explosion_s(string, explosion_string):
    stack = []
    ex_len = len(explosion_string)

    for i in range(len(string)):
        stack.append(string[i])
        if ''.join(stack[-ex_len:]) == explosion_string:
            for _ in range(ex_len):
                stack.pop()

    return stack


def main():
    s = input().strip()
    explosion_s = input().strip()
    arr = search_explosion_s(s, explosion_s)
    return ''.join(arr) if arr else 'FRULA'

print(main())

이것도 문자 순회하면서 Stack에 넣고 Stack의 마지막 두 요소가 폭발 문자열과 같다면 그 요소들을 전부 빼주는 방식으로 구현했다.

---

📝오늘자 질문

1. 오늘 진행된 강의에서 학습한 내용은 무엇인가요

• 스택, 큐, 덱

 

2. 이번 주 진행된 팀 스터디에서 얻은 인사이트는 무엇인가요?

• 함수로 컴포넌트화 연습하기
• deque.rotate() 메서드를 사용한 문제의 이해도를 높이자.(회전이 헷갈린다 ㅠ)

---

* 항해99 취업 리부트 코스를 수강하고 작성한 콘텐츠 입니다.

https://hanghae99.spartacodingclub.kr/reboot

IT 커리어 성장 코스 항해99, 개발자 취업부터 현직자 코스까지