Algorithm TIL (240909)

> [백준] 괄호의 값

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

🔥다시 보기🔥

 

문제 풀이 과정

• 스택 활용
• 괄호로 이루어진 문자열이 주어질 때, 각 괄호에 따라 괄호값을 구해야 한다. ()의 쌍일 때는 값이 2, []의 쌍일 때는 값이 3이라는 간단한 규칙같으나, (x)로 해당 괄호쌍 안에 또다른 괄호값이 있을 경우 값이 2x이 된다. 
• 이는 괄호가 (()) 괄호값이 곱해지는 형태, ()[] 괄호값이 더해지는 형태 2가지로 연산이 나뉘게 된다. 
• 문제에서 주어진 '(()[[]])([])' 문자열은 크게 두가지로 나눌 수 있다. (()[[]]) 과 ([]) 이다. (()[[]]) 는 2 x (2 + 3 * 3) 이고,  ([]) 는 2 * 3 이다. 쟁점은 저 괄호를 어떻게 구현해야 하는가로 보인다. 여기서 수학 개념 중 하나인 곱셈의 분배법칙을 생각해보면 된다.
• 2 x (2 + 3 * 3) 는 2 * 2 + 2 * 3 * 3 으로 나눌 수 있다. 그래서 열린 괄호를 마주할 때마다 스택에 괄호를 넣고 결과값에 2 혹은 3을 곱해주면 되겠다는 아이디어는 쉽게 떠올릴 수 있을 것이다. 여기서 중요한 점은 닫는 괄호를 만났을 때, 바로 직전에 문자가 한쌍을 이루는 열린 괄호인 경우에 괄호의 가장 내부에 있는 괄호쌍이므로 answer 에 괄호값을 더합니다. 그리고 닫는 괄호를 만날 때마다 괄호를 탈출한 것이므로 해당 괄호의 괄호값을 나눠줍니다. (중요한 아이디어, 계산이 끝난 괄호값을 제거한다!)
• 이러한 과정들을 코드로 나열하면 값을 출력할 수 있습니다.

 

문제 풀이

python

s = list(input())
stack = []

num = 0
temp = 1
for i in range(len(s)) :
    if s[i] == '(' :
        stack.append(s[i])
        temp *= 2
    elif s[i] == '[' :
        stack.append(s[i])
        temp *= 3
    elif s[i] == ')' :
        if not stack or stack[-1] == '[' : # 스택의 마지막 값이랑 쌍이 맞지 않다면 올바르지 못하므로 0을 리턴
            num = 0
            break
        if s[i-1] == '(' :
            num += temp
        stack.pop()
        temp //= 2 # 곱셈 분배법칙에 따라 닫힌괄호를 만나면, 계산이 끝난 괄호쌍 값을 제거하는 것
    else :
        if not stack or stack[-1] == '(' :
            num = 0 
            break
        if s[i-1] == '[' :
            num += temp
        stack.pop()
        temp //= 3

if stack :
    print(0)
else :
    print(num)

 

오늘의 회고 및 느낀점

스택과 괄호값... 곱셈의 분배법칙을 위해 닫힌 괄호를 만나면 해당 괄호값을 나누어주는 것... 메모!

 

---

> [백준] 정보 상인 호석

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

🔥다시 보기🔥

 

 

문제 풀이 과정

• 우선순위 큐 ( 최대 힙 )
• 처음 틀렸던 이유 :  고릴라의 정보가 주어지는 입력 값에서 개수, k를 정보의 가치로 두고 풀었다. 입력 값을 자세히 보고 문제를 파악하자. 이것 때문에 꽤나 시간을 허비했다ㅠ
• 이 문제는 고릴라들이 제공하는 정보가 주어질 때, 해당 이름의 고릴라 정보를 우선순위 큐로 설정하고 가치가 큰 순으로 정렬하면 된다. 그리고 호석이가 정보를 구매할 때, 구매한 정보들을 pop하면 된다.

 

문제 풀이

python

# 문제 해설
# 1 name k 숫자들 : 이름이 name인 고릴라가 k개의 정보를 순차적으로 C1~Ck 얻었다.
# 2 name b : name 고릴라에게 b개의 정보를 가치가 가장 비싼 순으로 구매한다. b개 이하로 정보를 갖고 있는 경우 모두 산다.
#   단, 한번 거래한 정보는 파기한다. (=pop)

# 문제 접근 과정
# 1. Q가 1로 시작할 떄, 고릴라의 이름으로 정보를 저장한다. (key-value 형태의 딕셔너리 사용)
# 1-1. k개의 정보를 최대 힙으로 저장하기 위해 heapq라이브러리를 사용하여 -를 추가하여 저장한다.
# 2. Q가 2로 시작할 때, 해당 이름의 고릴라로부터 가장 비싼 정보를 pop하여 가져온다. 가치는 저장할 때 -를 추가했기 때문에 추출할 때도 -를 추가하여 계산한다.
# 3. ans에 pop한 정보 값을 더한다.

from collections import *
import heapq
q = int(input())

ans = 0
gorillas = {} # {name:[C1 ~ Ck 개의 정보]}
for i in range(q) :
    gorilla = input().split()
    if gorilla[0] == '1' :
        heap = []
        for i in gorilla[3:] :
            heapq.heappush(heap, -int(i))
        gorillas[gorilla[1]] = gorillas.get(gorilla[1], []) + heap
        heapq.heapify(gorillas[gorilla[1]])
        
    elif gorilla[0] == '2' and gorilla[1] in gorillas.keys() :
        li = gorillas[gorilla[1]]
        for i in range(int(gorilla[2])) :
            if li :
                temp = heapq.heappop(li)
                ans += (-temp)
print(ans)

 

오늘의 회고 및 느낀점

파이썬의 우선순위 큐 라이브러리 heapq는 기본 최소 힙이다. 최대 힙으로 구현하기 위해선 넣는 원소에 -를 붙여서 넣고 pop할 때도 -를 붙여서 뽑아낸다.

그리고 코드를 좀 더 깔끔하고 가독성이 좋게 작성하는 방법을 고민해보자!

 

---

> [백준] 종점

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

🔥다시 보기🔥

 

 

문제 풀이 과정

• 우선순위 큐
• 우선 버스가 들어오고 나가는 시간을 비교하기 위해 우선순위 큐를 사용해 정렬하는 것까지 생각했다. 하지만 그 다음 스텝이 막막하여 다른 코드를 참고했다.

 

• 버스 시간 문자열의 자리 수만큼 주어졌을 때, 들어오는 시간과 나가는 시간을 하나의 수로 표현한다. 비교할 수 있도록 문자열의 자리수대로 계산 ( ex. 06:30:00.000 -> 063000000 )
• 버스 들어오는 시간 기준 정렬
• 가장 빠른 버스 시간을 (나가는 시간, 들어오는 시간) 형태로 하여 heap에 넣는다. 그리고 다음 i번째 버스부터 n개의 버스의 시간표를 확인하면서 다음 i번째 버스의 들어오는 시간이 가장빠른 버스의 나가는 시간보다 빠르다면, 종점에 버스 공간이 하나 더 필요하므로 + 1 해준다. 그리고 heap에는 가장 빠른 버스와 i번째 버스를 (나가는 시간, 들어오는 시간) 형태로 다시 넣는다. (= 버스가 아직 나가지 않았음)
• 위의 경우가 아니라면 i번째 버스만 넣는다.

 

문제 풀이

python

# 문제 해설 및 출력
# 종점에 버스정비를 위해 필요한 최소 공간을 리턴하자. 최소 공간은 종점에 버스가 같은 시간대에 있는 최대 개수이다.

# 접근 과정
# 버스가 들어오는 시각 ~ 나가는 시각이 겹치는 버스의 개수만큼 공간이 필요하다. 그렇다면 버스가 종점에 있는 시간대 중 
# 겹치는 개수를 세어주면 된다. 시간이 겹친다 = 시각이 갇고 

import heapq
n = int(input())
buses = []
for _ in range(n) :
    bIn, bOut = input().split()
    
    # 버스 들어오고 나가는 시간 12자리 문자열의 자리수 만큼 곱해서 1자리 수로 만든다.
    bInTime = int(bIn[9:]) + int(bIn[6:8]) * 1000 + int(bIn[3:5]) * 100000 + int(bIn[0:2]) * 10000000
    bOutTime = int(bOut[9:]) + int(bOut[6:8]) * 1000 + int(bOut[3:5])  * 100000 + int(bOut[0:2]) * 10000000
    buses.append((bInTime, bOutTime))

buses.sort() # 출발 시각이 빠른 순서대로 정렬

q = [] # 버스 시간표 우선순위에 담을 배열
heapq.heappush(q, (buses[0][1], buses[0][0])) # 첫번째 버스의 나가는 시간을 기준으로 비교할 것이기 때문에 
bus_cnt_inTime = 1

for i in range(1, n) :
    outTime = heapq.heappop(q) # 현재 가장 빨리 나가는 버스를 꺼낸다.
    if buses[i][0] < outTime[0] : # 그 다음 버스의 들어오는 시간이, 이전 버스의 나가는 시간보다 빨리 들어오면
        bus_cnt_inTime += 1 # 종점에 해당 버스도 함께 있어야 하므로 종점 공간 + 1
        heapq.heappush(q, outTime) # 가장 빨리 나가는 버스가 아직 안나갔으므로 넣어준다.
        heapq.heappush(q, (buses[i][1], buses[i][0])) # 그 다음 버스를 넣는다.
    else :
        heapq.heappush(q, (buses[i][1], buses[i][0])) # 그 다음 버스를 넣는다.

print(bus_cnt_inTime)

 

오늘의 회고 및 느낀점

• 시간을 비교할 때, 시,분,초를 계산할 수도 있지만, 비교하는 시간의 형태가 모두 동일하다면 문자열의 길이만큼의 수로 변환하는 것도 하나의 방법이다. ( ex. 06:30:00.000 -> 063000000 )
• 버스가 들어오는 시간 ~ 나가는 시간이 겹치는지를 알 수 있는 것은 가장빠른 버스를 heap에 미리 넣고 가장 빠른 버스의 들어오는 시간과 그 다음 i번째 버스의 나가는 시간을 비교해보자.