[코드트리 챌린지] 마지막으로 남은숫자

뭔가 실력진단 날짜가 꼬였는데.. ;; 

3주차부터는 제대로 해봐야겠다.

 

드디어 백트래킹 문제를풀어서 690점대로 진입했다 후후

 

 

https://www.codetree.ai/missions/8/problems/last-remaining-number?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

삼성 코테 2번문항으로 주로 등장하는 시간제한 관련 자료구조 문제. 

특히나 자료구조에 대한 이해도가 높아야하고 python으로 하기 어렵기로 악명이 높다. 

그것을 푸는 방법중 우선순위 큐를 사용하고, 파이썬은 heapq 를 사용하여 푼다. 

그 예제문제를 풀어봤다. 

 

메인으로 알아야할것은, 

heappop과

heappush 

push(배열이름,값) 들어갈때 자동으로 최소값대로 인덱스가 정렬된다는걸 명심하자. 

 

import heapq

n=int(input())

maps=list(map(int,input().split()))

pd=[]

for j in range(len(maps)) :

    heapq.heappush(pd,-maps[j])

while (len(pd)>=2) :

    a=-(heapq.heappop(pd))

    b=-(heapq.heappop(pd))

    c=abs(a-b)

    if not c ==0:

        heapq.heappush(pd,-c)

    else:

        pass

if len(pd) ==0:

    print(-1)

else:

    print(-heapq.heappop(pd))