heemang.dev

1. 문제https://www.acmicpc.net/problem/21939 2. 코드Problem의 정렬 조건 1. 난이도가 낮은 순으로 정렬한다.2. 난이도가 같다면 문제 번호가 낮은 순으로 정렬한다.TreeSet을 사용하여 Problem 저장 시에 정렬이 될 수 있도록 한다.TreeSet은 first(), last()를 사용하여 첫 번째 요소와 마지막 요소에 접근할 수 있다. (양방향 접근)public class Main { static int N, M; static TreeSet set = new TreeSet(); static Map map = new HashMap(); // {문제 번호, 문제} public static void main(String[] args) thro..

1. 문제https://www.acmicpc.net/problem/2493 2. 풀이N = 500,000이므로 시간 복잡도 O(N^2)가 걸리는 코드를 작성한다면 시간 초과가 발생한다.이 문제는 시간 복잡도 O(N)으로 풀 수 있어야 한다.현재 건물(i)에서 왼쪽으로 레이저를 쏜다는 것은 (j 그렇다면 (j 그러나 for문을 사용하여 (0, i - 1) 건물을 모두 탐색한다면 시간 복잡도 O(N^2)이 된다. 이 문제는 스택을 사용하여 최근에 접근한 건물부터 탐색하여 해결할 수 있다.스택의 조건은 다음과 같다.현재 건물보다 높은 건물이 나올 때까지 스택에서 건물을 제거한다.스택 최상단에 있는 건물이 현재 건물보다 높은 건물이다.스택이 비어있다면 현재 건물보다 높은 건물이 없다는 것이다.예를 들어, 높이가..

1. 문제https://www.acmicpc.net/problem/21318 2. 코드누적 합(prefixSum)을 활용하여 해결하였다.피아노의 단계를 arr 배열에 저장한다.0 prefixSum 배열을 사용하여, 1번 피아노부터 현재 피아노까지의 실수 횟수를 기록한다.x 만약 prefixSum을 사용하지 않는다면 M번동안 (x, y) 받고 x prefixSum을 사용하여 x prefixSum[y - 1] : 범위 조건으로 y는 포함하지 않는다고 명시되어 있다.prefixSum[x - 1] : (1번 피아노부터 x번 피아노까지의 실수 합) - (1번 피아노부터 ~ x - 1번 피아노까지의 실수 합)public class Main { static int N, M; static int[] arr..

1. 문제https://www.acmicpc.net/problem/17132. 코드문제 푸는 것에 지쳐서 설명은 주석으로 대체한다..import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.HashMap;import java.util.Map;public class Main { static int N; static int M; static int[] persons; // 입력으로 받은 사람 번호 static Map pickPersons; // 사진이 등록된 사람, static int[] pickPers..

1. 문제https://www.acmicpc.net/problem/5212 2. 문제주의할 점 : 배열의 범위를 벗어나는 경우 바다(.)로 처리해야 한다.50년 후 지도 만들기lands 배열 : 50년 전의 지도newLands : 50년 후의 지도lands 배열을 탐색하면서 땅(X)으로 되어 있는 위치(x, y)를 찾는다.해당 좌표에서 인접한 상하좌우 좌표를 탐색하면서 주변에 바다(.)가 몇 곳이 있는지 개수(count)를 구한다. 단, 상하좌우 탐색 과정에서 배열의 범위를 벗어나는 경우 바다(.)이다.상하좌우 탐색을 마치고 땅 주변에 바다가 3곳 이상(count >= 3)이라면, 현재 위치(x, y)는 50년 후에 바다로 잠긴다. 이를 newLands[y][x]에 저장하면 된다.static void l..