우선순위 큐

[python] 백준 - 2014. 소수의 곱

🤔문제 해결 G2 | 수학, 우선순위 큐 DP로 구해보려고 했지만 역시 아니었다. 2**31 길이의 배열은 좀 아닌거 같다. 어려워서 알고리즘 분류를 보니 우선순위 큐로 해결하는 문제였다. 우선순위큐는 큐 안에 있는 값들 중 최소 값을 반환할 수 있다. 파이썬에서는 힙큐를 불러와서 사용하고 힙큐는 최소힙 기반으로 되어있다. 해결방법은 최초 힙큐에 주어진 소수를 넣는다. 힙큐에서 숫자를 하나씩 꺼내면서 주어진 소수들을 곱해서 힙큐에 넣는다. (이 때 꺼내는 횟수가 소수의 곱들 중에서 N번째 수이다) 하지만 이렇게 되면 중복이 발생한다. ( 2*3 이나 3*2 ) 3*2는 되지만 2*3은 안된다는 식으로 힙큐에서 꺼낸 수가 소수로 나누어 떨어지면 그 다음 소수는 건너뛴다. 결과는 아래와 같다 💻소스 코드 i..

[python] 백준 - 1655. 가운데를 말해요

🤔문제 해결 G2 | 우선순위 큐 처음에는 가볍게 정렬로 풀었지만, 시간초과가 발생했다. ( 바이너리서치는 통과 된다고 함 ) 가운데 값 구하기를 열심히 찾아봤지만 없었다. 어쩔 수 없다. 이 문제의 의도는 우선순위 큐를 활용하는 것이다. 파이썬의 힙큐 모듈을 사용하면 되는데, 최소힙 기준으로 되어있다. 최소힙은 가장 작은 원소가 루트에 위치하는 것이다. 우리는 가운데 값을 찾아야 하기 때문에 힙을 두개 만들어서 왼쪽의 가장 큰 수와 오른쪽의 가장 작은 수를 비교하여 가운데 값을 구할 것이다. 이렇게 두 부분으로 나누면 가운데 값을 구 할 수 있다. 하지만!!!!!!!!!!! 최소힙으로 힙큐 모듈이 구성되어 있으므로, 왼쪽의 구성은 음수를 붙여서 거꾸로 만들어야한다. 이렇게 하면 왼쪽의 0번과 오른쪽의 ..

[python] 프로그래머스 - 야근 지수

🤔문제 해결 Lv3 가장 큰 값을 조금 씩 줄여나가야 하는 문제! - 우선순위 큐를 이용했다. 우선순위 큐는 리스트에서 pop()을 하게 되면 가장 작은 값이 나오게 된다. 여기서는 가장 큰 값을 꺼내야 하므로 각각의 값을 음수로 힙큐에 넣어 줬다. 가장 작은 값(사실은 가장 큰 값)을 꺼내서 1씩 더해준다. 그리고 다시 힙큐에 넣어준다. 테스트 케이스 1번을 풀이 해 보자. 4, [4, 3, 3] 위 그림의 첫째줄은 처음 힙큐에 넣었을 때이다. 다음 줄부터는 1시간씩 지날 때 마다의 힙큐의 상황이다. -4가 제일 작으므로 -4를 꺼내서 1을 더해주고 다시 넣는다. -3을 꺼내서 1을 더해주고 다시 넣는다. 또 -3을 꺼내서 1을 더해주고 다시 넣는다. 마지막으로 -3을 꺼내서 1을 더해주고 다시 넣는다..