본문 바로가기
  • 개발하는 곰돌이

우선순위 큐7

[Kotlin] 백준 22252 : 정보 상인 호석 문제 링크 22252번: 정보 상인 호석 암흑가의 권력은 주먹과 정보에서 나온다. 주먹은 한 명에게 강하고, 정보는 세계를 가지고 놀 수 있기 때문에 호석이는 세상 모든 정보를 모으는 "정보 상인"이 되고 싶다. 정보 상인은 정보를 www.acmicpc.net 문제 해설 HashMap과 우선순위 큐를 사용하면 문제를 수월하게 해결할 수 있다. HashMap의 Key에 정보 고릴라의 이름을, Value에 정보 고릴라가 가진 정보들의 가치가 내림차순으로 정렬된 우선순위 큐를 저장한다. 여기까지 하면 사실상 문제 풀이는 끝난 것이나 다름 없다. 1번 쿼리의 경우에는 Map에 저장되지 않은 정보 고릴라의 이름이 나오면 새로운 우선순위 큐를 생성하여 Map에 저장하고 정보들의 가치를 저장하면 된다. 2번 쿼리의 .. 2023. 3. 23.
[Kotlin] 백준 23757 : 아이들과 선물 상자 문제 링크 23757번: 아이들과 선물 상자 모든 아이들이 실망하지 않고 각자 원하는 만큼 선물을 가져갈 수 있으면 $1$을, 그렇지 않으면 $0$을 출력한다. www.acmicpc.net 문제 해설 우선순위 큐를 이용하면 수월하게 해결할 수 있다. 아이들이 선물을 가져갈 땐 선물이 가장 많이 남아있는 상자에서 가져가게 되는데, 우선순위 큐를 내림차순 정렬하도록 선언하면 우선순위 큐의 가장 앞에 있는 값은 항상 가장 많은 선물이 담긴 개수가 된다. 즉, 아이들이 선물을 가져갈 때마다 우선순위 큐의 가장 앞에 있는 값을 추출하여 아이들이 원하는 선물의 개수만큼 뺀 이후에 다시 삽입하는 과정을 반복하면 된다. 문제에서 모든 아이들이 실망하지 않고 선물을 가져갈 수 있는지 여부를 출력해야 한다. 선물이 가장 .. 2023. 3. 20.
[Kotlin] 백준 1715 : 카드 정렬하기 문제 링크 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 문제 해설 [Kotlin] 백준 14698 : 전생했더니 슬라임 연구자였던 건에 대하여(Hard) 위 문제와 매우 유사한 문제이다. 차이점이라면 곱셈이 아니라 덧셈이라는 점과 입력의 개수가 다르다는 것 정도 뿐이다. 따라서, 같은 방법으로 접근하면 된다. 우선순위 큐에 카드 묶음의 크기를 모두 추가한 후, 가장 작은 크기의 카드 묶음 2개를 뽑아서 합친 후 우선순위 큐에 새로 합쳐진 카드 묶음을 다시 추가하는 과정을 모든 카드 묶음이 하.. 2023. 3. 3.
[Kotlin] 백준 14698 : 전생했더니 슬라임 연구자였던 건에 대하여(Hard) 문제 링크 14698번: 전생했더니 슬라임 연구자였던 건에 대하여 (Hard) 각 테스트 케이스마다 슬라임을 끝까지 합성했을 때 청구될 비용의 최솟값을 1, 000, 000, 007로 나눈 나머지를 출력한다. 전기 에너지가 전혀 필요하지 않은 경우엔 1 을 출력한다. www.acmicpc.net 문제 해설 각 테스트 케이스마다 구해야 하는 총 비용은 매 합성 단계마다 필요한 전기 에너지, 즉 매 합성 단계마다 합성되는 슬라임의 에너지들을 모두 곱한 값과 같다. 이 값을 최소로 하기 위해서는 매 합성마다 에너지가 가장 낮은 슬라임 둘을 합성해야 하는데, 예제의 경우를 그림으로 표현하면 다음과 같다. 따라서 우선순위 큐를 사용하면 문제를 수월하게 풀 수 있다. 입력받은 모든 슬라임을 우선순위 큐에 삽입한다... 2023. 2. 12.
[Kotlin] 백준 26215 : 눈 치우기 문제 링크 26215번: 눈 치우기 집 2와 집 3 앞의 눈을 치우고, 집 2와 집 3 앞의 눈을 치우고, 집 1과 집 3 앞의 눈을 치운 뒤 집 3 앞의 눈을 두 번 치우면 5분만에 모든 집 앞의 눈을 치울 수 있다. www.acmicpc.net 문제 해설 정렬을 이용하여 풀 수 있는 문제다. 우선 문제의 조건에 따라 분당 치울 수 있는 눈은 한집만 1 또는 두 집에서 각각 1씩, 총 2를 치울 수 있다. 따라서 한 집 앞에 쌓인 눈의 양이 1440을 초과한다면 무슨 수를 쓰더라도 24시간 내에 치울 수 없기 때문에 -1을 출력하고 프로그램을 종료한다.(코드의 11~14번째 줄) 그 외의 경우는 각 집 앞에 눈이 쌓인 양을 내림차순으로 정렬하여 해결한다. 눈이 쌓인 양이 가장 많은 집과 두 번째로 많이.. 2022. 12. 12.
[Kotlin] 백준 11286 : 절댓값 힙 문제 링크 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제 해설 힙은 우선순위 큐를 이용하여 구현하면 되지만 우선순위에 대해서 조금 생각해볼 수 있는 문제다. 기본적으로 수를 담는 우선순위 큐는 작은 수의 우선순위가 높은데, Kotlin에서는 람다식을 이용하여 손쉽게 우선순위를 변경할 수 있다. 따라서 우선순위 큐 객체를 생성할 때 절대값이 같은 경우에는 작은 수가, 그 외에는 절대값이 작은 수가 우선순위가 높아지도록 변경한 후 문제의 조건을 구현하면 된다. Code import ja.. 2022. 12. 6.
[Java] 프로그래머스 : 더 맵게 문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 힙 트리(heap tree)를 사용하는 문제다. 입출력 예의 설명에 따르면 모든 음식의 스코빌 지수가 K이상이 되지 않았을 때는 문제의 조건에 따라 만들어진 새로운 음식도 섞이는 대상이 될 수 있다. 스코빌 지수가 가장 낮은 두 수를 지속적으로 뽑아내고 새로운 음식을 집어넣으면서 정렬을 해야하는데, 일반적인 배열이나 리스트를 사용하면 음식을 섞을 때마다 매번 정렬을 하게 되면 시간복잡도 상으로 굉장한 손해를 보게 된다. 따라서, 힙 트리를 사용하는 것이 바람직하다. 힙 트리 방식으로 동작하는 대표적.. 2022. 11. 24.