처음 시도는 완전 탐색으로 시도했지만 50%에서 시간 초과가 나왔다. N의 값이 1000 이하니 완전 탐색을 이용하면 시간 초과가 나오는 게 당연한 결과였다. 다른 방법을 생각해봤지만 떠오르지 않아서 검색을 통해 힌트를 참고했다. 처음에는 이 문제가 왜 DP를 이용하는지 이해가 잘 안되었다. 점화식도 떠오르지 않았고, 지금까지 풀었던 문제들과는 조금 달라서 그렇게 생각한 것 같다. 풀이 방법은 R, G, B를 0, 1, 2로 대응시키고 다음 집의 색상을 봐야 한다. 예를 들어 첫 번째 집이 0이라면 다음 집은 1 또는 2가 되어야 한다. 1과 2중에서 더 작은 값을 더해 n까지 배열을 만들면 된다. 마지막으로 배열의 세 값 중 가장 작은 값을 출력하면 된다. DP로 풀 수 있는 문제지만 이전 집의 색상과..
다른 문제를 풀면서 투 포인터 알고리즘에 대해 알게 되었고 대표적인 문제를 풀어 보았다. 실버 4 문제라 기본적인 투 포인터 개념만 이해한다면 바로 풀 수 있는 문제이다. 투 포인터 알고리즘은 연속되고 길이가 가변적인 부분 배열을 만들어 특정 조건을 만족시키는 알고리즘이다. 배열을 반복적으로 탐색할때 2중 for문을 이용한다면 시간 복잡도가 O(n^2) 나온다. 그러나 투포인터 알고리즘을 이용한다면 시간 복잡도를 O(n)까지 줄일 수 있다. 투 포인터 알고리즘의 방식은 두 가지가 있다. 1. 시작점과 끝점이 배열의 시작점에서 같이 시작하는 것 2. 정렬된 배열 안에서 시작점과 끝점이 각각 배열의 시작점과 끝점에서 시작하는 것 이 문제는 첫 번째 방식으로 접근하여 풀었다. 간단하면서도 강력한 알고리즘이라 ..
문제 이름이 이중 우선순위 큐라서 우선순위 큐로 풀어야 하나 생각했다. 그런데 코드를 반쯤 작성하고 나니 TreeMap을 이용하는게 더 간단하겠다는 생각이 들어 TreeMap을 이용해서 다시 짰다. 골드 4 문제치고는 쉬운편이라고 느꼈다. 최종 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; import java.util.TreeMap; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamR..
N의 입력 크기가 1,000,000 까지 가능하므로 2중 for문을 사용해서 단순 비교를 하면 바로 시간초과가 날것을 예상했다. 그래도 한번 작성해 보았는데 1%에서 바로 시간초과가 난다. 어떻게 해야 할지 30분 정도 고민을 하다가 검색을 통해 힌트를 얻었다. 문제 해결의 키포인트는 정렬이다. 각 입력값을 낮은값부터 순위를 매겨서 처리하는것이다. 각 입력값에 대한 순위값을 출력하면 된다. HashMap을 이용해서 입력값과 순위값을 넣고 원본 배열과 비교하며 출력하면 된다. 구현이 어려운 문제는 아니지만 정렬이 필요하다는것과 적절하게 HashMap을 사용해야 한다는 생각을 하기 쉽지 않았다. 실패 코드(시간 초과) import java.io.BufferedReader; import java.io.Inpu..
