Algorithm TIL 240926

1️⃣ [백준] 센티와 마법의 뿅망치 (19638)

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

 

 

문제 해결 과정

• '매번 키가 가장 큰 거인의 키를 절반으로 줄인다' 를 확인하고 우선순위큐의 최대힙 자료구조를 이용하면 되겠구나 생각
• python은 heapq 라이브러리를 제공하여 사용
• heapq는 최소힙으로 구현되어 있음. 최대힙 구현하는 경우 원소값을 음수로 하여 넣고 추출할 때 양수로 변환

틀린 풀이와 과정

import heapq
import sys
input = sys.stdin.readline

# 센티보다 거인의 모든 키를 작게할 수 있는지 여부
def solution(N,H,T,giants) :
    cnt = 0 # 센티 뿅망치 사용 횟수
    
    # 뽕망치 횟수만큼 돌린다.
    for _ in range(T) :
        # 가장 큰 거인을 뽑는다.
        big = -heapq.heappop(giants)
        
        magic = big // 2
        cnt += 1 # 뿅망치 사용횟수 1 증가
    
        # 우선순위큐에 다시 넣는다.
        if magic > 0 :
            heapq.heappush(giants, -magic)
        else : 
            heapq.heappush(giants, -big)
        
        # 우선순위큐의 최대값이 센티의 키보다 작다면 반복문 멈춤
        if big < H : break
        
    bigG = -heapq.heappop(giants)

    print('YES' if bigG < H else 'NO')
    print(cnt if bigG < H else bigG)

N, H, T = map(int, input().split()) # 거인의나라 인구수, 센티의 키, 뿅망치 사용횟수
giants = [] # 최대 힙
for _ in range(N) :
    heapq.heappush(giants, -int(input())) 

solution(N,H,T,giants)

• 이유
  • 뿅망치로 가장 큰 거인의 키를 줄이는 반복문을 돌릴 때, 만약 가장 큰 거인의 키가 센티의 기보다 작다면 (big < H) 뿅망치 사용횟수인 cnt를 증가시킬 필요가 없음.
  • 그래서 반복문을 멈추는 코드를 cnt를 1 증가하는 코드보다 아래에 적어 모든 거인의 키가 센티의 키보다 작은 경우에 cnt 값이 잘못 계산되었다고 생각
  • 그래서 아예 모든 거인의 키가 센티의 키보다 작다면 return 시켜 탈출하도록 수정하여 통과

최종 풀이

'''
센티와 마법의 뿅망치
https://www.acmicpc.net/problem/19638
[문제 접근]
- '매번 키가 가장 큰 거인의 키를 줄인다.' 에서 거인의 키를 우선순위큐에 넣고 최대힙으로 구현
- 뿅망치로 우선순위큐의 최대값을 반으로 줄여서 다시 넣음

[1트 실패 이유]
- 반복문이 끝나기 전에 매번 최대값을 센티의 키와 비교한 뒤 return하여 반복을 끝내야 한다.
- 나는 big < H 조건문 이전에 cnt 값을 1증가 시켜서 뿅망치 사용횟수가 맞지 않아 문제가 틀렸던 것!
- cnt 증가 로직을 big < H 조건문 이후로 옮기니 문제 맞음!
'''

import heapq
import sys
input = sys.stdin.readline

# 센티보다 거인의 모든 키를 작게할 수 있는지 여부
def solution(N,H,T,giants) :
    cnt = 0 # 센티 뿅망치 사용 횟수
    
    # 뽕망치 횟수만큼 돌린다.
    for _ in range(T) :
        # 가장 큰 거인을 뽑는다.
        big = -heapq.heappop(giants)
    
        # 우선순위큐의 최대값이 센티의 키보다 작다면 반복문 멈춤(뿅망치 최소 사용횟수이므로)
        if big < H : 
            print('YES')
            print(cnt)
            return
        
        magic = big // 2
        cnt += 1 # 뿅망치 사용횟수 1 증가
        
        # 우선순위큐에 다시 넣는다.
        if magic > 0 :
            heapq.heappush(giants, -magic)
        else : 
            heapq.heappush(giants, -big)
    
    # 뿅망치 사용횟수만큼 줄인 다음, 전체적으로 거인의 키 확인
    bigG = -heapq.heappop(giants)
    print('YES' if bigG < H else 'NO')
    print(cnt if bigG < H else bigG)

N, H, T = map(int, input().split()) # 거인의나라 인구수, 센티의 키, 뿅망치 사용횟수
giants = [] # 최대 힙
for _ in range(N) :
    heapq.heappush(giants, -int(input())) 

solution(N,H,T,giants)

 

느낀 점

• 조건문을 적절한 위치에 작성하는 것이 중요함을 깨달았다

 

---

 

2️⃣ [백준] 문제 추천 시스템 Version 1 (21939)

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

 

문제 풀이 과정

• N개의 문제, M개의 명령어가 주어진다.
• 각 명령어에 맞게 추천 문제 리스트를 출력, 추가, 제거한다
• 명령어가 recommend일 때, x에 따라 1이면 가장 어려운 문제 번호 출력, -1이면 가장 쉬운 문제 번호 출력한다. 때문에 문제 레벨별로 나열하기 위해 우선순위큐 최대힙, 최소힙으로 추천 문제 나열

틀린 코드와 이유

import heapq
minQuestions = []
maxQuestions = []
result = []

N = int(input()) # 문제 개수
for i in range(N) :
    P, L = map(int, input().split())
    heapq.heappush(minQuestions, (L, P))
    heapq.heappush(maxQuestions, (-L, P))
    
M = int(input()) # 명령어 개수
for i in range(M) :
    m = input().split()
    
    if m[0] == 'add' :
        P, L = map(int, m[1:])
        heapq.heappush(minQuestions, (L, P))
        heapq.heappush(maxQuestions, (-L, P))
    elif m[0] == 'recommend' :
        # 어려운 문제
        if int(m[1]) == 1 : 
            result.append(heapq.heappop(maxQuestions))
        # 쉬운 문제
        elif int(m[1]) == -1 : 
            result.append(heapq.heappop(minQuestions))
    elif m[0] == 'solved' :
        minQuestions = list(filter(lambda x : x[1] != int(m[1]), minQuestions))
        maxQuestions = list(filter(lambda x : x[1] != -int(m[1]), maxQuestions))
        
for r in result :  
    print(r[1])

• 명령어가 solved 가 주어진 경우, 각 최소힙, 최대힙을 filter 로 제거했지만 filter 메서드는 O(N) 시간복잡도를 가진다. 그래서 O(N*M) 의 최대 연산인 경우 N 은 최대 100,000, M은 최대 10,000 로 10억 이상이기 때문에 '시간 초과' 나옴
• 때문에 추천 문제가 있는지 여부를 확인하기 위해 딕셔너리 자료구조를 사용해 O(1)의 연산으로 처리할 수 있도록 수정했다.

문제 풀이

python

'''
문제 추천 시스템 Version 1 (21939)
골드4

[문제 접근]
- 결과 : recommend 명령어가 주어지면, 해당 명령에 맞는 문제 번호 출력
- x == 1 ) 문제 난이도가 가장 어려운 문제 번호 출력
- x == -1 ) 문제 난이도가 가장 쉬운 문제 번호 출력
- all_q : 전체 추천 문제 리스트 저장
'''
import heapq
import sys
input = sys.stdin.readline

min_q = []
max_q = []
all_q = {} # 전체 추천 문제 리스트
result = []

N = int(input()) # 문제 개수
for i in range(N) :
    P, L = map(int, input().split())
    heapq.heappush(min_q, (L, P))
    heapq.heappush(max_q, (-L, -P)) # 최대 힙, 문제가 여러 개라면 문제 번호가 큰 것으로 출력할 것이기 때문에 문제 번호도 적용!
    all_q[P] = L
    
M = int(input()) # 명령어 개수
for i in range(M) :
    m = input().split()
    
    if m[0] == 'add' :
        P, L = map(int, m[1:])
        heapq.heappush(min_q, (L, P))
        heapq.heappush(max_q, (-L, -P))
        all_q[P] = L
        
    elif m[0] == 'recommend' :
        x = int(m[1])
        # 어려운 문제
        if x == 1 :
            # ✨ 문제번호가 가장 큰 것
            while max_q :
                level, num = map(lambda x : -x, heapq.heappop(max_q))
                if num in all_q and all_q[num] == level :
                    heapq.heappush(max_q, (-level, -num))
                    result.append(num)
                    break
            
        # 쉬운 문제
        elif x == -1 : 
            while min_q :
                level, num = heapq.heappop(min_q)
                if num in all_q and all_q[num] == level :
                    heapq.heappush(min_q, (level, num))
                    result.append(num)
                    break
            
    elif m[0] == 'solved' :
        # ✨ 딕셔너리 사용해서 제거해보기
        P = int(m[1])
        if P in all_q :
            del all_q[P]
        
for r in result :       
    print(r)

 

느낀점

• 시간복잡도 1초를 초과하지 않으려면 O(N^2)의 시간복잡도 이하로 되도록 해야한다. 이 부분에서 딕셔너리를 사용한다는 아이디어를 생각해낼 수 있을 것 같다. 즉, N의 범위를 보고 O(1)의 시간복잡도로 처리할 수 있는 자료구조를 생각해야 한다!