EDOC 2023-2 3주차 과제

03-5. 스택과 큐

 

011. 스택 수열 (백준 1874번)

 

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

 

from sys import stdin

n = int(stdin.readline())
data = []
stk = []
ans = []

for _ in range(n):
    data.append(int(stdin.readline()))

i = 0
for j in range(1, n+1):
    stk.append(j)
    ans.append("+")
    while (data[i] == stk[-1]):
        stk.pop()
        ans.append("-")
        i += 1
        if len(stk) == 0:
            break

if len(stk) == 0:
    for i in ans:
        print(i)
else:
    print("NO")

 

(정답)

 

---

 

012. 오큰수 (백준 17298번)

 

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

 

from sys import stdin

n = int(stdin.readline())
data = list(map(int, stdin.readline().split()))
stk = []
oks = [0] * n

for i in range(0, n):
    while len(stk) != 0 and data[stk[-1]] < data[i]: 
        oks[stk.pop()] = data[i]
    stk.append(i)

while len(stk) > 0:
    oks[stk.pop()] = -1

for i in oks:
    print(i, end=" ")

 

너무 어려웠다... 오빠가 옆에서 계속 힌트줘서 겨우 풀었다... 풀고 나니 코드가 넘 간단해서 약간의 현타와 상당한 쾌감... (정답)

 

---

 

013. 카드2 (백준 2164번)

 

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

 

import sys
from collections import deque

n = int(sys.stdin.readline())
deq = deque()

for i in range(1, n+1) :
    deq.append(i)

while len(deq) != 1 :
    deq.popleft()
    deq.append(deq.popleft())

print(deq.popleft())

 

(정답)

 

---

 

014. 절댓값 힙 (백준 11286번)

 

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

 

from queue import PriorityQueue
from sys import stdin

n = int(stdin.readline())
que = PriorityQueue()

for _ in range(n):
    num = int(stdin.readline())

    if num == 0:
        if que.empty():
            print(0)
        else:
            print(que.get()[1])
    else:
        que.put((abs(num), num))

 

우선순위 큐 처음 사용해봤다. 아직 원리는 잘 모르겠지만 사용하는 건 어렵지 않았다. (정답) 근데 우선순위 큐랑 힙큐는 같은건가..??

 

---

04-1. 버블 정렬

 

015. 수 정렬하기 1 (백준 2750번)

 

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

 

from sys import stdin

n = int(stdin.readline())
data = []

for i in range(n):
    data.append(int(stdin.readline()))

for i in range(0, n-1):
    for j in range(0, n-1-i):
        if data[j] > data[j+1]:
            temp = data[j]
            data[j] = data[j+1]
            data[j+1] = temp

for i in data:
    print(i)

 

예전에는 그냥 sort()로 풀었던 것 같다. 이번에는 공부삼아 버블 정렬을 직접 작성하여 풀었다. (정답)

 

---

 

016. 버블 소트 (백준 1377번)

 

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

 

from sys import stdin

n = int(stdin.readline())
data = []

for i in range(n):
    data.append((int(stdin.readline()), i))

data.sort()
max = 0

for i in range(n):
    if data[i][1] - i > max:
        max = data[i][1] - i

print(max + 1)

 

튜플을 정렬할 때는 첫번째 값으로 먼저 정렬하고, 같으면 두번째 값으로 정렬하고 이런식으로 되는 것 같다. 아마도... (정답)

 

---

04-2. 선택 정렬

 

017. 소트인사이드 (백준 1427번)

 

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

 

from sys import stdin

data = list(map(int, stdin.readline().strip()))
n = len(data)

for i in range(0, n-1):
    maxIndex = i
    for j in range(i+1, n):
        if data[j] > data[maxIndex]:
            maxIndex = j
    temp = data[maxIndex]
    data[maxIndex] = data[i]
    data[i] = temp

for i in data:
    print(i, end="")

 

이것도 마찬가지로 예전에 풀었던 문제지만 공부겸 선택 정렬로 다시 풀었다. (정답)