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])