[Coding Test] 1주차 - Data Structure1 (스택, 큐, Deque)

💗10799 쇠막대기

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

10799번: 쇠막대기

[ 풀이 ]

스택 이용

1. "(" 일 경우 스택에 일단 append
2. ")"일 경우 레이저인지 아닌지 구분해야함
3. ")"일 때 바로 이전 문자가 "("라면 레이저이므로 스택 길이만큼 쇠막대기 개수 더하기
4. 바로 이전 문자가 "(" 가 아니라 ")"라면 쇠막대기이므로 +1

[ 코드 ]

steel = list(input())
stack = []
result = 0
for i in range(len(steel)):
    if steel[i] == '(':
        stack.append('(')
    else:
        if steel[i-1] == '(':
            stack.pop()
            result += len(stack)
        else:
            stack.pop()
            result += 1

print(result)

---

💗1158 요세푸스 문제

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

1158번: 요세푸스 문제

[ 풀이 ]

deque 이용

1. 사람 수 만큼 deque(circle)에 1부터 n까지 저장
2. circle에서 k번째 사람을 삭제하기 위해 k-1까지는 popleft한 다음 다시 append
3. 마지막 k번째는 popleft하고 정답 리스트에 추가

[ 코드 ]

from collections import deque

n, k = map(int, input().split())
circle = deque([i for i in range(1, n+1)])
result = []
while len(circle) != 0:
    cnt = k
    while cnt != 1:
        circle.append(circle.popleft())
        cnt -= 1
    x = circle.popleft()
    result.append(x)

print("<", end="")
print(*result, sep=", ", end="")
print(">")

---

💗1966 프린터큐

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

1966번: 프린터 큐

[ 풀이 ]

m이 빠져나온 것을 -1이라고 생각하고 -1이 될 때까지 다음 과정 진행

1. 중요도 순으로 제거하기 위해서 중요도가 가장 큰 것이 맨 앞에 있으면 삭제
   • result(m이 몇 번째에 빠져나가는지 카운트) 증가
2. 중요도가 가장 큰 것이 맨 앞에 있지 않으면 맨 뒤로 보내고 삭제
   • 맨 뒤로 보낼때 m이 어디에 있었는지 기억하기 위해 m위치도 조정

[ 코드 ]

t = int(input())
for i in range(t):
    n, m = map(int, input().split())
    star = list(map(int, input().split()))
    result = 0
    while m != -1:
        if star[0] == max(star):
            del star[0]
            m -= 1
            result += 1
        else:
            star.append(star[0])
            del star[0]
            if m == 0:
                m = len(star) - 1
            else:
                m -= 1

    print(result)

---

💗9012 괄호

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

9012번: 괄호

[ 풀이 ]

스택 이용

1. 문자열을 받은 후 "("라면 일단 스택에 append
2. ")"라면 스택에서 pop하는데 스택이 비었다면 바로 NO출력
3. 모든 문자열을 돌았을 때 스택이 비었다면 YES출력하고 그렇지 않으면 NO출력

[ 코드 ]

t = int(input())
for _ in range(t):
    stack = []
    s = input()
    for j in s:
        if j == "(":
            stack.append(j)
        else:
            if stack:
                stack.pop()
            else:
                print("NO")
                break
    else:
        if not stack:
            print("YES")
        else:
            print("NO")