forDevLife

처음에는, 이미 스택으로 들어온 값을 check해주는 배열을 통해서 조건을 검사하는 방식으로 코드를 구현했다. 결과는 시간초과.. 그래서 1 ~ n까지 들어간 수를 start pointer로 가리키는 방식을 적용했다. 이렇게 하면 check 배열이 별도로 필요가 없어진다. 또한 start pointer보다 작을 경우에만 stack에 넣고 큰 경우에는 pop이 가능한지 check 하면 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; public class Main { public static void main(String[] args) th..

계속 반복되는 문제이다. 확실히 구현 방법을 이해하고 외우자. for문은 항상 알고자 하는 최대 범위 숫자의 제곱근까지만 탐색하면 된다. 추가로 코드에도 주석으로 되어 있지만, for문에 대한 설명이다. // i에 들어오는 2의 배수부터 시작해서 자신을 더해가면서 true로 만들어준다. // 예를 들어, 3일 경우 3*2인 6부터 시작해서 6 -> 9 -> 12 .. 하는 식으로 없애준다. // 하지만 j = 2일 때, 이미 2의 배수들은 모두 정리되므로 j = i * 2가 아닌 j = i * i부터 탐색하면 훨씬 빨라진다. // 즉 3일 경우, 6은 2에서 이미 정리된 수이므로 3 * 3 = 9 부터 정리한다. // 마찬가지로 133을 예로 들면, 133 * 2 = 266은 이미 2에 의해서 정리된 값..

앞서 푼 이진탐색이랑 완전히 동일한 문제이다. 다만 start를 0으로 두면 이후에 divide by 0 예외가 뜨므로, 문제 조건대로 꼭 1로 설정을 해두자(자연수) 예외는 입력으로 K = 2, N = 2, 1, 1을 넣을 때 발생했다. start가 처음에 0이면, mid 값이 0이 되므로 에러가 발생한다. 유의하자. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new S..

아래는 시간초과한 코드다. 매우 큰 수가 입력되어 결국엔 overflow로 인해서 정상적인 값이 나오지 않았고, Long으로 변경하자마자 시간초과 에러가 발생했다. 정석대로 이분 탐색으로 진행해야 한다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine(), " "); int N = Integer.parseInt(st.ne..

입력 시, 최대 높이를 받는다. 해당 높이부터 0까지 가장 짧은 시간을 구한 후, 마지막에 출력한다. import java.io.*; import java.util.*; class Answer { int time; int height; public Answer(int time, int height) { this.time = time; this.height = height; } } public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new Strin..

처음에는 그냥 단순히 큐로 구현했다. 역시나 풀리긴 하지만 시간 / 메모리를 좀 먹는 편. 아래는 큐가 아닌 LinkedList로 구현한 방법이다. idx가 움직이는 것을 다음과 같이 설명할 수 있다. 1. idx에 처음에 K-1만큼 더해준다. 우선 배열은 하나가 사라지면, 그 다음 걸 가리키게 되므로 한칸 내려서 더해준다. -1하지 않으면 원래 탐색 대상은 넘어가 버린다. 2. %= 연산을 통해 마치 실제로 큐에 계속 데이터를 넣는 것처럼 구현할 수 있다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = n..

브루트포스 - DFS로, 전체 겹치지 않는 부분집합(원소 3개)을 만들어 모두 비교해 봐야 한다. DFS를 통해 겹치지 않는 원소의 집합 찾는 방법은 항상 유용하니 외우자. import java.io.*; import java.util.StringTokenizer; public class Main { static int[] arr; static int[] tmp; static int max; static int M; public static void DFS(int L, int S) { if (L == 3) { int sum = 0; for (int i = 0; i < 3; i++) { sum += tmp[i]; } if(sum

- GCD -> 유클리드 호제법으로 풀 수 있다. 최대 공약수가 구해지면, 최소 공배수는 두 수의 곱 / 최대 공약수이다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.read..

- 이전에 소수 관련된 문제 - 에라토스테네스의 체 방식으로 문제를 풀었었다. - 이번에는 다른 방식으로 소수 판별을 진행했다. (참조 블로그 : https://st-lab.tistory.com/80) import java.io.*; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); StringTokenizer st = new StringTokeniz..

HashMap이 HashSet보다 결과는 더 빠른 것으로 보인다. 또한 일반 println -> bw.write를 했더니 훨씬 빨라짐을 확인했다.. 앞으로 이걸 쓰자. import java.io.*; import java.util.HashMap; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out..