알고리즘/문제풀이 - 백준

백준 1655 가운데를 말해요

문제 : https://www.acmicpc.net/problem/1655 서론 상당히 오래 걸린 문제. 반나절은 푼것 같다. 우선순위 큐는 내부 힙이 완벽히 정렬이 되지는 않지만 큐에서 빼낼때마다 배열에 저장하면 완벽히 정렬이 된다. 그래서 입력 한번 받을때마다 큐를 비웠다 채웠다를 반복해봤는데 시간초과 트리에서 수식으로 얻을 수 있는게 있는지 고민해봤으나 찾을 수 없었다. 엑셀에서 예상되는 결과를 표로 그려봤는데 시프트레지스터가 떠올라서 아이디어를 얻을 수 있었다. 아이디어 입력값이 들어올때마다 예상되는 중앙값을 표로 나타내봤다. 각 행의 노란색 셀이 중앙값인데, 노란색 셀이 두개면 둘 중 최소값이다. 우선순위 큐에선 입력될때마다 위와 같이 완벽히 정렬이 되지는 않지만 일단은 정렬이 된다고 가정하고 ..

2019. 8. 21. 20:29