알고리즘

풀이 '부모노드 = 왼쪽 자식노드 * 오른쪽 자식노드' 이다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int[] ary; static long[] tree; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(..

풀이 구간 합 구하기에서 풀었던 방법은 '부모노드 = 왼쪽 자식노드 + 오른쪽 자식노드' 였다. 이 문제에서는 최솟값을 구할 때는 '부모노드 = Math.min(왼쪽 자식노드, 오른쪽 자식노드)' 최댓값을 구할 때는 '부모노드 = Math.max(왼쪽 자식노드, 오른쪽 자식노드)' 로 구하면 된다. + min∙max 세그먼트 트리를 초기화할 때(init 함수) 구간에서의 min∙max를 구할 때(query 함수) 전체 탐색 범위를 1~N, 0~N-1 / 구간 탐색 범위 left right를 left-1~right-1, left~right 로 설정하면 된다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputS..

풀이 - 세그먼트 트리 구현 https://book.acmicpc.net/ds/segment-tree 세그먼트 트리 누적 합을 사용하면, 1번 연산의 시간 복잡도를 $O(1)$로 줄일 수 있습니다. 하지만, 2번 연산으로 수가 변경될 때마다 누적 합을 다시 구해야 하기 때문에, 2번 연산의 시간 복잡도는 $O(N)$입니다. book.acmicpc.net 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOE..

풀이 * 초기 문자열을 넣을 자료구조 : LinkedList Why? '커서' 를 중심으로 push, pop을 해야 하므로, LinkedList를 사용하였다. 연결구조로 각 요소가 이전과 다음 요소의 정보를 가지고 있어, 해당 정보를 활용하여 push, pop을 하기에 용이하다고 생각 1) 커서의 위치를 str.length()로 설정한다. 2) L, D 명령마다 커서의 위치를 이동시킨다. 3) B 커서의 위치를 왼쪽으로 이동시키고 삭제를 한다. - 이 때 커서의 위치가 맨 앞이었을 경우, 커서의 위치가 음수가 되므로 0으로 초기화 및 삭제를 하지 않는다. 4) P : 커서의 위치에 문자를 추가하고, 커서의 위치를 오른쪽으로 이동시킨다. 5) LinkedList의 list.get()으로 StringBuil..

풀이 1) 주어지는 함수가 R(뒤집기), D(삭제) 이므로, 주어진 자료구조를 읽어나가는 시점(처음, 끝)을 설정하는 게 중요하다. => deque 사용 start_point : true → 앞 start_point : false → 뒤 2) 'R' 이면 start_point 를 뒤집어주고, 'D' 이면 start_point 에 따라 pollFirst(), pollLast()를 한다. - 이 때, poll() 한 값이 null 이면 error 이다. 3) deque의 원소가 0개이더라도, "[]" 와 같이 출력을 해주어야 한다. (공백으로 출력했다가, 계속 틀렸다..) + 입력을 받을 때 [1,2,3,4,5] 형식으로 입력을 받는데 구분하려는 문자열을 StringTokenizer("[],") 한 번에 넘..

풀이 1) 뽑아내려고 하는 수(num)를 기준으로 왼쪽이 더 많은지, 해당 수를 포함해서 오른쪽이 더 많은지 비교해야 한다. => Deque 사용 2) num이 나올 때까지 pollFirst(), pollLast()를 실행한다. 연산 count++ 3) poll을 통해 추출한 수가 num과 같으면 이전까지 poll 했던 것들을 원상복귀를 시킨다. (deque.addAll()) - pollLast()가 같을 시에는 1번째 인덱스로 이동하는 과정이 필요하므로 count++ 3) 계산한 연산 수 count를 출력한다. + LinkedList로 deque을 만들어 deque.indexOf(num)을 이용해 찾고자 하는 num의 인덱스를 찾고 해당 인덱스와 중간 인덱스를 비교하여 왼쪽 이동, 오른쪽 이동을 결정할..

풀이 1) ArrayDeque 를 사용해서 Deque 정의한다. 2) 문제에서 주어진 명령 8가지를 Deque 함수를 사용해서 명령을 구현한다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; StringBuilder sb = new Stri..

풀이 1) 테스트케이스 T와 문서의 개수 N, 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 몇 번째에 놓여 있는지 M을 입력받는다. 2) 각 문서의 중요도를 입력받는다. 3) Queue에 저장되어 있는 M번째 문서가 언제 출력되는지 추적해야되므로, 각 문서를 Queue에 저장할 때 int[] 배열로 (i번째 문서, 우선순위)를 같이 저장한다. 4) Queue.peek()가 우선순위가 가장 높은 문서일 때, Queue.poll()을 하면서 문서를 출력한다. 그렇지 않을 때는, Queue.peek()가 우선순위가 가장 높은 문서가 될 때까지 Queue.add(Queue.poll())을 반복한다. 5) 우선순위가 가장 높은 문서부터 출력이 될 때 count++ 을 해주며, 찾고자 하는 문서(우선순..