Untitled1.class

문제 링크: https://www.acmicpc.net/problem/1655풀이힙 구성에는 priority queue를 사용했다.pqLeft는 최대 힙, pqRight는 최소 힙이다.매번 최대 힙의 peek 값이 중앙값이라는 가정 하에, (pqLeft.size()==pqRight.size()일 때, pqLeft에 offer한다)최대 힙(중앙값 이하), 최소 힙(중앙값 초과)를 이용한다.pqLeft의 size와 pqRight의 size가 같을 때, pqLeft에 offer한다.만약 pqLeft의 peek값이 pqRight의 peek값보다 크다면(원소 정렬이 어긋남), peek 원소를 switch한다.매번 pqLeft.peek() 값을 출력한다.작성한 코드import java.util.*;import ja..

문제 링크: https://www.acmicpc.net/problem/2910풀이문제메시지는 N개의 숫자로 이루어져 있고,숫자는 C 이하이다.창영이는 이 숫자를 자주 등장하는 빈도순으로 정렬하려 한다.만약 두 수 X, Y가 있을 때,X가 Y보다 수열에서 많이 등장하는 경우에는 X가 Y보다 앞에 있어야 한다.만약 등장 횟수가 같다면, 먼저 나온 것이 앞에 있어야 한다.요구하는 것수열이 주어졌을 때, 빈도 정렬을 하시오.떠올린 로직맨 처음에 생각했던 건 단순하게 new Long[C+1] 배열을 만들어서 값을 일일이 다 세는 거였지만 이건 좀 무모하고..숫자 사이즈가 큰 데 비해 실질적으로 숫자 개수는 적으니까 다른 방법을 고안해 보았다. 일단 List numbers와 int[] count, PriorityQ..

문제 링크: https://www.acmicpc.net/problem/5648풀이수 범위 주의.N은 최고 10의 6승까지 가능하지만 입력으로 주어지는 수는 10의 12승까지 가능하기 때문에 변수형을 Long으로 잡아야 한다. 입력 받을 때 주의.맨 첫 번째 원소를 N으로 놓고, 현재 line에 있는 원소를 일단 읽어들이며 idx를 증가시킨 뒤, idx가 N과 일치하다면 while 문에서 벗어난다.작성한 코드import java.util.*;import java.io.*;class Main{ public static void main(String[] args) throws Exception{ BufferedReader br=new BufferedReader(new InputStreamRe..

문제 링크: https://www.acmicpc.net/problem/2146풀이문제섬을 잇는 다리 만들기.한 섬과 다른 섬을 잇는 가장 짧은 다리 하나만 만들기로 했음.나라 크기: N*N (1≤N≤100)0: 바다, 1: 육지이 나라는 여러 섬으로 이루어져 있고, 동서남북으로 육지가 붙어 있다면 섬임.바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다.요구하는 것지도가 주어질 때, 가장 짧은 다리 하나를 놓아 두 대륙을 연결하는 방법을 찾으시오.떠올린 로직각 섬에서 다리를 뻗어 보자.만약 섬이 1, 2, 3 있다고 하면, 꼭 1-2, 1-3이 아니더라도 2-3이 베스트가 될 수도 있기 때문.class Node는 depth를 기반으로 PriorityQueue 내 정렬i번째 섬 visited 처리, ..

문제 링크: https://www.acmicpc.net/submit/2206/95320265풀이문제N*M 행렬0: 이동 가능1: 이동 불가능시작 위치: 1, 1목적지: N, M단, 최단 경로로 이동(시작+도착도 카운트)이동하는 도중에 벽 1개 부수고 가는 게 낫다면, 벽을 1개 까지 부수고 이동해도 됨.동서남북요구하는 것(0, 0) to (N-1, M-1)까지 0만 밟되, 벽 1개 부수고 가는 게 낫다면 부수고 이동한다.이 조건에서, 목적지까지 갈 수 있는 최단 거리?떠올린 로직그럼 있는 벽 1개씩 없애면서 이동해 보면 안됨? ❌Queue을 만들어서, 일일이 벽 정보를 poll() 하며 해당 좌표를 빈 공간(0)으로 바꿔 주었고, 예제는 맞았으나 시간 초과(2%)그럼 Node class에 crashed ..

문제 링크: https://www.acmicpc.net/problem/5427풀이문제매 초마다, 불은 동서남북 방향의 빈 공간으로만 퍼진다.상근이는 동서남북 빈 공간(단, 불이 붙었거나 붙을 예정인 칸으로는 이동 불가)으로 이동 가능.빌딩 지도가 주어졌을 때, 빌딩 탈출 최소 시간은? 빌딩 지도 너비 w, 높이 h1 ≤ w,h ≤ 1,000문자의미.빈 공간#벽@상근이 시작 위치*****불요구하는 것불을 동서남북 빈 공간으로 퍼뜨리기상근이를 위험하지 않은(불 붙어 있거나, 해당 연산에서 불 붙을 예정인 곳 제외) 빈 공간으로 동서남북 중 이동시키기고친 로직마킹된 곳은 어차피 방화할 것이고, 상근이는 그 곳으로 이동하지 못하기 때문에FireInfo를 정의하여 Queue로 관리하되, moveDepth를 사용하..

문제 링크: https://www.acmicpc.net/problem/2493 탑 수: N일직선 위에 높이가 서로 다른 N개의 탑을 왼쪽부터 오른쪽으로 세워 놓았다.각 탑의 꼭대기에 신호를 왼쪽으로 발사하는 레이저 송신기를 설치했다. 탑의 기둥 모두에는 레이저 신호 수신기가 있다.하나의 탑에서 발사된 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다.예를 들어 높이가 6, 9, 5, 7, 4인 5개의 탑이 있다면,높이가 4인 탑5에서 발사한 신호는 높이가 7인 탑4가,높이가 7인 탑4에서 발사한 신호는 높이가 9인 탑2가,높이가 5인 탑3에서 발사한 신호는 높이가 9인 탑2가 수신한다.탑1, 탑2가 발사한 신호는 어떤 탑에서도 수신하지 못한다. (0)N과 탑들의 높이가 주어질 때, 각 탑에서 ..

문제 링크: https://www.acmicpc.net/problem/24445풀이 도출(1h 내로 제한)visited을 indexing 용도로 사용.간선 정렬을 위해 내림차순 pq 사용했음.(메모리 엄청 잡아 먹었음)작성한 코드import java.util.*;import java.io.*;class Main{ static List> graph; static int[] visited; public static void main(String[] args) throws Exception{ BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); graph=new ArrayList(); ..