코테

문제 어른 상어가 마법사가 되었고, 파이어볼을 배웠다. 마법사 상어가 크기가 N×N인 격자에 파이어볼 M개를 발사했다. 가장 처음에 파이어볼은 각자 위치에서 이동을 대기하고 있다. i번 파이어볼의 위치는 (ri, ci), 질량은 mi이고, 방향은 di, 속력은 si이다. 위치 (r, c)는 r행 c열을 의미한다. 격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다. 파이어볼의 방향은 어떤 칸과 인접한 8개의 칸의 방향을 의미하며, 정수로는 다음과 같다. 마법사 상어가 모든 파이어볼에게 이동을 명령하면 다음이 일들이 일어난다. 모든 파이어볼이 자신의 방향 di로 속력 si칸 만큼 이동한다. 이동하는 중에는 같은 칸에 여러 개의 파이..

문제 N행 M열의 표 A가 있고, 표의 각 칸에는 숫자가 하나씩 적혀있다. 연두는 서로 다른 1개 이상의 칸을 선택하려고 하는데, 행의 번호가 선택한 순서대로 등차수열을 이루고 있어야 하고, 열의 번호도 선택한 순서대로 등차수열을 이루고 있어야 한다. 이렇게 선택한 칸에 적힌 수를 순서대로 이어붙이면 정수를 하나 만들 수 있다. 연두가 만들 수 있는 정수 중에서 가장 큰 완전 제곱수를 구해보자. 완전 제곱수란 어떤 정수를 제곱한 수이다. 입력 첫째 줄에 N, M이 주어진다. 둘째 줄부터 N개의 줄에는 표에 적힌 숫자가 1번 행부터 N번 행까지 순서대로 한 줄에 한 행씩 주어진다. 한 행에 적힌 숫자는 1번 열부터 M번 열까지 순서대로 주어지고, 공백없이 모두 붙여져 있다. 출력 첫째 줄에 연두가 만들 수..

배열로 무식하게 푸는 방법과 우선순위 큐를 이용해서 푸는 2가지 방법이 있었다. 첫번째로는 배열을 사용한 풀이인데 나는 우선 이것부터 떠올렸다. 매번 값을 받을 때 마다 sort를 해주어서 홀수번 째 마다 중앙값을 구해주면 됐는데 시간초과가 날줄 알았지만 간당간당하게 통과했다. 아무래도 수열의 크기가 크지 않아서 그랬던 듯 하다. 두번째 풀이는 min-heap과 max-heap을 이용한 풀이였다. 이건 다른 분들의 블로그를 참고해서 푼 문제이다. 확실히 배열로 풀었을 때 보다 최적화 면에서 더 나았다. 어떻게 이걸 바로 떠올리고 풀지라는 신기한 생각을 또 가지게 되었다. (__) 1. 중앙값의 개수 출력 => (N+1) / 2 2. 최대힙과 최소힙의 크기가 같다면 최대힙, 다르다면 최소힙에 값을 넣는다...

25년 간의 수행 끝에 원재는 미래를 보는 능력을 갖게 되었다. 이 능력으로 원재는 사재기를 하려고 한다. 다만 당국의 감시가 심해 한 번에 많은 양을 사재기 할 수 없다. 다음과 같은 조건 하에서 사재기를 하여 최대한의 이득을 얻도록 도와주자. 1. 원재는 연속된 N일 동안의 물건의 매매가를 예측하여 알고 있다. 2. 당국의 감시망에 걸리지 않기 위해 하루에 최대 1만큼 구입할 수 있다. 3. 판매는 얼마든지 할 수 있다. 예를 들어 3일 동안의 매매가가 1, 2, 3 이라면 처음 두 날에 원료를 구매하여 마지막 날에 팔면 3의 이익을 얻을 수 있다. [입력] 첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스 별로 첫 줄에는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘..

스택을 사용한 문제였다. 어느 부분에 자료구조를 사용해야 하는지 감을 잡을 수 있는 문제이다. 우선 연산자, 피연산자, 괄호의 우선순위를 정해준다. '(', ')' = 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..