📌오늘의 TIL
오늘은 특히 문제의 답을 찾기보다
"내가 접근한 방법이 왜 문제였을까?"를 깊게 파보았다.
나의 접근법과 무엇이 잘못 되었는지 회고록이 되겠다.
(모든 문제는 백준에서 푼 문제다.)
1.패션왕 신해빈
"""
31120kb 60ms
0. ✅point : 가짓 수를 구하는 계산식
1. n번 실행되는 for문에서 옷이 종류별로 얼마나 있는지 clothes(dict)에 추가
2. 각 종류별로 조합을 하기 위해선 곱하면 가짓 수를 알 수 있음.
3. 따라서 for문으로 clothes의 value 값들을 뽑아서 결과값에 곱함. (곱셈을 위해서 결과값의 디폴트 값은 1)
4. 단, 안 입는 경우를 포함하기 위해서 각 종류별로 1을 포함하여 곱함.
5. 마지막에 모두 안 입는 경우를 제외하기 위해서 결과값에 1을 뺌.
"""
t = int(input())
for _ in range(t):
clothes = {}
n = int(input())
for _ in range(n):
name, kind = input().split()
if kind in clothes:
clothes[kind] += 1
else:
clothes[kind] = 1
result = 1
for count in clothes.values():
result *= count + 1
print(count, result)
result -= 1
print(result)
"""
📝behind (시간 초과)
맨 처음엔
위의 코드처럼 가짓 수를 구하는 방식으로 시작했으나
'종류가 겹칠 때 제외시키는 방법'을 구하지 못 하여
아래의 코드처럼
'직접 조합하여 갯수를 확인하는 방법'으로 접근했습니다.
하지만 시간 초과가 났고
결국 질문 게시판, 검색 등을 활용해서 풀었습니다.
"""
# from itertools import combinations
#
# t = int(input())
#
# for _ in range(t):
# n = int(input())
# clothes = {}
# for _ in range(n):
# name, kind = input().split()
# clothes[name] = kind
#
# items = list(clothes.keys())
# cnt = 0
# result = []
#
# for r in range(1, n + 1): # 부분집합의 크기를 1부터 아이템의 총 개수까지
# for subset in combinations(items, r): # 아이템들 중에서 r개를 선택하는 모든 조합
# if len(set(clothes[item] for item in subset)) == r: # 선택된 아이템들의 값이 모두 서로 다르면
# cnt += 1
#
# print(cnt)
2. N번째 큰 수
"""
33188kb 1860ms
0. ✅point : 가장 낮은 값 버리기
1. n번 실행되는 for문에서 입력된 줄의 값들을 하나씩 뽑음.
2. heap에 값들을 추가하나 heap의 길이가 n 이상 일때는 최솟값을 pop하여 버림.
(n번째 큰 수를 찾기 때문에 n+1번째인 최솟값은 필요 없음)
3. 다 돌면 [ 마지막 n번째로 큰 수 ] = [ heap에서 가장 작은 수 ] = [ heap의 최솟값 pop ] 을 출력
"""
from heapq import heappush, heappop
n = int(input())
heap = []
for _ in range(n):
for value in map(int, input().split()):
heappush(heap, value)
if len(heap) > n:
heappop(heap)
print(heappop(heap))
"""
📝behind (메모리 초과)
맨 처음엔
아래의 코드처럼
최댓값을 우선순위로 하는 heap으로 풀었습니다.
각 value에 마이너스를 붙여서
가장 큰 값을 가장 작은 값으로 만들어주고 heap에 추가한 후
다 돌면 n-1번만큼 pop하고 n번째 pop 다시 마이너스를 붙여서
출력하는 형식으로 풀었습니다.
하지만 메모리 초과가 났고
질문 게시판, 검색 등을 통해서 힌트를 얻고
위의 코드와 같이 수정했습니다.
"""
# from heapq import heappush, heappop
#
# n = int(input())
# heap = []
# for _ in range(n):
# for value in list(map(int, input().split())):
# heappush(heap, -value)
#
# for _ in range(n-1):
# heappop(heap)
#
# print(heappop(heap)*-1)
3. 카드 합체 놀이
"""
33188kb 56ms
0. ✅point : heap까지 포함해서 시간 복잡도 계산하기 (데이터 넣고 꺼낼 때마다 O(log N))
1. 모든 값을 heap에 추가.
2. m 만큼 heap의 가장 작은 두 수를 더하여 해당 값을 heap에 두 번 추가. (= 문제 조건 1, 2)
3. heap의 총 합산을 출력
"""
from heapq import heappush, heappop
n, m = map(int, input().split())
heap = []
for value in list(map(int, input().split())):
heappush(heap, value)
for _ in range(m):
x = heappop(heap)
y = heappop(heap)
heappush(heap, (x + y))
heappush(heap, (x + y))
print(sum(heap))
"""
📝behind (시간 초과)
아래의 코드와 같이
index값까지 포함하여 a(list)에 넣고 다시 덮는 방식으로
접근했으나 시간 초과가 났고
문제에서 카드의 위치나 순서를 체크하는 조건은 없었으므로
애초에 a(list)는 필요가 없었다.
'아래의 코드가 왜 시간 초과가 날까?'를 고민해보았을 때
처음엔 이중 for문으로 m * n = 15,000 * 1,000 = 15,000,000 이므로
시간제한 1초(대략 1억 연산) 기준으로 초과가 안 된다고 생각했다.
그러나 heap의 시간 복잡도까지 포함해야 한다.
아래 짠 코드의 정확한 식은
15,000 * ( log 1000 + ( 1,000 * log 1000) ) 이고
최고차항만 남기면 15,000 * (1000 * log 1000) 이다.
log 1000 = 대략 10 이므로
15,000 * 10,000 = 150,000,000 = 1억 5천
이면 시간초과가 난다.
다음엔 꼭 사용하는 함수까지 시간 복잡도를 잘 계산하자!
"""
# from heapq import heappush, heappop
#
# n, m = map(int, input().split())
# a = list(map(int, input().split()))
#
#
# for _ in range(m):
# heap = []
# for i in range(n):
# heappush(heap, (a[i], i))
#
# x, x_index = heappop(heap)
# y, y_index = heappop(heap)
# a[x_index] = (x+y)
# a[y_index] = (x+y)
#
#
# print(sum(a))
4. 절댓값힙
"""
39824kb 140ms
0. ✅point : 시간 초과가 난다면 input 체크하기
1. n번의 for문에서 heap에 (절대값, 원본값) 을 튜플로 넣음.
2. 단, 값이 0 이라면 출력 하라는 의미이므로 heap을 pop 하여 출력. 그러나 heap이 비어있다면 0 출력.
"""
from heapq import heappush, heappop
import sys
input = sys.stdin.readline
n = int(input())
heap = []
for i in range(n):
x = int(input())
if x == 0:
if heap:
_, value = heappop(heap)
print(value)
else:
print(0)
continue
heappush(heap, (abs(x), x))
"""
📝behind (시간 초과)
이것도 처음엔 시간 초과가 났으나 input만 바꿔줬는데 통과했다.
이제는 sys.stdin.readline 써서 입력을 받아야겠다.
"""항해99 취업 리부트 코스를 수강하고 작성한 콘텐츠 입니다.
