재원블로그 재원블로그

이 문제는 Map을 이용해서 풀었다. 도로의 길이가 10억이므로 배열로 만들면 메모리 초과가 나게 된다. 주목할 점은 end - begin이 5000밖에 안된다는 점이다. 따라서 해당 부분만 저장하면 된다는 생각을 했고, Map을 이용해서 해당 범위 안의 숫자들을 저장했다. 정직하게 반복문을 돌려 1부터 1,000만까지 계산하면 당연히 시간 초과가 난다. 1의 경우 2부터 10억까지를 루프를 돌리기 때문이다. 따라서 num * 2가 begin보다 작을 경우를 두어 이 때는 연산을 통해 한번에 시작 숫자를 찾아내야 한다. 위 부분만 구현해낼 수 있으면 한 번에 문제를 풀 수 있다. import java.util.*; class Solution { Map numbers = new HashMap(); int ..

이 문제는 자료구조 및 구현 문제이다. 모든 속성의 길이가 최대 8까지이므로, 완전 탐색으로 시간 안에 구현이 가능하다. 먼저 모든 키의 경우의 수를 구하고, 각 경우에 대해 최소성과 유일성을 검증하는 방식으로 구현했다. 최소성과 유일성을 판단하는 로직이 상당히 까다롭지만, 구현을 해낸다면 문제는 쉽게 풀린다. import java.util.*; import java.io.*; class Solution { Set candidate = new HashSet(); String[][] table; int columnSize; int rowSize; public int solution(String[][] relation) { table = relation; rowSize = relation.length; co..

이 문제는 자료구조를 이용한 문제이다. 처음에는 00:00부터 23:59를 분으로 바꾸어 0 ~ 1339 까지 루프를 돌려 문제를 풀었으나, 계속 오답이 나왔다. 그래서 자료 구조를 사용하여 문제를 풀었고, 정답을 맞출 수 있었다. import java.util.*; import java.io.*; class Solution { static final int MAX = 2000; Stack stopped = new Stack(); Queue tasks = new LinkedList(); public String[] solution(String[][] plans) { List temp = new ArrayList(); for (final String[] plan : plans) { final String ..

이 문제는 완전 탐색을 이용해서 풀었다. 처음에는 정말 온전히 완전 탐색을 이용해서 구현했다. 하지만 정답은 나오나 시간 초과가 떴다. 조금만 생각해보면 시간을 완전히 줄일 수 있다. N * N 체스판에 N개의 퀸을 놓는다. 퀸은 가로, 세로, 대각선 전체를 이동할 수 있기 때문에, N * N 체스판에 N개의 퀸을 놓으려면 모든 행에 하나씩 퀸이 있는 모습일 것이다. 이 점을 이용하면 시간을 굉장히 많이 줄일 수 있다. class Solution { int N; int[][] board; int[] dy = {-1, -1, 0, 1, 1, 1, 0, -1}; int[] dx = {0, -1, -1, -1, 0, 1, 1, 1}; public int solution(int n) { N = n; board ..

이 문제는 스택을 이용해서 풀었다. 1부터 s 길이 - 1 까지의 부분 문자열 길이를 정하고, 그 부분 문자열에 대한 압축 연산을 수행하여 길이를 찾아내는 방식이다. 입력 s의 길이가 최대 1,000 이므로, O(n^2) 이하 알고리즘까지도 가능하다. 한 가지 주의할 점은 압축 후 마지막에 길이를 계산할 때, 10 이상의 count를 가진 경우 10은 두 자리 수이므로 2를 result에 더해줘야 한다. 이를 위해 String.valueOf() 를 통해 String으로 변환 후 length를 더해주는 것으로 정답을 구했다.= import java.util.*; import java.io.*; class Solution { final Stack st = new Stack(); public int solut..

이 문제는 구현 문제이다. 배열의 최대 크기가 100 x 100 이고, bulid_frame으로 주어지는 최대 길이가 1,000 이므로 최악으로 연산해도 1,000만이기 때문에 시간 초과가 나지 않는다. 문제에서 주어진 요구사항을 그대로 구현하면 된다. 기둥 요구사항 - 바닥 위 - 보의 한쪽 끝 부분 위 - 다른 기둥 위 보 요구사항 - 한쪽 끝 부분이 기둥 위 - 양쪽 끝 부분이 다른 보와 동시 연결 주의할 점은 유효성 검증에서 x - 1 부분을 가져올 때 x == 0 인 경우에는 런타임 에러가 나게 된다는 점이다. 이 부분에서는 요구사항에 따라 특이 케이스로 분리하면 정답이 나오게 된다. import java.util.*; import java.io.*; class Solution { static ..

이 문제는 누적 합을 이용해서 풀었다. 누적 합은 길이가 n인 arr 배열이 있다고 했을 때 sum[i] = arr[0....i] 까지의 합 으로 정의하여 구간 합을 빠르게 구하기 위한 테크닉이다. 누적 합을 이용한 테크닉이 하나 있는데 만약 i 부터 j 까지 전부 1을 더하고 싶을 경우 반복문으로 하는 것이 아닌 arr[i]++, arr[j + 1]-- 을 적용하고 나중에 일괄적으로 누적 합을 계산하면 원하는 결과가 나오는 방법이 있다. 이 방법을 사용하면 반복문으로 매번 하는 것보다 시간 복잡도가 많이 개선된다. 매 루프마다 정해진 구간에 반복문을 수행하는 게 아닌 나중에 일괄적으로 처리할 수 있기 때문이다. 이 문제 또한 이 방법을 생각하는 것이 핵심이었다. 그러나 이 방법으로 정답이 나오지 않아 ..

이 문제는 다이나믹 프로그래밍을 사용해서 풀었다. 다이나믹 프로그래밍을 사용하는 전형적인 문제이다. 요구사항으로 map이 1인 경우에는 차가 못 지나가고, 2인 경우에는 회전이 불가능하다. 2인 경우에는 매개변수로 주어지는 direction을 그대로 가져가면서 재귀 호출하면 간단하게 해결할 수 있다. import java.util.*; import java.io.*; class Solution { static final int MOD = 20170805; static final int RIGHT = 0; static final int DOWN = 1; int[][] map; int Y; int X; int[] dy = {0, 1}; int[] dx = {1, 0}; int[][][] dp = new in..