Java

문제 접근 방식 최소 힙을 구현하는 문제다. 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도를 회전하면 위와 같고 다시 행과 열이 뒤집혀 원본 상태에서 인덱스만 뒤집히기 때문에 원본 배열을 거꾸로 읽어주면 된다. 인덱스는..

문제 접근 방식 플러그를 최소한으로 빼면서 전기용품을 사용하려면 이후에 다시 쓰일 전기용품의 플러그를 빼는 것보단 나중에 쓰일 일이 없는 플러그를 빼는 것이 효율적일 것이고 만약 나중에 쓰인다면 가장 나중에 쓰이는 것을 빼는 게 효율적이다. 아래와 같이 상황을 세 가지로 나누어 처리해 주면 된다. 이미 멀티탭에 꽂힌 전기용품이면 그대로 사용하면 되니 아무런 행동도 하지 않음 멀티탭에 빈 공간이 있는 경우에는 그대로 빈 공간에 꽂음 빈 공간이 없으면 앞으로 사용되지 않거나 가장 나중에 사용되는 것을 빼고 새로 꽂음 첫 번째 상황을 처리하기 위해 불리언 배열을 만들어 멀티탭에 꽂거나 뺄 때마다 상태를 바꿔주었고 두 번째와 세 번째 상황을 처리하기 위해 정수형 배열을 만들어 멀티탭에 꽂혀 있는 플러그들이 어떤..

문제 접근 방식 주어진 수열에서 순서 상관 없이 수들을 더하거나 둘을 묶어서 곱하여 가장 큰 값을 얻기 위해서는 빼야 할 때는 가능한 가장 작은 수를 더해줄 때는 가장 큰 수를 더해줘야 한다. 두 수를 곱하는 경우를 생각해보면 음수 * 음수 = 양수 음수 * 0 = 0 양수 * 양수 = 양수 위와 같이 세 가지 경우가 있고 두 수를 더하는 경우를 생각해보면 양수 * 1 < 양수 + 1 양수 * 0 < 양수 + 0 위와 같은 경우가 있다. 좀 더 간단하게 정리해보면 아래와 같다. // 음수로 만들 수 있는 최적의 해 음수 * 0이하의 수 // 양수로 만들 수 있는 최적의 해 양수 * 양수 양수 + 1 양수는 0과 곱하거나 더하는 경우에는 어떤 이득도 볼 수 없기 때문에 0은 위와 같이 음수와 처리해주는 것..

문제 접근 방식 1 3 2 5 3 5 6 7 위와 같이 일직선 상의 선분의 시작점과 끝점이 주어졌을 때 시작점이 가장 작은 순으로 정렬하고 각 선분을 그어보면 세 가지 경우로 선분을 그을 수 있는데 1 2 3 4 5 6 7 1 3 2 5 3 5 6 7 위와 같이 처음 1-3 선분이 있을 때 다음에 오는 2-5 선분은 이전 1-3선분에 겹치면서 길이가 조금 더 긴 경우 3-5 선분은 이전 선분 자체에 모두 겹치는 경우 6-7 선분은 겹치지 않는 새로운 선분인 경우다. 완전히 새로운 경우에는 끝점 - 시작점으로 선분의 길이를 구할 수 있고 겹치는 경우에는 겹치지 않는 경우만 계산하면 되기 때문에 현재 선분의 끝점에서 이전 선분의 끝점을 빼주면 되고 완전히 겹치는 경우에는 계산할 필요가 없다. 풀이 publi..

문제 접근 방식 우선 문제를 정리해 보면 꽃이 피는 날과 지는 날이 주어졌을 때 피는 날을 포함한 날부터 꽃이 피기 시작하고 지는 날을 포함하지 않은 날까지 꽃이 피어있는다. 정원에 꽃이 하나라도 피어 있는 상태를 유지하기 위해선 이전에 핀 꽃이 지기 전이나 지자 마자 바로 다음 꽃이 피어 있어야 하기 때문에 이전에 심은 꽃들 중 가장 늦게 지는 날보다 전이거나 지는 당일에 꽃이 피는 경우에만 심을 수 있다. 10 2 15 3 23 4 12 6 5 5 2 5 31 9 14 12 24 6 15 9 3 6 3 6 15 2 28 4 25 6 15 9 27 10 5 12 31 7 14 9 1 위와 같은 입력이 주어졌을 때 꽃이 빨리 피는 순서대로, 같은 경우에는 빨리 지는 순서대로 먼저 정렬을 해준다. 2, 1..

문제 접근 방식 주어진 식에 적절히 괄호를 추가해 가장 작은 결과를 얻어야 하는데 간단하게 생각해 보면 - 부호가 등장한 이후에 나오는 모든 숫자들을 - 부호가 재등장하기 전까지 빼주면 된다. 55-50+40-50+40+30-50 예를 들어 위와 같은 식이 주어졌다면 55-(50+40)-(50+40+30)-(50) 이렇게 괄호를 추가해 계산하는 것이 가장 작은 결과를 얻는다. 55-((50+40)-(50+40+30)-(50)) 조금만 더 생각해 보면 첫 - 부호 등장 이후에 오는 모든 수들은 복잡하게 생각할 필요 없이 빼도 상관이 없다는 것을 알 수 있다. 그래서 처음으로 -부호가 등장하기 전까지만 값을 더해주고 이후에 오는 모든 수들은 빼주면 된다. 풀이 public class Main { public..