재원블로그 재원블로그

이 문제는 스택을 이용해서 풀었다. 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..

이 문제는 이진 트리의 탐색을 이용한 문제이다. 2차원 좌표로 점들이 주어지고, 이들을 이진 트리로 간주하여 전위, 후위 순회 결과를 찾는 문제이다. 중요한 점은 x좌표가 같은 것이 하나도 없다는 사실이다. 또한 이진 트리를 중위 순회하면 오름차순으로 정렬된다는 사실도 굉장히 중요하다. 이를 이용하면 x좌표로 오름차순 정렬한 노드들의 순서가 곧 중위 순회한 결과를 나타내게 된다. 그러면 문제가 중위 순회 결과가 주어졌을 때, 전위 및 후위 순회의 결과를 나타내는 문제로 바뀌게 된다. 일정 구간 안에서 가장 y좌표가 높은 노드가 루트임을 이용하여 문제를 쉽게 풀 수 있었다. import java.util.*; import java.io.*; class Solution { Node[] inorder; Lis..

이 문제는 그리디 알고리즘을 이용해서 풀었다. scores의 길이 범위가 [1, 100,000] 이므로 O(N log N) 이하의 알고리즘을 생각해야 한다. 나의 경우에는 근무 점수를 기준으로 내림차순, 같을 경우 동료 점수 기준으로 내림차순으로 정렬했다. 그 후 delete() 메소드를 통해 기준 미달인 사원을 추출하고, rank() 메소드를 통해 완호의 등수를 매기고 리턴한다. delete 메소드가 굉장히 중요한데, 기본 아이디어는 high라는 변수를 정하고 list를 순회하면서 동료 점수가 더 낮은 경우 삭제하고 만약 높다면 high에 새로 저장하는 것이다. 여기서 주의할 점은 점수에 중복이 가능하여 분기문이 추가된다는 것이다. 만약 입력이 [[4, 0], [2, 3], [4, 4], [2, 6]]..

이 문제는 kmp 알고리즘 및 문자열, 구현 문제이다. 문제를 단순화하면 라디오에서 재생된 만큼의 음표 문자열에서 내가 들은 문자열을 각각 탐색하는 문제이다. 아주 단순하게, 브루트포스 알고리즘으로 문자열 탐색을 수행할 경우 O(NM)의 시간이 걸린다. 입력 문자열의 최대 길이가 1,439 이므로 단순하게 제곱하면 약 200만이고, 이를 최대 길이 100인 문자열 배열에 대해 수행해야 하므로 약 2억번의 연산이 걸려 1초 안에 풀 수 없게 된다. 그러므로 문자열 탐색 시간을 줄여아 하고 이 때 kmp 알고리즘이 떠올랐다. O(N + M) 시간에 탐색이 가능하므로 시간 안에 풀 수 있게 된다. 이 문제에서 핵심 포인트가 몇개 있는데 그 중 하나는 #이 붙은 음표이다. C#은 하나의 문자로 취급되어야 하기 ..

이 문제는 이진 검색 트리를 이용한 문제이다. 이진 검색 트리의 전위 순회의 경우, 루-왼-오 순으로 노드를 탐색하고, 후위 순회의 경우 왼-오-루 순으로 탐색한다. 따라서 주어진 범위 내에서의 벡터에서 가장 첫번째 노드는 항상 루트이고, 그 안에서 루트보다 작은 첫번째 값이 왼쪽 서브트리의 루트, 루트보다 큰 첫번째 값이 오른쪽 서브트리의 루트가 된다. 이를 이용해서 풀면 된다. 주의할 점은 이진 검색 트리가 최악의 경우 1자로 쭉 이어질 수 있는데, 이를 까먹고 전역 배열을 만들어 원래 트리를 형성하려고 하면 안된다. OutOfBounds 런타임 에러를 만나게 된다. #include #include #include using namespace std; #define MAX 10000 #define I..