스택 문제입니다. 모든 수를 같은 수로 만드는데 가장 적은 add 사용 회수를 출력해야합니다. 스택이 비어있다면 현재 값을 넣어줍니다. 스택이 차있고, 스택 top값보다 현재값이 크다면 차이만큼 결과값에 더해주고 pop(), push(현재 값)을 해줍니다. 스택이 차있고, 스택 top값보다 현재값이 작다면 pop(), push(현재 값)을 해줍니다. 입력값이 다 들어오면 stack의 값들을 max값과 차를 구해서 결과값에 더해주었습니다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedRea..

이분탐색 문제입니다. 최대체력을 기준으로 이분탐색을 진행합니다. 해당체력으로 용을 잡을 수 있다면 => right = mid - 1; 해당체력으로 용을 잡을 수 없다면 => left = mid + 1; 이 문제는 간단한 이분탐색이지만 Integer값을 넘어가게 되면서 해당 문제를 고치느라 시간을 썼습니다. Long타입으로 선언해주고 1_000_000 * 1_000_000의 결과값인 999999000001를 사용해서 아래와 같이 썼습니다. Long right = 999999000001L * n; import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { Buf..

누적합 문제입니다. 수열이 주어집니다. [연속한 k개의 수1]와 [연속한 k개의 수2]의 차가 가장 적은 값을 구해야합니다. 위의 [연속한 수1] [연속한 수2]는 겹치면 안되며, 적은 값이 여러개면 k를 최대인것으로 출력합니다. 누적합을 구해준후에 브루트포스로 모든 경우의수를 확인했습니다. import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new O..

문자가 주어지고 암호를 찾는 규칙이 있을때 암호를 몇번만에 찾는지 구하는 문제입니다. 문자는 최대 100가지이며, 영어 대,소문자는 52가지이므로 48가지의 문자가 더 있다고 생각했습니다. 배열에 해당문자가 쓰여진 순서를 기록했습니다. 배열 인덱스에 매핑하는것은 아스키코드를 참고했습니다. 사용 될 수 있는 문자 중 가장 작은 수의 문자는 '!' 입니다. int index = s.charAt(i) - '!'; arr[index] = i; 매핑한 후에 수학 계산을 해주었습니다. for (int i = 0; i < code.length(); ++i) { int index = code.charAt(i) - '!'; result *= size; result += arr[index]; result %= 900528..

누적합 문제입니다. 직사각형안의 값들의 평균을 구하는 문제입니다. (R * C) * Q = (1000 * 1000) * 10000 => 10_000_000_000이 나오므로 매번 모든 값들을 더하면 시간초과가 발생합니다. 2차원 배열의 누적합을 구해줍니다. 직사각형이 주어지면 해당 위치의 값을 누적합을 통해서 구하고 안의 개수만큼 나누어서 평균을 출력해줍니다. import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Buffe..

투 포인터 문제입니다. 두 값의 차의 절댓값이 M이상이면서 가장 작은 값을 찾아야합니다. 같은 수를 고를수도 있습니다. left와 right를 0으로 둡니다. 해당 위치의 값들의 차이를 구합니다. 1. m보다 작은 경우 - right 증가 2. m보다 큰 경우 - left 증가 - 결과값보다 작으면 갱신 3. m과 같은 경우 - left, right 증가 - 결과값보다 작으면 갱신 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System..

그리디 문제입니다. 최소의 화살을 사용해서 풍선을 터트려야 합니다. 풍선의 높이가 주어지고 화살은 직선으로 이동합니다. 화살이 풍선과 닿으면 풍선은 터지고 화살의 높이가 한칸 내려갑니다. 1_000_002 크기의 배열을 만들었습니다. 풍선의 높이가 입력으로 들어오면 해당 높이 + 1에 풍선이 있는지 확인합니다. - 있으면 해당 높이에 -1을 하고 현재위치에 +1을 합니다. - 없으면 현재위치에 +1을 합니다. 모든 풍선에 위의 과정을 반복해주고 배열안에 값들의 합을 출력해주었습니다. import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception { BufferedR..

그리디 문제입니다. 크레인과 박스가 주어지고 배는 한번에 하나의 박스를 옮길 수 있습니다. 각 크레인마다 무게 제한이 있으며, 무게 제한 보다 큰 박스는 옮길 수 없습니다. 모든 박스를 크레인을 통해 옮기는데 걸리는 최솟값을 구해야합니다. 먼저 정렬을 해주었습니다. 그리고 각 크레인마다 들 수 있는 가장 높은것들부터 들도록 하였습니다. 가장 무게제한이 큰 크레인이 마지막 박스 까지 온 경우 종료하고 카운트한 값을 출력합니다. 불가능한 경우를 찾기위해 정렬한 후 크레인의 가장 큰 무게제한과 박스의 가장 큰 무게를 비교해서 박스가 더 큰 경우 불가능한 경우로 판단해주었습니다. import java.util.*; import java.io.*; public class Main { public static vo..