본문 바로가기

전체 글

 (37)
백준_전화번호 목록_5052 문제 링크 조건 n개의 전화번호 목록 중 임의의 두 번호가 서로 접두사 관계에 있다면 NO (일관성 없음), 없다면 YES (일관성 있음) 출력 접근 방법 정렬 전화번호 목록 문자열 정렬 후 바로 앞 번호가 현재 번호의 접두사인지 확인 n이 크지 않아서 정렬로 푸는게 속도나 메모리에 더 효율적임 트라이 전화번호를 하나씩 Trie 트리에 넣으면서 임의의 두 번호가 서로 접두사 관계에 있는지 확인 솔루션 public class Main { static int t,n;//testcase, 전화번호 개수 static class Node{ Map children; boolean end;//끝번호인지 확인 Node(){ children = new HashMap(); end = false; } } static Nod..
백준_암호만들기_1759 문제 링크 조건 L : 암호 문자 수, 3~15 이하 자연수 C : 암호로 사용할 수 있는 문자 수, 3~15 이하 자연수 완성된 암호는 최소 1개의 모음, 2개의 자음으로 구성되어 있다. 접근 방법 조합 글자 수가 15 이하 => 조합 dfs를 돌려도 시간초과 나지 X 조합 dfs로 문자 완성되면, 암호 조건(모음 1개, 자음 2개 이상) 체크 후 출력 솔루션 public class Main { static char[] alpha; static boolean[] check;//모음 체크를 위한 배열 static int L, C;//암호 길이, 문자 개수 public static void main(String[] args) throws IOException { BufferedReader br = new ..
백준_미세먼지안녕!_17144 문제 링크 조건 R, C : 방 R x C, 6~50 이하 자연수 현재 칸에서 4방으로 먼지가 퍼질 때, (A / 5)만큼 퍼지고 소수점 이하는 무시함 접근 방법 확산은 미세먼지가 있는 모든 칸에서 동시에 발생 plus 배열에 모든 칸에서 퍼지는 양 누적 후 한 번에 map에 더해줌 공기청정기 작동 => 위쪽은 반시계, 아래쪽은 시계방향 순환 rotate 배열에 위쪽, 아래쪽 확산 방향 저장 후 순서에 맞게 확산시켜줌 솔루션 public class Main { static int R, C, T;//map R*C, 시간 T초 static int[][] map, plus; static int[] dr = {0,-1,0,1}; static int[] dc = {1,0,-1,0}; static int[][] r..
백준_욕심쟁이판다_1937 문제 링크 조건 n : 대나무 숲 크기, 1~500 이하 현재 칸보다 대나무가 더 많은 칸으로만 이동 가능 접근 방법 메모이제이션 활용 memo 배열에 현재 칸(i, j)에서 출발했을 때 최대 몇일 살아남을 수 있는지 저장하며 시간을 단축 솔루션 public class Main_1937_욕심쟁이판다 { static int N; static int[][] map, memo; static int K;//판다가 살아남을 수 있는 day 수 static int[] dr = {-1,1,0,0}; static int[] dc = {0,0,-1,1}; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedR..
백준_PuyoPuyo_11559 문제 링크 조건 게임 맵 크기 : 12 X 6 같은 색 뿌요가 4개 이상 인접해 있으면 터짐 => 한 턴 마다 연쇄 수 ++ 접근 방법 시키는 대로 함 while문 돌리며, 같은 색 뿌요가 4개 이상 인접해 있는지 dfs로 체크 cnt가 4개 이상이면 터뜨림 한 턴이 마무리되면 뿌요가 터져서 비워진 공간 전부 채워주고 연쇄 수를 1 더함 솔루션 public class Main_11559_PuyoPuyo { static int R,C; static char[][] map; static boolean[][] check; static int chain, cnt; static int[] dr = {-1,1,0,0}; static int[] dc = {0,0,-1,1}; public static void main..
백준_비숍_1799 문제 링크 조건 N : 체스판 크기, 1~10 이하 자연수 비숍은 사방 대각선으로 공격 가능 접근 방법 체스판의 검은 영역 과 흰 영역 을 분리해 생각 큰 덩어리를 둘로 분리해 작은 덩어리 두 번 계산 시간복잡도 영역을 분리하지 않은 경우 : O(2 ^ (N*N)) => 각각의 체스칸마다(N*N개) 비숍을 놓을 지 말지 선택(2가지) 영역을 분리한 경우 : O(2 ^ (N/2 * N/2)) => 각각의 체스칸마다(N/2*N/2개) 비숍을 놓을 지 말지 선택(2가지) * 2(흰 영역, 검은 영역 두 번 계산) 솔루션 public class Main_1799_비숍 { static int N, size, max;//map N*N static int[][] map;//체스판 static int[] dr = {-..
백준_도로검문_2307 문제 링크 조건 N : 도시 개수 M : 도로 개수(양방향) 류원룡이 검문할 수 있는 도로는 단 한개임 접근 방법 dijkstra로 전체 도로를 기준으로 최단거리 구함 거쳐온 루트를 path 배열에 저장 path를 활용해 최단 경로에 포함되는 도로 중 하나씩 삭제하며 최대지연 시간을 구함 솔루션 public class Main { static int N,M;//지점 수, 도로 수 static List[] adj; static int[] dij; static int[] path;//최단 경로 저장 static final int max = Integer.MAX_VALUE; static PriorityQueue pq; public static void main(String[] args) throws IOExc..
백준_파티_1238_Dijkstra&Floyd-Warshall 문제 링크 조건 N : 학생 수, 1~1000 이하 M : 단방향 도로 정보, 1~10,000 이하 X : 파티를 여는 학생 번호 접근 방법 Floyd-Warshall(플로이드 워셜) O(N3) 시간복잡도(오래걸림) 모든 노드에서 각각의 노드로 이동할 때 모든 최단거리를 구함 Dijkstra 단방향 값어치 정보가 주어진다 => dijkstra를 두 번 진행 X번 학생 집으로 들어오는 방향에 대한 dijkstra (각 친구들이 파티에 올 때 걸리는 최단시간) X번 학생 집에서 나가는 방향에 대한 dijkstra (각 친구들이 집으로 돌아갈 때 걸리는최단시간) 솔루션 Floyd-Warshall => 31152KB, 1884ms public class Main {//floyd-warshall static in..

티스토리툴바