Java/Algorithms

문제 접근 방식 우선순위 큐를 활용해서 풀 수 있는 문제로 우선순위 큐를 덱처럼 사용하면 된다. 원할 때마다 언제든지 가장 작은 값을 빼거나 가장 큰 값을 뺄 수 있어야 하기 때문에 최소힙과 최대힙에 동일하게 수를 추가해 준 후에 가장 큰 값을 빼야 하는 경우에는 최대힙에서 반대의 경우는 최소힙에서 빼주면 된다. 이때 조심해야할게 반대쪽에서 뺀 수는 반대쪽에만 사라지고 다른 한쪽에는 존재하기 때문에 맵을 이용해서 수마다 등장 횟수를 카운팅 해준 후에 수들을 큐에서 꺼낼 때마다 꺼낸 수가 등장 횟수가 남아있는지 확인하여 다른 쪽의 큐와 상태를 유지해 줄 수 있다. 예를 들면 최대값을 하나 빼려고 최대힙에서 9라는 숫자를 꺼냈는데 해당 숫자의 카운트가 0이라면 최소힙에서 빼서 사라진 값이기에 해당 수를 건너..

문제 접근 방식 정말 쉬운데 하고 풀었다가 바로 틀려버린 문제다... 데드라인이 빠른 순으로 정렬하고 같다면 보상이 큰 순으로 정렬한 후에 그대로 반복문을 돌면서 더해줬더니 예제는 맞지만 제출하니 틀렸다. 예제가 하나뿐이라 생각하지 못한 케이스가 있었는데 데드라인이 나중이라도 이전 데드라인 문제를 생략하고 이후의 데드라인 문제를 푸는 것이 좋을 때가 있다. 2 30 2 20 3 60 3 50 위와 같이 데드라인이 2일 때 2개를 선택하는 것보단 둘 다 선택하지 않고 데드라인이 3일 때를 선택하는 것이 더 효율적이다. 그래서 정렬은 그대로 유지하되 최소힙을 사용해 이전에 선택한 값이 이후에 선택할 값보다 비효율적인 경우 교체해줘야 한다. 2 30 2 20 최소힙 {20, 30} 3 60 최소힙 {30, 6..

문제 접근 방식 수가 하나씩 추가될 때마다 현재까지의 수 중에서 중간값을 출력해야 하고 현재까지 부른 수가 짝수 개면 중간값은 둘 중 더 작은 수를 출력한다. 무식하게 생각하면 매번 수를 부를 때마다 정렬해서 중간 인덱스를 출력하는 방법을 떠올릴 수 있지만 문제의 제한 시간과 입력을 생각하면 불가능하다. 최소힙과 최대힙 우선순위 큐를 각각 하나씩 만들어서 특정 상황에 맞게 수를 저장하고 꺼내는 방식으로 효율적으로 풀 수 있는 문제다. 예를 들어 현재까지 주어진 수가 짝수 개일 때를 생각해 보면 현재 수가 이전까지의 중간값보다 작은 경우를 살펴보면 다음과 같다. 4 5 10 (11) 12 15 20// 중간값 11 >> 6 이 입력으로 들어옴 4 5 6 (10 11) 12 15 20 // 중간값이 두개지만..

문제 접근 방식 맨 처음에 문제를 풀 때는 잘못 이해해서 정렬을 사용해서 풀 수도 있을 줄 알았는데 문제를 제대로 이해하고 보니 중간중간 계산 결과를 다시 넣을 때마다 정렬을 한다면 매우 비효율적이기 때문에 우선순위 큐를 사용해서 풀었다. 10 // 10개의 수가 주어졌을 때 123 456 234 998 12 7 876 887 455 234 만약 위와 같은 입력이 주어졌을 때 계산 순서는 다음과 같다. 7 + 12 = 19 19 + 123 = 142 142 + 234 = 376 376 + 234 = 610 610 + 455 = 1065 1065 + 456 = 1521 1521 + 876 = 2397 2397 + 887 = 3284 3284 + 998 = 4282 위 순서대로 계산하여 결과를 모두 더하면 ..

문제 접근 방식 배열에 수를 모두 저장한 후에 정렬하고 끝에서 n번째 인덱스를 출력해도 풀리는 문제지만 우선순위 큐를 이용해서 좀 더 효율적으로 풀 수 있다. 최소 힙으로도 풀 수 있지만 최대 힙으로 푸는 것이 더 효율적이니 자바에서 제공하는 우선순위 큐 기준으로는 생성자 파라미터로 정렬 기준을 역순으로 주어 최대 힙을 사용할 수 있다. 최대 힙에 입력 받은 수들을 모두 넣어준 후에 n개를 꺼내면 n번째 큰 수가 나오게 된다. 풀이 public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); ..

문제 접근 방식 최소 힙을 구현하는 문제다. C++의 STL이나 자바의 유틸 클래스에 이미 구현된 우선순위 큐를 사용해서 편하게 풀 수도 있지만 구현해봐야 어떤 원리로 동작하는지를 이해하기 쉽기 때문에 직접 구현해봤다. 최소 힙은 부모가 자식보다 작은 값을 가지고 있는 이진 트리 구조여야 하기 때문에 새로운 값을 추가할 때는 가장 마지막 자식 노드에 값을 추가한 후에 해당 노드가 부모 노드보다 큰지 검사하면서 만약 더 작다면 부모 노드와 바꿔주면 된다. 반대로 가장 작은 값을 하나 꺼낼 때는 최소 힙의 구조상 무조건 최상위 부모 노드가 가장 작은 값에 해당하기 때문에 해당 값을 출력하고 삭제해주면 된다. 풀이 public class Main { public static void main(String[] ..

문제 접근 방식 우선순위큐 최소힙을 사용해서 풀 수 있는 문제로 직접 구현해서 풀 수도 있지만 자바에서 제공하는 우선순위 큐를 사용하여 풀었다. 두 가지 방식으로 풀어봤는데 첫 번째는 우선순위 큐의 생성자에 파라미터로 정렬 기준을 제공해 문제에서 요구하는 순서대로 정렬되게 하는 방법이고 두 번째 방법은 우선순위 큐에 모두 절댓값으로 변환해 양수인 값만 저장하면서 맵에 음수인 경우만 카운팅 하는 방법이다. 우선 첫 번째 방법부터 살펴보면 정렬기준을 절댓값이 같다면 더 작은 값이 먼저 나와야 하니 abs(x) == abs(y) 라면 x - y를 리턴해주고 두 수의 절댓값이 다르다면 절댓값이 더 작은 수가 앞에 오면 되니 abs(x) - abs(y)를 리턴해주면 된다. 두 번째 방법은 자바에서 우선순위 큐의 ..

문제 접근 방식 문제의 포인트는 배열을 돌리는 것인데 직접 원소들을 움직일 수도 있지만 90도씩 회전할 때마다 배열의 요소들이 어떻게 움직이는지만 안다면 배열을 움직이지 않고도 풀 수 있다. 만약 위와 같은 n행 m열의 스티커 배열이 주어졌다고 가정했을 때 배열을 90도씩 회전시켜 보겠다. 우선 오른쪽으로 90도 회전시켰을 때를 살펴보면 행과 열이 뒤집히고 뒤집히기 전의 n행부터 1번째행까지의 첫 열의 값들이 첫 행에 위치하고 있고 그 아래줄부터는 다시 n행부터 1번째행까지의 두 번째 열의 값들이 위치하고 있는 것을 알 수 있다. 인덱스를 정리하면 위와 같다. 한 번 더 90도를 회전하면 위와 같고 다시 행과 열이 뒤집혀 원본 상태에서 인덱스만 뒤집히기 때문에 원본 배열을 거꾸로 읽어주면 된다. 인덱스는..