5. 자료구조(스택, 큐, 해쉬, 힙)

스택

· LIFO: Last In First Out, 나중에 들어간 게 먼저 나온다.

· 들어가는 입구와 나오는 출구가 같다.

· 파이썬은 리스트로 스택을 구현할 수 있다. 리스트 그 자체가 스택의 속성을 띰.

 

1. 가장 큰 수(스택)

입력예제 1번 5276823을 가지고 문제를 이해해보자면, 각 숫자들은 자신 앞에 자신보다 더 작은 숫자가 있으면 그 숫자를 없애고(지우고) 앞으로 가야한다.

 

1) 5

5

 

2) 2 - 앞의 숫자가 자기보다 큼 → 지우지 않음

5 2

 

3) 7 - 앞의 숫자들이 자기보다 작음 → 지우고 앞으로 전진

5 2 7 즉,

 

4) 6

7 6

 

5) 8 - 7은 지울 수 없기 때문에(지우는 횟수 끝) 6까지만 지울 수 있음

7 6 8

 

6) 더이상 지울 수 없기 때문에 답은

7 8 2 3

 

 

입력예제 2번 9977252641 풀이

 

1) 9

9

 

2) 9 - 앞 숫자(9)가 자기보다 크지 않기 때문에(같다) 그냥 들어간다.

9 9

 

3) 7 - 앞 숫자(9)가 자기보다 크기 때문에 그냥 들어간다.

9 9 7

 

4) 7 - 들어간다.

9 9 7 7

 

5) 2 - 들어간다.

9 9 7 7 2

 

6) 5 - 앞 숫자(2)가 보다 작기 때문에 2를 지우고 들어간다.

9 9 7 7 5

 

7) 2 - 들어간다.

9 9 7 7 5 2

 

8) 6 - 2보다 크므로 2를 지우고, 5보다도 크므로 5도 지우고 앞으로 간다. (7보다는 작음)

9 9 7 7 6

 

9) 4와 1은 들어간다.

9 9 7 7 6 4 1

 

그런데 5개의 숫자를 지워야 하는데, 3개밖에 지우지 않았으므로 뒤에서부터 숫자 2개를 더 지워야 한다.

→ 리스트의 인덱싱 이용

숫자가 내림차순으로 들어가있기 때문에 뒤 숫자를 지우는 것. 

 

n, m = map(int, input().split())
r = m
n = list(map(int, str(n)))  # 정수를 숫자 하나씩 쪼개서 list에 넣는다. (str형변환 필수)
stack = []

for x in n:
    while stack and m > 0 and stack[-1] < x:  # 여러 조건들을 한번에 처리, 지울 수 있는 건 최대한 지운다.
        stack.pop()
        m -= 1
    stack.append(x)

if m != 0:
    stack = stack[:-m]

res = ''.join(map(str, stack))
print(res)

'''
그냥 이렇게 해도 됨
for x in stack:
    print(x, end = '')
'''

** 백준 2812번 크게 만들기 문제와 같은 문제

 

breakcoding.tistory.com/109

[Python] 백준 시간초과 해결, 입출력 속도 개선

---

2. 쇠막대기(스택)

일단.. 그림부터 어려워보이긴 했는데 문제를 읽으니 더 어떻게 해야 할 지 막막했던..

 

먼저, 예제보다 더 쉬운 예시를 가지고 어떻게 풀 지 고민해보자. (결국 강의를 보았다.)

( ( ( ) ( ) ) ) 를 예시로 들겠다. 맨 왼쪽에서부터 보기 시작한다.

 

( ( ( ) ( ) ) ) - ( 이 나왔다. 아직 이게 쇠막대기의 시작인지 레이저의 시작인 지 알 수 없다. 넘어간다.

( ( ( ) ( ) ) ) - ( 이 또 나왔다. 따라서 이전의 ( 은 쇠막대기의 시작이라고 확정할 수 있다. (아직 쇠막대기의 길이는 알 수 없다.) 두 번째 ( 은 아직 쇠막대기의 시작인지 레이저의 시작인지 알 수 없다.

( ( ( ) ( ) ) ) - ( 이 또 나왔다. 위의 설명과 같다.

( ( ( ) ( ) ) ) - ) 이 처음으로 나왔다. 이 전의 기호를 보니 ( 이다. ( ) 이 연결되어 나왔으므로 레이저다. 레이저를 쏘는 순간 쇠막대기 2개가 절단된다. 레이저로 절단된, 쇠막대기 앞의 부분을 카운트해줘야 한다.

( ( ( ) ( ) ) ) - ( 이 나왔다. 아직 쇠막대기인지 레이저인지 알 수 없다. 넘어간다.

( ( ( ) ( ) ) ) - ) 이 나왔다. 이 전의 기호가 ( 이므로 레이저다. 쇠막대기가 절단되므로 이번에도 레이저로 절단된 부분을 카운트한다.

( ( ( ) ( ) ) ) - ) 이 나왔다. 앞 기호가 ) 이므로 이번 ) 은 쇠막대기의 끝을 의미한다. 쇠막대기의 끝이 생겼으므로 이 부분도 카운트해주어야 한다.

( ( ( ) ( ) ) ) - 위 설명과 같다.

 

결국 최종적으로 쇠막대기의 개수는 6개가 된다.

이해가 잘 되지 않는다면 인프런 강의를 다시 보자! (직접 그려보면서 하면 이해가 갈 것이다.)

 

이걸 어떻게 코드로 구현하느냐가 문제이다. 스택으로 구현할 수 있는 이유를 생각해보자.

( 이 나오면 계속 append를 하다가, ) 이 나오고 이게 레이저로 판단된다면 stack의 top인 ( 를 pop하고 스택에 쌓여있는 ( 의 개수를 카운트한다. ( 의 개수가 곧 막대기의 개수이니까. 그리고 ) 가 나왔는데 레이저가 아니고, 쇠막대기의 끝이라면 +1을 해주고 stack의 top을 pop해주면 된다.

 

열심히 코딩을 해서..!! 결국 내가 맞는 코드를 짰다!! 강의 보기 전에!!

사실 로직은 다 강의에서 배운 거긴 하지만.. 그래도 잘 했다! (나중에 강의 보니까 강사님 코드랑 존똑임 소름.)

s = input()
stack = []
cnt = 0

for i in range(len(s)):
    if s[i] == '(':
        stack.append(s[i])
    else:
        if s[i-1] == '(':
            stack.pop()
            cnt += len(stack)
        else:
            stack.pop()
            cnt += 1
print(cnt)

결국 '쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다.' 라는 조건이 가장 핵심인 것 같다. ) 가 나오면 차례대로 처리할 수 있으니까. 

 

자료를 맨 앞부터 차근차근 쌓아간다고 생각하고 그림을 그려보면서 이해했으면, 문제에 접근하기 조금 더 쉽지 않았을까 싶다.

 

근데 코드를 자세히 보면 stack.pop()이 중복되니까 그 부분을 아래 코드처럼 고치면 더 좋은 코드가 될 것이다.

s = input()
stack = []
cnt = 0

for i in range(len(s)):
    if s[i] == '(':
        stack.append(s[i])
    else:
        stack.pop()  # 여기!
        if s[i-1] == '(':
            cnt += len(stack)
        else:
            cnt += 1
print(cnt)

---

3. 후위표기식 만들기(스택)

20분 정도 고민했는데 전~혀 모르겠다.

백준 1918번 문제를 보고 중위표기식을 후위표기식으로 변환하는 방법은 충분히 이해했는데, 이걸 어떻게 스택으로 구현할 수 있는 것인지 모르겠다.

 

강의를 보고 나니 이해가 되었다. 먼저, 연산자 사이의 우선 순위를 고려해야 한다. *와 /가 +와 -보다 우선이다. 그리고 그들보다 ( ) 가 더 우선이다. 즉, ( ) * / + - 순이라고 생각하자. 그리고 스택에 연산자를 넣었다 뺐다 하면서 식을 완성해나갈 것이다. (스택은 우선 순위를 가진 자료들을 처리하기에 좋은 자료구조 같다는 생각이 든다.)

 

스택에 남아있는 연산자는 현재 넣을 연산자보다 우선순위가 뒤인 연산자들이라는 점을 명심하자.

-> 빨리 연산해야 하는 연산자들일수록 스택에서 빨리 나오게 된다. (연산자들 사이의 우선순위, 식에 포함된 위치에 따른 우선순위 고려)

 

후위표기식을 계산하는 방법을 생각해보면, 연산자가 나오면 바로 앞의 두 숫자를 가지고 해당 연산을 수행하므로 그 순서가 그렇게 된다. (그냥 다시 직접 해보면서 이해해라.. 말로 설명하기 어렵다.)

숫자는 변수를 만들어서 거기에 누적하든, 바로 출력하든 상관이 없으므로 그냥 출력이라고 하겠다.

 

3 + 5 * 2 / ( 7 - 2 ) → 숫자 3을 출력한다.

3 + 5 * 2 / ( 7 - 2 ) → +를 스택에 push한다.

3 + 5 * 2 / ( 7 - 2 ) → 5를 출력한다. 

3 + 5 * 2 / ( 7 - 2 ) → *가 나왔다. 현재 스택에 있는 연산자는 +이므로 신경 쓸 필요가 없다. 스택에 push한다.

3 + 5 * 2 / ( 7 - 2 ) → 2를 출력한다.

3 + 5 * 2 / ( 7 - 2 ) → 현재 스택에는 차례대로 +와 *이 들어있는 상태이다. *이 /보다 우선순위가 앞이므로(실제로는 동일하지만, 원래 식에서 / 보다 앞에 위치하는 것이므로 먼저 계산해야 한다. 즉, 동일한 우선순위에 있는 연산자는 pop해야 한다.) *을 스택에서 pop하여 출력한다.

3 + 5 * 2 / ( 7 - 2 ) → 열린 괄호가 나왔다. 열린 괄호는 무조건 스택에 그냥 push한다. 닫힌 괄호가 언제 나올지 모르고, 후위식으로 표현하는 방법을 생각해보면 ( 앞의 연산자는 ) 보다 뒤에 나와야 하기 때문에 스택에 담긴 연산자들을 굳이 꺼내줄 필요가 없다.

3 + 5 * 2 / ( 7 - 2 ) → 7을 출력한다.

3 + 5 * 2 / ( 7 - 2 ) → 현재 스택에는 차례대로 +, /, ( 가 들어있는 상태이다. -보다 우선순위가 앞인 연산자들이 들어있으므로 스택에 push한다.

3 + 5 * 2 / ( 7 - 2 ) → 2를 출력한다.

3 + 5 * 2 / ( 7 - 2 ) → 닫힌 괄호가 나왔다. 현재 스택에는 +, /, (, - 가 들어있다. -는 닫힌 괄호보다 우선순위가 낮으므로 pop해주어야 한다. 그리고 ( 도 이제 필요없으니 pop하여 삭제한다.

 

이제 식의 처리가 끝났으므로, 스택에 남아있는 연산자들은 차례대로 pop해준다.

 

이를 코드로 구현하면 다음과 같다.

a = input()
stack = []
res = ""

for x in a:
    if x.isdecimal():  # x가 10진수이면 참
        res += x
    else:
        if x == '(':
            stack.append(x)
        elif x == '*' or x == '/':
            while stack and (stack[-1] == '*' or stack[-1] == '/'):
                res += stack.pop()
            stack.append(x)
        elif x == '+' or x == '-':
            while stack and stack[-1] != '(':  # 여기 중요, 만약 (가 앞에 있다면 이는 곧 괄호 안의 연산자라는 거고, stack[-1]의 우선순위가 가장 높다는 뜻. -> pop하면 안된다.
                res += stack.pop()
            stack.append(x)
        elif x == ')':
            while stack and stack[-1] != '(':
                res += stack.pop()
            stack.pop()

while stack:
    res += stack.pop()

print(res)

 

안녕하세요.

"섹션5. - 3번_후위표기식 만들기" 질문이 있습니다.

for x in data:

    if x.isdecimal():

        res += x

    else:

        if x == '(':

            stack.append(x)

        elif x == '*' or x == '/':

            while stack and (stack[-1] == '*' or stack[-1] == '/'):

                res =+ stack.pop()

            stack.append(x)

...

... 

...

연산자가 곱셈(*)이랑 나눗셈(/)일때,  while문에서는

아래의 다른 while문들과는 다르게, '(' 연산자가 나오면 멈춰야하는  != '('  가 있는데 왜, 위에 쓴 while문에는 없는지 모르겠습니다.

똑같이  != '('  를 입력해줬는데 돌아가긴 하더라구요. 혹시 넣어도 되는 부분인지, 아니면 넣어주면 안되는지 궁금합니다 ㅠㅠㅠ

 

인프런 해당 강의에 위같은 질문이 있었는데, 고민해봤지만 확실한 답을 내리지 못하겠다. 이 글 복습할 때 다시 찾아보는 것도 좋을 듯!

 

+) 나만의 코드를 다시 작성해보는 것도 좋겠다. 결국 이 문제는 연산자의 우선순위만 제대로 고려하면 풀 수 있는 문제인데, 이를 스택과 결부지어서 어떻게 넣고 어떻게 뺄 것인지를 코드로 구현하는 방식은 여러 가지 방식이 있을 것이다.

---

4. 후위식 연산(스택)

바로 전에 3번을 풀어서 그런지 거꾸로 생각하는 것은 쉬웠다.

연산자가 나오면 그 앞의 두 숫자를 가지고 연산을 진행하고, 연산 결과 값을 다시 스택에 넣으면 된다.

주의해야할 점이 있다면, 스택에서 pop하면 나중에 들어간 숫자부터 나오기 때문에 연산 순서를 유의해야 한다.

 

가볍게 success~!

a = input()
stack = []

for x in a:
    if x.isdecimal():
        stack.append(x)
    else:
        a = int(stack.pop())
        b = int(stack.pop())
        if x == '+':
            stack.append(b+a)
        elif x == '-':
            stack.append(b-a)
        elif x == '*':
            stack.append(b*a)
        elif x == '/':
            stack.append(b/a)
            
print(stack[0])

---

큐(Queue)

· FIFO: First In First Out, 먼저 들어간 게 먼저 나온다.

· 스택과 자료가 나오는 순서가 다르다.

· 파이썬에서는 큐라는 구조를 deque라는 자료구조를 통해 사용할 수 있다.

· deque의 append, popleft 함수 사용.

 

5. 공주 구하기(큐)

문제에는 원형으로 왕자들이 앉아있지만, 이를 큐 형태로 재해석하면 다음과 같다.

 

1 2 3 4 5 6 7 8 → 1번 왕자는 1을 외치고 맨 뒤로 간다. (popleft() 후 append())

2 3 4 5 6 7 8 1 → 2번 왕자는 2를 외치고 맨 뒤로 간다.

3 4 5 6 7 8 1 2 → 3번 왕자는 3을 외치게 되므로 큐에서 삭제한다. (popleft())

4 5 6 7 8 1 2 → 4번 왕자는 1을 외치고 맨 뒤로 간다.

5 6 7 8 1 2 4 → 5번 왕자는 2를 외치고 맨 뒤로 간다.

.

.

.

7

 

이렇게 3을 외치는 사람을 차례대로 왕자가 한 명만 남을 때까지 큐에서 삭제해나가면 된다.

 

내가 짠 코드는 다음과 같다.

from collections import deque

n, k = map(int, input().split())
dq = list(range(1, n+1))
dq = deque(dq)
cnt = 0

while len(dq) != 1:
    cnt += 1
    if cnt == k:
        dq.popleft()
        cnt = 0
    else:
        dq.append(dq.popleft())

print(dq[0])

 

강사님 코드는 다음과 같은데, 이중 for문 도는 것보다는 while문 한 번 도는게 더 낫지 않나 싶다. 전체 횟수는 똑같을 것 같기도 하고..

from collections import deque
n, k = map(int, input().split())
dq = list(range(1, n+1))
dq = deque(dq)

while dq:
    for _ in range(k-1):
        cur = dq.popleft()
        dq.append(cur)
    dq.popleft()
    if len(dq) == 1:
        print(dq[0])
        dq.popleft()  # break해도 되지만, 답을 출력하고 마저 pop해버리면 어차피 while문 조건 불만족해서 반복문 끝

---

6. 응급실(큐)

단계별로 입력예제 1을 보자. 

 

60[0] 50[1] 70[2] 80[3] 90[4] → 0번째 환자보다 위험도가 높은 환자가 뒤에 있으므로 0번째 환자는 맨 뒤로 간다. (popleft(), append())

50[1] 70[2] 80[3] 90[4] 60[0] → 맨 뒤로 간다.

 

대충 과정을 생각해보면 위 5번 문제와 다를게 없다. 다만 M번째 환자를 어떻게 추적할 것인지가 문제라고 생각했는데, M번째 환자의 위험도를 미리 저장해두고, 해당 위험도가 pop되면 멈추면 될 것 같다. (그래서 문제 조건에서도 M이 0부터 시작하는 걸지도?)

 

근데 위 생각은 틀렸다.. 왜냐면 위험도가 같은 환자들이 존재할 수 있기 때문에, 환자의 위험도만 가지고는 원하던 환자라는 것을 확신할 수 없다. 이렇게 잘못 생각하고 짠 코드이다. 채점했더니 60점이 나왔다.

from collections import deque

n, m = map(int, input().split())
dq = list(map(int, input().split()))
obj = dq[m]
cnt = 0
dq = deque(dq)

while True:
    for i in range(1, len(dq)):
        if dq[0] < dq[i]:
            cur = dq.popleft()
            dq.append(cur)
            break
    else:
        cur = dq.popleft()
        cnt += 1
        if cur == obj:
            print(cnt)
            break

** 그럼 그냥 정렬하고 풀면 되는 거 아닌가?

아니다. 이 또한 위험도가 중복일 수 있기 때문에 하면 안 되는 생각이다.

 

해답은 2중 리스트이다. (리스트 안에 튜플로 저장) 리스트에 (m, 위험도)를 차례대로 저장하면 되는 것이다.

dq = [(pos, val) for pos, val in enumerate(list(map(int, input().split())))]
# [(0, 60), (1, 60), (2, 90), (3, 60), (4, 60), (5, 60)]

 

답안 코드는 다음과 같다.

from collections import deque

n, m = map(int, input().split())
dq = [(pos, val) for pos, val in enumerate(list(map(int, input().split())))]
dq = deque(dq)
cnt = 0

while True:
    cur = dq.popleft()  # cur: current
    if any(cur[1] < x[1] for x in dq):  # cur[1] < x[1]이 하나라도 참이면 if문 참
        dq.append(cur)
    else:
        cnt += 1
        if cur[0] == m:
            print(cnt)
            break

맨 앞의 환자의 위험도를 나머지 환자들의 위험도와 비교할 때 나는 for문을 사용했는데, any()라는 함수를 써서 그 안에서 for문을 돌리니 구조가 훨씬 간결해졌다. 코드를 어떻게 하면 더 보기 좋게, 편하게 짤 수 있는지 이렇게 문제를 많이 풀어보면서 다양한 함수를 알아두는 게 좋을 것 같다.

 

* for문을 돌지 않더라도, 리스트를 하나 더 만들어서 dq[1:-1]까지 넣은 다음에, 그들 중 최댓값하고만 비교해도 될 것 같다는 생각이 들었다.

---

7. 교육과정 설계(큐)

정답 코드는 다음과 같다. (조금 고민해보다가 너무 졸려서.. 그냥 강의 들어버림)

from collections import deque

need = input()
n = int(input())

for i in range(n):
    plan = input()
    dq = deque(need)
    for x in plan:
        if x in dq:  # 먼저 필수과목 여부 확인
            if x != dq.popleft():
                print("#%d NO" % (i+1))
                break
    else:
        if len(dq) == 0:  # 필수과목이 전부 포함되어 있는지 확인
            print("#%d YES" % (i+1))
        else:
            print("#%d NO" % (i+1))

코드를 읽어보면 대충 어떻게 풀었는지 이해가 갈 것이다.

 

사실 나는 강사님 코드를 따라서 타이핑해보다가, 필수과목을 중복으로 듣는 경우는 따로 고려해야되는 거 아닌가? 라고 생각했었는데, 어차피 한번 들었으면 pop해서 dq에서 삭제되기 때문에 중복으로 듣는 과목이 있어도 for x in plan: 이 for문에서 거짓이 되어버린다. 그래서 신경쓸 필요가 없었던 것이다.

 

---

8. 단어 찾기(해쉬)

이건 그냥 쉬운 문제인데..?

n = int(input())
note = []
for _ in range(n):
    note.append(input())
poem = []
for _ in range(n-1):
    poem.append(input())

for i in range(n):
    if note[i] not in poem:
        print(note[i])
        break

 

'해쉬'라는 특성 상 딕셔너리를 쓰신 강사님 코드는 아래와 같다.

n = int(input())
p = dict()  # 딕셔너리 만들기

for _ in range(n):
    word = input()
    p[word] = 1

for _ in range(n-1):
    word = input()
    p[word] = 0

for key, val in p.items():
    if val == 1:
        print(key)
        break

---

9. Anagram(아나그램: 구글 인터뷰 문제) (딕셔너리 해쉬)

내 코드. 이건 뭐.. 별 생각 없이도 풀 수 있는 문제.

word1 = input()
word2 = input()
dic = dict()

for i in word1:
    if i in dic:
        dic[i] += 1
    else:
        dic[i] = 1

for i in word2:
    if i in dic:
        dic[i] -= 1
    else:
        dic[i] = -1

for key, val in dic.items():
    if val != 0:
        print("NO")
        break
else:
    print("YES")

 

word1 = input()
word2 = input()
dic1 = dict()
dic2 = dict()

for x in word1:
    dic1[x] = dic1.get(x, 0) + 1

for x in word2:
    dic2[x] = dic2.get(x, 0) + 1

for i in dic1.keys():
    if i in dic2.keys():
        if dic1[i] != dic2[i]:
            print("NO")
            break
    else:
        print("NO")
        break
else:
    print("YES")

위 코드가 강사님 코드이다. 딕셔너리의 get 메소드를 알게 되었다.

dic1.get(x, 0) → 키가 x인 값이 있으면 그 값을 리턴하고, 키 x가 없으면 0을 리턴한다.

 

+) 이 강의 뒤에 바로 이 코드를 개선한 코드 강의가 있는데, 더하고 빼는 과정이 내가 짰던 코드와 비슷한 방식이다.

a = input()
b = input()
sH = dict()

for x in a:
    sH[x] = sH.get(x, 0) + 1

for x in a:
    sH[x] = sH.get(x, 0) - 1

for x in a:
    if sH.get(x) > 0:
        print("NO")
        break
else:
    print("YES")

---

10. 최소힙

· 최소힙은 완전이진트리로 구현된 자료구조

· 부모 노드값이 자식(들)의 노드값보다 작게 구성됨

 

* 숫자가 입력될 때마다 최소힙의 형태를 만든다고 생각하자.

 

→ 정리하기 힘드니까 그냥 강의 찾아봐... (처음 배우는 자료구조라서 그럼)

 

galid1.tistory.com/485

자료구조 - 힙(Heap)이란?

코드 자체는 정말 쉽다. 근데 위 링크에 백준 문제가 있는데, 그 문제는 아예 힙을 새로 만드는 코드이기에 살짝 복잡한데, 공부해보면 좋을 것 같다.

import heapq as hq

a = []  # 리스트에 자료를 push, pop함. heapq를 이용하면 이 리스트를 힙처럼 사용 가능.

while True:
    n = int(input())
    if n == -1:
        break
    if n == 0:
        if len(a) == 0:
            print(-1)
        else:
            print(hq.heappop(a))  # 루트 노드값 pop한 후 출력
    else:
        hq.heappush(a, n)

---

11. 최대힙

· 힙은 기본적으로 최소힙으로 동작한다. 최소힙이 default.

· 최대힙은 약간의 응용이 필요할 뿐. → 입력할 때 부호를 반대로 바꿔서 입력.

import heapq as hq

a = []

while True:
    n = int(input())
    if n == -1:
        break
    if n == 0:
        if len(a) == 0:
            print(-1)
        else:
            print(-hq.heappop(a))
    else:
        hq.heappush(a, -n)