새발블로그

문제https://www.acmicpc.net/problem/18870풀이방법중복이 없어야해서 Set을 썼는데 정렬이 필요했다...그래서 이전에 스터디할 떄 정리한 TreeSet을 사용하였다그리고 set의 인덱스를 접근하려했는데 해당 시간복잡도가 높아서 시간초과가 났다해쉬맵을 사용하면 N(1)이 가능..풀이import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.par..

문제https://www.acmicpc.net/problem/17298풀이방법i = 0 (탑 높이 6) 스택: 비어있음 → answer[0] = 0 0번 인덱스 push (스택: [0])i = 1 (탑 높이 9) 스택 top(0번, 6) i = 2 (탑 높이 5) 스택 top(1번, 9) > 5 → answer[2] = 2 (1번 인덱스 + 1) 2번 인덱스 push (스택: [1, 2])i = 3 (탑 높이 7) 스택 top(2번, 5) 7 → answer[3] = 2 (1번 인덱스 + 1) 3번 인덱스 push (스택: [1, 3])i = 4 (탑 높이 4)스택 top(3번, 7) > 4 → answer[4] = 4 (3번 인덱스 + 1) 4번 인덱스 push (스택: [1, 3, 4])풀이impo..

문제https://www.acmicpc.net/problem/1697풀이방법1차원 bfs는 dx, dy를 미리 지정하지 못하니까 값이 바뀔 때 동적으로 계산할 수 있도록 !풀이import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { final int MAX_VALUE = 100001; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine());..

문제https://www.acmicpc.net/problem/28018풀이방법그냥 배열 돌려가면서 다 더해주기했는데 시간 초과남time[S] += 1 time[E+1] -=1time 배열에 대한 누적합 적용 --> 각 시각에 사용중인 좌석time[1] += 1 time[6] += -1time[3] += 1 time[7] += -1차분배열시간: 0 1 2 3 4 5 6 7변화량: 0 1 0 1 0 0 -1 -1누적합좌석 수: 0 1 1 2 2 2 1 0풀이import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader b..

문제https://www.acmicpc.net/problem/1967풀이방법트리의 정의에 따라 한번 갈라지면 다시 만날 수 없음트리의 지름은 임의의 노드에서 시작해서, 가장 먼 노드의 위치를 찾고그 노드에서 가장 먼 노드까지의 거리를 찾으면됨풀이import java.io.*;import java.util.*;public class Main { static int maxDist = 0; static int farNode = 0; public static void dfs(List> tree, boolean[] visited, int node, int dist ) { visited[node] = true; if (dist> maxDist) { max..

문제https://www.acmicpc.net/problem/2579풀이방법마지막은 무조건 밟아야 하므로N-2 계단이면 dp[i-2] + score[i]N-1 계단이면 dp[i-3]+dp[i-1]+score[i]위에서 dp[i-3]을 dp[i-2]로 하면 연속 세계단이라 안됨점화식은 dp[i] = max(dp[i-2] + score[i], dp[i-3] + score[i-1] + score[i])풀이import java.util.*;import java.io.*;public class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new Input..

문제https://www.acmicpc.net/problem/21736풀이방법맵 입력받기BFS를 도연이(I부터)BFS이동공간은 O일 때 (조건에 X가 아닐 때 추가해줘야함)BFS중 다음 탐색 경로가 P이면 만날 사람 수 카운팅 해주기카운트수가 0이면 TT 출력풀이import java.util.*;import java.io.*;public class Main { public static int bfs(int N, int M, int[] cur, char[][] campus, boolean[][] visited, int pCnt) { //동 북 서 남 int[] dx = {0, 1, 0, -1}; int[] dy = {1, 0, -1, 0}; Queue..

문제https://www.acmicpc.net/problem/10026풀이방법합쳐져있는 그래프 받기일반사람이 보는 그래프랑 적록색약이 보는 그래프를 만듦각각 BFS풀이import java.util.*;import java.io.*;import java.lang.*;public class Main{ public static void BFS(int N, char[][]map, boolean[][]visited, int[] cur) { int[] dx = {0, -1, 0, 1}; int[] dy = {1, 0, -1, 0}; Queue queue = new ArrayDeque(); queue.add(cur); while (!queue.isE..