2023년 7월 28일 알고리즘 문제풀이
백준 1655번
1차 시도
나의 생각
양 끝과 중간이라는 생각에 deque을 사용하면 어떨까 생각하고 코드를 작성했다. 생각해보니 중간과 끝 사이에 새로운 숫자를 집어넣어야 하는데… 다행히 우선순위 큐, 최소 heap이 생각났지만 너무 늦게 생각나서 코드 작성을 못했다. 다음 시도에선 해봐야지.
결과
오답
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import sys
from heapq import heappop, heappush, heappushpop
n = int(sys.stdin.readline())
big = []
mid = []
small = []
for _ in range(n):
num = int(sys.stdin.readline())
if not mid:
mid.append(num)
print(num)
continue
if num >= mid:
tmp = heappushpop(big,num)
mid.append(tmp)
print(mid[0])
else:
tmp = heappushpop(small,-num)
mid.append(-tmp)
mid.sort()
print(mid[0])
2차 시도
나의 생각
heap을 사용하였다. 가운데 값을 기준으로 크냐 작냐에 따라 경우가 나눠질거라고 생각해서 가운뎃값보다 작은 heap, 가운뎃값을 담은 heap, 더 큰 heap 세개로 나누어서 생각했다. 하지만 문제에서 나왔듯 가운데 값이 전체 숫자의 갯수에 따라 2개일 수도 한 개 일수도 있어서 가운데를 담는 배열을 1로 유지해야할지, 혹은 큰 배열과 작은 배열의 수를 갖게 유지해야할 지 여러모로 헷갈렸다. 차라리 하나를 우직하게 했으면 정답은 나왔으려나.. 여러 생각에 헤메다가 시간만 허비하고 코드를 완성하지 못했다.
결과
오답
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import sys
from heapq import heappop, heappush, heappushpop
n = int(sys.stdin.readline())
large = []
mid = []
small = []
for _ in range(n):
num = int(sys.stdin.readline())
if not mid :
heappush(mid,num)
print(num)
continue
if len(mid) == 2:
min_val = min(mid)
if num >= min_val:
tmp = heappushpop(large,num)
heappush(small,tmp)
tmp = heappop(mid)
heappush(large,mid[0])
mid[0] = tmp
else:
heappush(mid,num)
3차 시도
나의 생각
우선 처음 3개의 숫자는 따로 조건을 작성하였다. 그리고 2차 시도에서 고민하던 문제는 항상 가운뎃값을 담는 배열을 1개로 유지하기로 하였다. 코드를 작성하다보니 large와 small이라는 배열은 같거나, large가 1만큼 크기가 더 큰 경우 밖에 없다는 것을 깨달았다. 내가 가운뎃값의 배열을 1개만 담기로 설정해놨기 때문에 전체 숫자의 갯수가 홀수면 두 배열의 길이는 같을 것이고, 짝수라면 가운뎃값 후보 2개 중 작은 값이 가운뎃 값을 위한 배열에 들어가고 남은 값은 더 크기 때문에large배열에 들어가야하면서 생긴 규칙이다. 이를 바탕으로 다양하게 조건을 나누었지만 어디가 문제인지 indexerror와 typeerror가 발생하여 오답처리 되었다. 내가 생각해도 코드가 너무 복잡하고 더럽다.
결과
오답
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
import sys
from heapq import heappop, heappush, heappushpop
n = int(sys.stdin.readline())
large = [] # 가운뎃값보다 큰 배열
mid = [] # 가운뎃값 담는 배열
small = [] # 가운덱값보다 작은 배열, 최소힙이기 때문에 음수로 바꿔서 넣고 뺄 예정
cnt = 0 # 초반 3개를 위한 설정
for _ in range(n):
cnt += 1 # 입력한 숫자 체크
num = int(sys.stdin.readline())
if cnt == 1: # 처음 들어온 숫자는 무조건 출력
heappush(mid,num) # 1개뿐일땐 가운데
print(num)
elif cnt == 2: # 두번째로 들어올때는 둘 중 작은 수
tmp = heappushpop(mid,num) # 두 숫자 모두 mid에 들어있음
print(tmp)
heappush(large,heappop(mid)) # 두 숫자 중 큰 것은 large로 옮김
heappush(mid,tmp) # 작은 것은 mid에 둔다.
# 현재 mid에 한 개, large에 1개 들어있는 상태. 이제부턴 일반화 가능하므로 cnt는 신경안씀
else:
if len(large) == len(small): # 두 배열의 크기가 같다면 mid에는 1개뿐이므로 다음에 수가 들어오면 가운데값이 2개가 된다.
if mid[0] > num: # 현재 가운뎃값보다 작은 값이 들어오면?
num *= -1
tmp = heappush(small,num) # 음수로 변환해 small에 넣은 후 pop하여 최대힙을 찾는다.
tmp *= -1
tmp = heappushpop(mid,tmp) # 찾은 최대힙을 mid에 넣고 최소힙을 찾는다.
print(tmp) # 가운데 값중 작은 수를 출력해야하니 그대로 출력
heappush(large,heappop(mid)) # mid에 남은 수는 큰 수 이므로 large로 넣는다.
heappush(mid,tmp) # 아까 뺀 가운데 값을 다시 넣어준다.
# 이 상황에서는 mid의 길이는 1이고 large의 길이가 small보다 1 더 길다.
else: # 가운뎃값보다 큰 값이 들어왔다.
tmp = heappush(large,num) # large배열에 넣는다.
tmp = heappop(mid) # 어차피 large배열에서 최소힙을 구해봤자 둘 중 더 작은 현재 mid의 원소를 출력해야하므로 굳이 꺼내지 않는다.
print(tmp) # 가운뎃값 중 작은 수를 출력
heappush(mid,tmp)
else: # large와 small이 같지 않을 때는 항상 large가 더 크다. 가운데 값 둘 중 작은 수를 출력하고 큰 수는 large에 넣도록 로직이 되있으므로.
if mid[0] > num: # 현재 가운뎃값보다 더 작은 수가 들어옴
num *= -1 # 음수로 변환
heappush(small,num) # 가운뎃값은 하나므로 배열의 길이가 1 작은 small 에 넣고 현재 가운뎃값 그대로 다시 출력하면된다.
tmp = heappop(mid)
print(tmp)
heappush(mid,tmp)
else: # 현재 가운뎃값보다 더 큰 수가 들어옴
tmp = heappop(mid) # 현재 가운뎃값은 음수로 변환해 small배열에 넣는다.
tmp *= -1
heappush(small,tmp)
tmp = heappushpop(large,num) # 새로 들어온 수를 large 배열에 넣고 최소힙을 구한다.
heappush(mid,tmp) # 구한 최소 heap을 새로운 가운뎃값으로 설정
print(tmp)
4차 시도
나의 생각
코드가 더러워진 가장 큰 문제는 heap의 최솟값을 출력할때 heappop으로 찾아내어 출력하고 다시 heappush로 넣어줬기 때문이다.
혼자 테스트해본 결과 내가 만든 배열에 `heappop`,`heappush`를 사용해서 배열을 수정해주면 0번 index가 항상 최솟값을 나타낸다!
이걸 모르고 heappop,heappush를 해댔으니 코드가 더러워질 수밖에.. 기존의 로직은 유지한채 코드만 잘 정리했더니 훨씬 깔끔해졌고 바로 정답이였다. 참고로 최솟값이 튀어나오기 때문에 최댓값을 내야하는 small 배열은 넣고 뺄 때 음수로 변환해주었다.
결과
정답
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import sys
from heapq import heappop, heappush, heappushpop
n = int(sys.stdin.readline())
large = []
small = []
for _ in range(n):
num = int(sys.stdin.readline())
if not large and not small:
print(num)
heappush(large,num)
elif len(large) == len(small):
if -small[0] < num:
heappush(large,num)
print(large[0])
else:
tmp = heappushpop(small,-num)
heappush(large,-tmp)
print(large[0])
else:
if num >= large[0]:
tmp = heappop(large)
heappush(small,-tmp)
heappush(large,num)
print(-small[0])
else:
heappush(small,-num)
print(-small[0])
