구름톤 챌린지 3주 day14 학습 일기

바지 겟

 

방문할 수 있으면서, 번호가 가장 작은 노드를 방문하는 부분에서 

두가지 방법으로 풀이를 해보았다.

1. child 노드를 배열로 다 받은 뒤, parent 노드를 순회하면서 child 노드 배열을 sort()

2. child노드 배열을 heapq(최소힙)으로 구성

 

실행 시간에 미세한 차이가 있기는 했다.

그리고 최소힙에서 pop을 할 때, indent를 너무 들여쓰지 않기 위해 (어제 배운) 코드를 작성했는데

하지만 추가된 코드로 인해 코드가 길어진 측면이 있다.

 

힙을 사용하지 않고 sort() 후에, 반복문으로 조건에 맞는지 확인하는 방법이 코드를 작성하거나 읽는데는 좋은것 같긴 한데

만약 정렬에 소요되는 시간도 줄여야 한다면 힙을 사용 할 수도 있을 것 같다.

 

다만 파이썬 heapq를 사용하며 주의해야 할 부분이 있다.

heapq인 q 배열은 heapq.heappop(q) 하면, 가장 작은 값부터 pop한다.

하지만,

리스트 자체가 가장 작은 수부터 오름차순으로 정렬된 결과를 보여주는 것은 아니다.

그래서

for문을 순회할 때, heapq가 최소힙으로 구성되어 있으니 가장 작은 값부터 접근한다고 생각하면 틀릴 수 있다.

numbers = [3, 1, 4, 2, 6, 5, 3, 5]
queue = []
for num in numbers:
    heapq.heappush(queue, num)
    print(num,queue)

# 출력 결과
#3 [3]
#1 [1, 3]
#4 [1, 3, 4]
#2 [1, 2, 4, 3]
#6 [1, 2, 4, 3, 6]
#5 [1, 2, 4, 3, 6, 5]
#3 [1, 2, 3, 3, 6, 5, 4]
#5 [1, 2, 3, 3, 6, 5, 4, 5]

for queueNum in queue:
    print(queueNum)

# 출력 결과
#1
#2
#3
#3
#6
#5
#4
#5

for _ in numbers:
    popped=heapq.heappop(queue)
    print(popped,queue)

# 출력 결과
#1 [2, 3, 3, 5, 6, 5, 4]
#2 [3, 3, 4, 5, 6, 5]
#3 [3, 5, 4, 5, 6]
#3 [4, 5, 6, 5]
#4 [5, 5, 6]
#5 [5, 6]
#5 [6]
#6 []

 

오늘의 학습일기 끝