BOJ

이중 우선순위 큐 구현 문제였다. min-heap 과 max-heap 두개로 구현해볼까 했는데 뭔가 내가 전혀 모르는 방법이 있을 것 같아서 찾아보니 min-max-heap을 구현하는 방법과 c++의 STL 라이브러리에서 Multiset을 이용한 방법 그리고 내가 사용한 TreeMap을 이용한 구현 방법이 있었다. 먼저 나는 다른 알고리즘 문제를 풀면서 Map 자료구조 중에서는 항상 HashMap 만을 사용해왔었다. TreeMap은 내부가 레드 블랙 트리를 사용하고 있고 삽입, 삭제, 추가 모두 O(log n)의 시간복잡도가 나와서 HashMap 보다는 성능이 떨어진다. 하지만 범위의 검색을 하거나 최댓값, 최솟값을 찾을 때는 TreeMap을 사용하는 것이 효율적이다. 처음에는 구현할 때 중복으로 들어오..

스택을 사용한 문제였다. 어느 부분에 자료구조를 사용해야 하는지 감을 잡을 수 있는 문제이다. 우선 연산자, 피연산자, 괄호의 우선순위를 정해준다. '(', ')' = 0 '-', '+' = 1 '*', '/' = 2 그리고 input으로 주어진 식에서 탐색되는 경우는 4가지 이다. 1. 알파벳 2. 여는 괄호 3. 닫는 괄호 4. 연산자 1번의 경우엔 바로 sb에 append해주면 된다. 2번의 경우엔 바로 stack에 push 해주면 된다. 3번의 경우엔 스택의 top에 여는 괄호가 나올 때 까지 pop을 해서 그 요소를 sb에 append 해주면 된다. 4번의 경우엔 stack의 top에 있는 요소가 현재 연산자보다 높거나 같은 경우 계속해서 pop을 해서 sb에 append 해주면 된다. 그리고 ..

import java.io.*; import java.util.*; class Top { int loc; int len; Top(int loc, int len) { this.loc = loc; this.len = len; } } public class Main { static BufferedReader br; static StringTokenizer st; static int n; static int[] tops; static Stack s = new Stack(); static StringBuilder ans = new StringBuilder(); public static void main(String[] args) throws IOException { input(); solve(); System.o..

import java.io.*; import java.util.*; public class DeleteBracket { static BufferedReader br; static StringBuilder sb; static Stack s; static List list; static int brckNum; static List res; static HashSet dup; public static void main(String[] args) throws IOException{ input(); searchBrck(); solve(0, ""); Collections.sort(res); for(int i = 0; i < res.size(); i++) { if(!dup.contains(res.get(i))) { ..

import java.io.*; import java.util.*; public class Laboratory { static int[] dx = {-1, 1, 0, 0}; static int[] dy = {0, 0, -1, 1}; static BufferedReader br; static StringTokenizer st; static int n, m; static int res = Integer.MIN_VALUE; static int[][] map, copyMap, virusMap; public static void main(String[] args) throws IOException{ input(); solve(0); System.out.println(res); } static void input(..

import java.io.*; import java.util.*; public class SalePizza { static BufferedReader br; static StringTokenizer st; static int orderNum, m, n, ans; static int[] mPizzaPieces, nPizzaPieces; static List left, right; public static void main(String[] args) throws IOException{ /* 1. 피자 A의 부분합을 구한다. 2. 피자 B의 부분합을 구한다. 3. 두 배열의 합 중 정답과 일치하는 것을 고른다. 유의할 점은 피자는 원형이기 때문에 부분합을 구할 때 신경써준다. */ input(); getSu..

import java.io.*; import java.util.*; public class FourIntegersWithSumOfZero { static BufferedReader br; static StringTokenizer st; static int n; static long ans; static int[] a, b, c, d; static long[] left, right; public static void main(String[] args) throws IOException{ input(); calculate(); Arrays.sort(left); Arrays.sort(right); getSum(); System.out.println(ans); } static void input() throws..

import java.io.*; import java.util.*; public class Main { static BufferedReader br; static StringTokenizer st; static int n, s; static int[] arr; static List left; static List right; static long ans; public static void main(String[] args) throws IOException{ input(); dfs(left, arr.length/2, 0, 0); dfs(right, n, arr.length/2, 0); Collections.sort(left); Collections.sort(right); System.out.println..

import java.io.*; import java.util.*; class Point_1 { int x; int y; Point_1(int x, int y) { this.x = x; this.y = y; } } public class AlgoSpot { static int[] dx = {-1, 1, 0, 0}; static int[] dy = {0, 0, -1, 1}; static BufferedReader br; static StringTokenizer st; static int n, m; static int[][] board; static int[][] dp; public static void main(String[] args) throws IOException{ input(); System.ou..

import java.io.*; import java.util.*; public class SubTotal { static BufferedReader br; static StringTokenizer st; static int[] nums; static int n, s, ans; public static void main(String[] args) throws IOException{ input(); solve(); System.out.println(ans); } static void input() throws IOException { br = new BufferedReader(new InputStreamReader(System.in)); st = new StringTokenizer(br.readLine()..