알고리즘

문제 자체는 어렵지 않다. 이전 글인 '나무 자르기' 글을 참고하면 쉽게 풀 수 있는 문제다. 문제의 조건 중 'N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이 때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오'는 중간값(mid, 자르는 길이)로 잘랐을 때의 랜선 길이의 수(cnt)가 N보다 크더라도 조건에 일치하는 것으로 본다는 의미를 가진다. 또한, 해당 조건(N개 이상의 랜선을 만들 수 있도록 랜선 길이를 정하는 방법)에 일치하는 경우의 수가 여러 가지이며, 이 경우들 중에서 자르는 랜선의 최대 길이(여기서는 이를 확인하기 위한 값으로 mid 사용)가 최댓값인 경우를 찾는 문제이다. 즉, cnt가 M과 같은 경우에는 lt를 mid + 1 로 변경시켜서 두 범위 중 더 큰..

이분 탐색을 통해 최소한 M미터 이상의 나무를 가져갈 수 있는 상황을 모두 체크해야 한다. 단순 이분 탐색과 다른 점은 이분 탐색에서는 확인하고자 하는 배열을 정렬해서 모든 처리가 끝나지만, 이 문제처럼 배열의 순서가 지켜져야 하는 상황에서는 아래와 같이 Java Stream을 사용해 rt 값을 최댓값으로 정의할 수 있다. (lt 역시 최솟값으로 설정해야 한다.) 유의할 점은 조건에 일치하는 경우에 lt, rt를 어떻게 움직이냐는 것인데, 높이(mid)를 높게 잡을 수록 가지고 갈 수 있는 나무가 적어진다. 문제에서는 자르는 높이의 최댓값(가져갈 수 있는 양은 최솟값이 됨)을 구하기 때문에, sum이 M과 일치하거나 더 높은 경우에는 자르는 높이를 올려야 한다. 즉, 두 범위 중 뒷 범위에서 탐색이 다시..

이분 탐색(Binary Search) 탐색(search) 기법 중 하나로, 정렬된 배열에서 찾고자하는 값을 탐색할 때 그 범위를 두 부분으로 나누어(=이분) 탐색하는 방법이다. 탐색하고자 하는 범위를 계속해서 줄여감으로써 시간 효율성을 O(logN)까지 올릴 수 있다. 탐색 범위를 줄이는 방법은 다음과 같다. 범위의 가장 중앙 인덱스(mid)의 값과 찾고자 하는 값을 비교한다. 찾고자 하는 값이 해당 인덱스(mid) 값보다 클 경우 범위는 해당 인덱스(mid)의 바로 뒤(mid + 1)부터 탐색 범위의 마지막 인덱스(처음에는 끝 인덱스)까지이다. 다시 정의된 범위에서 가장 중앙 인덱스의 값과 비교한다. (mid 값 변경) 찾고자 하는 값이 중앙 인덱스 값보다 작을 경우 범위는 탐색 범위의 시작 인덱스부터..

문제(백준 캡쳐) 초기 작성 코드 import java.util.Scanner; public class Main { private int solution(String str) { int answer = 0, idx = 0; char[] stack = new char[str.length()]; stack[idx++] = '('; for (int i = 1; i < str.length(); i++) { char c = str.charAt(i); if (c == '(') stack[idx++] = c; else { if (c == str.charAt(i - 1)) { stack[--idx] = ' '; answer++; } else { stack[--idx] = ' '; answer += idx; } } } ..

문자열 S와 T가 주어지고, S에서 문자열 T와 아나그램이 되는 부분문자열의 개수를 출력하는 문제이다. 첫 줄에 S가, 다음 줄에 T가 입력된다. 주어지는 문자열의 각 문자를 해싱해서 문자의 개수를 value로 삼는 것이 기본이 된다. 여기에 문자 T는 항상 S보다 짧은 문자열이고, S 내에서 T와 아나그램인 연속되는 문자를 찾는 것이기 때문에, T의 길이만큼 sliding-window 알고리즘 기법을 사용하면 된다. 사실 처음에 two-pointer 알고리즘 기법도 함께 적용하려 했으나 다른 문제로 실패하면서 보류하게 되었다. 이후에 코드를 개선할 때 추가할 예정이다. 많은 시간이 소요된 부분 two-pointer, sliding-window 알고리즘을 사용하기 위해 문자열 T를 해싱할 때 S 문자열의..

0과 1로 구성된 길이가 N인 수열이 주어지면, 이 수열에서 최대 k번 0을 1로 변경할 수 있습니다. 최대 k번의 변경을 통해 이 수열에서 1로만 구성된 최대 길이의 연속부분수열을 찾는 프로그램을 작성하는 문제이다. 첫 줄에 수열의 길이인 자연수 N(5

N개의 수로 이루어진 수열이 주어지면, 이 수열에서 연속부분수열의 합이 특정숫자 M이 되는 경우가 몇 번 있는지 구하는 문제이다. 초기 작성 코드 import java.util.Scanner; public class Main { private int solution(int n, int m, int[] arr) { int answer = 0; for (int i = 0; i m) break; } } return answer; } public static void main(String[] args..

N일 동안의 매출 중 연속 K일 동안의 최대 매출액을 출력하는 문제다. 첫 줄에 N(5

초기 작성 코드 import java.util.*; public class Main { private List solution(List a, List b) { List answer = new ArrayList(); answer.addAll(a); answer.addAll(b); Collections.sort(answer, new Comparator() { @Override public int compare(Integer o1, Integer o2) { return o1 > o2 ? 1 : o1 < o2 ? -1 : 0; } }); return answer; } public static void main(String[] args) { Main al = new Main(); Scanner sc = new S..

봉우리란, N*N 형태의 격자판에서 주변(상하좌우)의 값보다 높은 값을 가지는 인덱스들이 봉우리가 된다. 주변과 같은 값이 있다면 봉우리가 아님에 유의하자. + 격자판은 0으로만 구성된 행, 열에 감싸진다. (격자판의 상하좌우 마지막 행, 열은 모두 0으로 구성되어있다.) 초기 작성 코드 import java.util.Scanner; public class Main { private int solution(int n, int[][] grid) { int answer = 0; for (int i = 1; i grid[i][j + 1]) { if (grid[i][j] > grid[i - 1][j] && grid[i][j] > grid[i + 1][j]) { answer++; } } } } return ans..