출처 HackerRank No Prefix Set 문제 설명 주어진 단어 집합 중 Prefix(접두사)가 존재하는 단어가 있으면 BAD SET와 함께 처음으로 접두사가 발생한 단어를 출력합니다. 그런 단어가 없으면 GOOD SET을 출력합니다. 접근 완전탐색 가장 단순한 접근은 각 단어마다 나머지 단어들을 돌면서 prefix가 존재하는지 확인하는 것입니다. 문제에서 주어진 단어의 수는 최대 10^5 이므로, O(N^2)1 이상의 알고리즘을 사용할 수 없습니다. TRIE Trie2 자료구조를 통해 단어들의 탐색을 최적화할 수 있습니다. Trie 자료구조의 형태는 다음과 같습니다. Trie 자료구조 형태 ...
출처 HackerRank New Year Chaos 문제 설명 영문 사이트이므로 문제를 간단히 설명하겠습니다. 롤러코스터에 승객들이 n명 탑승중입니다. 각자는 탑승 순서대로 번호를 부여받습니다. 롤러코스터 승객들은 앞 사람과 최대 두 번까지 순서를 변경할 수 있습니다. bribe라는 단어를 처음 보고 해석이 안됐는데 ‘매수하다’ 라는 뜻으로, 앞 사람 자리를 매수한다는 뜻인 것 같습니다. 이렇게 변경된 롤러코스터의 상태가 큐로 주어집니다. 만약 3번 이상 변경한 사람이 있으면 “Too Chaotic"이라는 문자열을 출력합니다. 그런 사람이 없다면 승객들의 변경 횟수를 출력합니다. 접근 완전 탐색? 큐의 크기(n)가 최대 10^5이므로 O(N^2) 로직은 실행이 불가능하므로 완전탐색은 불가능합니다. Greedy 현재 승객이 타고있는 지점(idx)과 갖고 있는 번호의 관계를 통해 어떻게 변경이 이루어졌는지 유추해볼 수 있습니다. ...
출처 https://www.acmicpc.net/problem/16236 접근 알고리즘 시작지점부터 가장 가까운 물고기부터 탐색합니다. 문제 조건에서 주어진 물고기를 선택하는 기준을 만족하기 위해, Heap1에 다음 물고기를 넣어 정렬하였습니다. 다음 물고기가 먹을 수 있는 물고기라면, 해당 위치를 시작점으로 다시 BFS를 수행합니다. 시간복잡도 고민 BFS로 물고기를 먹으러 이동하면서 걸리는 시간 : O(N^2) 이동하면서 물고기를 정렬하는 시간(Priority Queue 사용 시) : O(NlogN) N = 20 이므로 시간복잡도 내 충분히 가능하다고 판단했습니다. 유의사항 PriorityQueue를 정렬할 때, Integer의 유틸리티 메서드인 compare()를 활용하면 좋다고 합니다.2 물고기를 먹은 뒤 해당 위치에서 BFS를 다시 수행하기 위해 방문 배열을 초기화하는 로직이 필요합니다. 풀이 package solving; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; /* * [조건] * 시간 제한 : 2초 / 메모리 제한 512MB * [풀이] * 오른쪽 아래부터 역으로 공간을 돌면서 가장 가까운 물고기의 위치를 확인한다.(N^2) * 해당 물고기를 먹으러 이동하면서 걸리는 시간을 측정한다.(N^2) * 더이상 이동할 수 없거나, 모든 칸이 빌때까지 이를 반복한다(N^2) * => N^6 = 20^6 = 32 x 10^6 이므로 시간복잡도 내 가능 * 시작지점부터 가장 가까운 물고기를 탐색한다. * 해당 지점까지 bfs로 이동하여 해당 지점이 나오면 걸린 시간을 현재시간에 더한다. * 더이상 이동이 불가능하다면 현재 시간을 출력한다. * 이동이 가능하다면 먹은 횟수를 더하고, 먹은 횟수가 상어의 크기만큼 쌓이면 상어 크기를 1 늘린다. */ public class bj_16236_아기_상어 { static int N, eatCount, size = 2; static int[] start; static int[][] space; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine()); space = new int[N][N]; start = new int[2]; for (int i = 0; i < N; i++) { StringTokenizer st = new StringTokenizer(br.readLine()); for (int j = 0; j < N; j++) { int now = Integer.parseInt(st.nextToken()); if (now == 9) start = new int[]{i, j}; space[i][j] = now; } } System.out.println(bfs()); } // 먹을 수 있는 물고기가 더 없을떄까지 bfs 이동 static int[] dr = {-1, 0, 0, 1}; static int[] dc = {0, -1, 1, 0}; private static int bfs() { boolean[][] visited = new boolean[N][N]; // 우선순위 큐 : 거리 > 위 > 왼쪽 순으로 내부 정렬 PriorityQueue<int[]> q = new PriorityQueue<>((o1, o2) -> { if (o1[2] != o2[2]) return Integer.compare(o1[2], o2[2]); // Integer.compare() 메서드 활용 if (o1[0] != o2[0]) return Integer.compare(o1[0], o2[0]); return Integer.compare(o1[1], o2[1]); }); int ret = 0; q.offer(new int[] {start[0], start[1], 0}); visited[start[0]][start[1]] = true; while (!q.isEmpty()) { int[] now = q.poll(); // 자신보다 작은 물고기를 만났을 때 : 해당 물고기를 먹은 후 큐를 비우고 다시 bfs 시작 int fish = space[now[0]][now[1]]; if (fish != 0 && fish < size) { if (++eatCount >= size) { size++; eatCount = 0; } // 이동시간 갱신 ret += now[2]; // bfs 초기화 + 방문배열 초기화 q.clear(); q.offer(new int[]{now[0], now[1], 0}); for (int j = 0; j < N; j++) Arrays.fill(visited[j], false); visited[now[0]][now[1]] = true; // 공간 변화 : 아기상어 위치 이동 + 최초위치 아기상어 칸 비우기 space[now[0]][now[1]] = 9; space[start[0]][start[1]] = 0; start = new int[]{now[0], now[1]}; continue; } for (int i = 0; i < 4; i++) { int nr = now[0] + dr[i]; int nc = now[1] + dc[i]; if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue; if (visited[nr][nc] || space[nr][nc] > size) continue; visited[nr][nc] = true; q.offer(new int[] {nr, nc, now[2] + 1}); } } return ret; } } 결과 ...
출처 https://www.acmicpc.net/problem/2573 접근 각 칸이 10이하이고 전체 칸은 10,000이므로 빙산을 모두 녹이려면 10 _ 10,000 _ 10,000이지만, 네 변이 노출되면 금방 사라지므로 완전탐색이 가능하다고 판단했습니다. 매 회마다 빙산을 녹이고, 빙산을 bfs(dfs)로 탐색해서 두 덩어리가 있는지 확인한다. 모든 빙산이 다 녹았지만 2개로 분리되지 않는 경우를 주의한다.1 풀이 package solving; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; /* * [조건] * 시간제한 : 1초, 메모리 제한 : 256MV * 이차원 배열의 크기가 300^2 이하이며 전체 칸의 개수는 10,000개 이하, 각 칸의 크기는 10 이하 * [풀이] * 각 칸이 10이하이고 전체 칸은 10,000이므로 빙산을 모두 녹이려면 10 * 10,000 * 10,000이지만, 네 변이 노출되면 금방 사라지므로 완전탐색 * 매 회마다 빙산을 녹이고, 빙산을 bfs로 탐색해서 두 덩어리가 있는지 확인한다. */ public class bj_2573_빙산 { static int N, M, count; static int[] dr = {0, 0, 1, -1}; static int[] dc = {1, -1, 0, 0}; static int[][] pole; public static void main(String[] args) throws IOException { // 초기화 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); pole = new int[N][M]; for (int i = 0; i < N; i++) { st = new StringTokenizer(br.readLine()); for (int j = 0; j < M; j++) pole[i][j] = Integer.parseInt(st.nextToken()); } count = 0; // 빙산을 녹이면서 두 개로 분리되는지 확인 while (!isFinished()) { melt(); count++; } System.out.println(count); } // 빙산 녹이기(녹은 값을 별도의 리스트에 저장 후 마지막에 반영) private static void melt() { List<int[]> melted = new ArrayList<>(); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (pole[i][j] == 0) continue; int now = pole[i][j]; for (int k = 0; k < 4; k++) { int nr = i + dr[k]; int nc = j + dc[k]; if (nr < 0 || nr >= N || nc < 0 || nc >= M || pole[nr][nc] != 0) continue; now --; } if (now < 0) now = 0; melted.add(new int[] {i, j, now}); } } for (int[] now : melted) pole[now[0]][now[1]] = now[2]; } // 2개로 분리되었는지 확인(BFS) private static boolean isFinished() { // 두 덩이로 분리되지 않고 모든 빙산이 녹았을때 예외처리(중요) int sum = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { sum += pole[i][j]; } } if (sum == 0) { count = 0; return true; } // BFS 초기화 Queue<int[]> q = new ArrayDeque<>(); boolean[][] isVisited = new boolean[N][M]; boolean isOneBlock = false; // 한 얼음을 만날때까지 확인 for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (!isVisited[i][j] && pole[i][j] != 0) { // 이미 얼음을 만났음에도 다시 만난 경우 true(빙산이 2개로 나눠짐) if (isOneBlock) return true; isOneBlock = true; // BFS를 돌면서 방문처리 q.offer(new int[] {i, j}); isVisited[i][j] = true; while (!q.isEmpty()) { int[] now = q.poll(); for (int k = 0; k < 4; k++) { int nr = now[0] + dr[k]; int nc = now[1] + dc[k]; if (nr < 0 || nr >= N || nc < 0 || nc >= M || pole[nr][nc] == 0 || isVisited[nr][nc]) continue; isVisited[nr][nc] = true; q.offer(new int[] {nr, nc}); } } } } } return false; } } 결과 ...
출처 https://www.acmicpc.net/problem/1753 접근 각 정점에서 다른 정점으로의 최솟값을 다익스트라1를 통해 구합니다. 정점으로부터 최단거리의 간선으로만 이동하기 때문에 O(ElogV) ≈ 1,200,0002으로 모든 간선을 확인하는 것이 가능합니다. 탐색하는 간선 개수를 최적화하기 위해 LinkedList로 저장합니다.3 문제에서 주어진 예제를 그래프로 표현했습니다. 그래프 1 2 3 4 5 초기화 0 INF INF INF INF 1 -> 2, 3 0 2 3 INF INF 2 -> 3, 4 0 2 3 7 INF 3 -> 4 0 2 3 7 INF 5 -> 1 0 2 3 7 INF 위와 같이 거리 배열을 초기화한 후, 각 정점의 간선들을 탐색하며 배열을 채워나갑니다. 이 때, Greedy 알고리즘인 다익스트라가 도입되는데, 각 지점에서 가중치의 최솟값인 경로만 선택하면서 목표지점까지 이동하면 최소 경로를 구할 수 있다는 것입니다. ...