/*
* 숫자가 주어질 때마다 위치 찾아 삽입.
* 삽입 위치 찾는건 이분탐색으로.
* 중간값은 짝수->len/2-1 홀수->len/2
*/
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder sb;
static int N;
static List<Integer> list;
public static void main(String[] args) throws IOException {
init();
for (int i=0; i<N; i++) {
int newNum = Integer.parseInt(br.readLine());
int targetIdx = binarySearch(0, list.size()-1, newNum);
list.add(targetIdx, newNum);
int midIdx = list.size()/2;
if (list.size()%2 == 0) midIdx -= 1;
sb.append(list.get(midIdx)).append('\n');
}
System.out.println(sb);
}
private static int binarySearch(int s, int e, int target) {
int mid = (s+e)/2;
if (s > e) {
return s;
}
int midNum = list.get(mid);
if (midNum == target) {
return mid;
} else if(midNum < target) {
return binarySearch(mid+1, e, target);
} else {
return binarySearch(s, mid-1, target);
}
}
private static void init() throws IOException {
sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
list = new ArrayList<>();
}
}
결론적으로 정답은 맞았으나, 실행속도가 아쉬웠다.
개선 사항
원인
기존 내 코드의 실행속도가 느렸던 원인을 생각해볼 때,
ArrayList를 사용해 삽입하는 방식이 주요 원인이라고 생각했다.
✨ Javadoc (ArrayList의 add 메서드에 대한 내용 발췌)
위 javadoc 내용을 보면 어레이리스트도 결국 배열이기 때문에,
삽입을 하려면 결국 배열처럼 해당 인덱스를 비우기 위해 이후 숫자를 모두 하나씩 미루고,
비워진 자리에 삽입하는 로직이기 때문에 배열 전체를 순회해야 한다.
사실상 시간 복잡도는 O(N2) 인 셈인 것이다.
그래서 대안으로 힙정렬을 생각했다.
PriorityQueue의 정렬방식이기도 한 힙정렬은 시간복잡도가 O(NlogN)으로 더 효율적이다.
개선 코드
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder sb;
static int N;
static PriorityQueue<Integer> maxHeap; // 최대힙 (작은 수들의 절반)
static PriorityQueue<Integer> minHeap; // 최소힙 (큰 수들의 절반)
public static void main(String[] args) throws IOException {
init();
for (int i = 0; i < N; i++) {
int x = Integer.parseInt(br.readLine());
insert(x);
sb.append(maxHeap.peek()).append('\n'); // 항상 아래 중앙값 출력
}
System.out.print(sb);
}
private static void init() throws IOException {
sb = new StringBuilder();
N = Integer.parseInt(br.readLine().trim());
maxHeap = new PriorityQueue<>(Collections.reverseOrder());
minHeap = new PriorityQueue<>();
}
private static void insert(int n) {
// maxheap을 우선으로 담기
if (maxHeap.isEmpty() || n <= maxHeap.peek()) maxHeap.offer(n);
else minHeap.offer(n);
if (maxHeap.size() < minHeap.size()) maxHeap.offer(minHeap.poll());
if (maxHeap.size() > minHeap.size() + 1) minHeap.offer(maxHeap.poll());
if (!minHeap.isEmpty() && maxHeap.peek() > minHeap.peek()) {
int a = maxHeap.poll(), b = minHeap.poll();
maxHeap.offer(b);
minHeap.offer(a);
}
}
}
개선 후 (30% 속도 향상)
배운점
기존에는 매 입력마다 정렬된 리스트에 이분 탐색으로 삽입했는데, 삽입 과정에서 배열의 뒤 원소들을 한 칸씩 밀어야 해서 O(N) 시간이 소요되었다. 따라서 입력이 많아질수록 전체 시간 복잡도가 O(N^2)까지 치솟아 성능상 한계가 있었다.
이를 힙(PriorityQueue) 두 개로 관리하는 방식으로 바꾸면서, 각 입력마다 삽입·삭제 연산을 O(log N)에 처리할 수 있었고, 전체 시간 복잡도는 O(N log N)으로 크게 개선되었다.
다만, 다른 사람들의 200ms대 풀이를 보니 똑같이 힙을 활용하더라도 PriorityQueue 대신 배열 기반으로 직접 힙 연산을 구현해 오버헤드를 줄인 경우가 있었다. 이를 통해 단순히 자료구조를 교체하는 것만으로는 충분하지 않고, 문제 상황에 맞는 세밀한 최적화와 구현 방식의 차이가 성능을 크게 좌우한다는 점을 배울 수 있었다.
N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.
아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.
아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.
아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.
더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.
아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.
아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.
공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.
0: 빈 칸
1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
9: 아기 상어의 위치
내 정답 코드
내가 생각한 로직은,
1. 지도에서 현황을 관리할 map 배열(int[][] map), 빠르게 물고기 위치에 접근하기 위한 fishes배열(ArrayList<int[]>[] fishes), 상어의 위치, 크기, 먹은 물고기 수를 관리하기 위한 shark 배열(int[] shark)을 선언하여 관리한다.
그리고 엄마 상어를 찾기 전까지 아래 작업을 반복한다.
1. 가장 가까운 타겟 선택
- fishes 배열을 순회하며, 나보다 크기가 작은 물고기들과의 거리를 각각 bfs 작업으로 탐색한다.
- 가장 가까우면서, 좌측 상단에 있는 물고기를 타겟으로 선정한다.
2. 선택된 타겟이 없으면 반복 종료
3. 해당 타겟으로 이동하여 잡아먹기
- map에서 상어 위치 이동
- shark배열 좌표값, 먹은 물고기 수, 크기 값 조정
- fishes리스트에서 해당 물고기 제거
4. 이동하는 데 필요한 시간만큼 소요시간에 가산
public class Main {
static StringBuilder sb;
static int N;
// 0: r, 1: c, 2: 크기, 3: 먹은 물고기 수
static int[] shark = new int[4];
// 0: r, 1: c, 2: 크기, 3: 물고기 리스트 index
static int[] target = new int[4];
static int[][] map;
static boolean[][] visited;
static ArrayList<int[]>[] fishes;
public static void main(String[] args) throws IOException {
init();
System.out.println(simulation());
}
// 시뮬레이션
private static int simulation() {
int time = 0;
while (true) {
// 가장 가까운 타겟 선택
// => 상어보다 크기 작으면서 가장 가까운 물고기
Arrays.fill(target, 0);
int min = 401;
for (int i = 1; i < shark[2] && i < 7; i++) {
for (int j=0; j<fishes[i].size(); j++) {
int[] fish = fishes[i].get(j);
int timeTaken = bfs(fish[0], fish[1]);
if (timeTaken <= min) {
if (timeTaken == min) {
if (target[0] < fish[0])
continue;
else if (target[0] == fish[0]) {
if (target[1] < fish[1])
continue;
}
}
target[0] = fish[0];
target[1] = fish[1];
target[2] = i;
target[3] = j;
min = timeTaken;
}
}
}
// 타겟이 없으면 종료
if (target[2] <= 0) {
return time;
}
// 타겟 있으면 해당 위치 이동 후 시간 가산
// 물고기 먹기
shark[3] += 1;
fishes[target[2]].remove(target[3]);
// 상어 위치 이동
map[shark[0]][shark[1]] = 0;
map[target[0]][target[1]] = 9;
shark[0] = target[0];
shark[1] = target[1];
// 상어 크기 조정
if (shark[3] >= shark[2]) {
shark[2] += 1;
shark[3] = 0;
}
// 시간 가산
time += min;
}
}
static int[] dr = { -1, 1, 0, 0 };
static int[] dc = { 0, 0, -1, 1 };
private static int bfs(int targetR, int targetC) {
visited = new boolean[N][N];
Queue<int[]> q = new ArrayDeque<>();
// 시작지점 큐에 삽입 & 방문체크
q.offer(new int[] { shark[0], shark[1] });
visited[shark[0]][shark[1]] = true;
int size = 1;
int cnt = 0;
while (!q.isEmpty()) {
for (int i = 0; i < size; i++) {
int[] curr = q.poll();
// 목표지점 도착 시 종료
if (curr[0] == targetR && curr[1] == targetC) {
return cnt;
}
// 사방탐색
for (int dir = 0; dir < 4; dir++) {
int nr = curr[0] + dr[dir];
int nc = curr[1] + dc[dir];
// 이미 방문했거나, 범위 밖이거나, 상어보다 크기가 큰 물고기면 패스
if (nr < 0 || nr >= N || nc < 0 || nc >= N)
continue;
if (visited[nr][nc])
continue;
if (map[nr][nc] > shark[2])
continue;
q.offer(new int[] { nr, nc });
visited[nr][nc] = true;
}
}
cnt += 1;
size = q.size();
}
return Integer.MAX_VALUE;
}
private static void init() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
sb = new StringBuilder();
// 물고기 크기별 좌표값 저장 배열
fishes = new ArrayList[7];
for (int i = 1; i <= 6; i++) {
fishes[i] = new ArrayList<>();
}
N = Integer.parseInt(br.readLine());
map = new int[N][N];
for (int r = 0; r < N; r++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int c = 0; c < N; c++) {
int n = Integer.parseInt(st.nextToken());
map[r][c] = n;
if (1 <= n && n <= 6) {
fishes[n].add(new int[] { r, c });
}
if (n == 9) {
shark[0] = r;
shark[1] = c;
shark[2] = 2;
}
}
}
}
}
개선 사항
생각해보니, 모든 물고기를 대상으로 bfs를 돌릴 필요가 없었다.
상어의 현위치를 중심으로, bfs 탐색을 하다가 물고기가 걸리면, 그것을 타겟으로 하면 됐다.
결국 bfs를 1번만 하면 훨씬 시간을 단축할 수 있을 거라 생각했다.
주요 변경
우선순위 큐 사용
노드(Node)를 거리 → 행 → 열 순으로 정렬하도록 구현.
우선순위가 가장 높은(가장 가까운 + 위쪽 + 왼쪽) 물고기부터 바로 선택 가능하다.
탐색 리셋 구조
물고기를 먹은 순간 pq.clear() + visited 배열 재생성하여 shark의 현위치를 기준으로 새로 탐색한다.
상어 위치에서 새롭게 탐색을 시작하므로, 불필요한 경로 계산을 방지한다.
public class Main {
static StringBuilder sb;
static int N;
// shark: [0]=r, [1]=c, [2]=size, [3]=eaten
static int[] shark = new int[4];
static int[][] map;
public static void main(String[] args) throws IOException {
init();
System.out.println(simulation());
}
static class Node implements Comparable<Node> {
int r, c, dist;
Node(int r, int c, int dist) {
this.r = r; this.c = c; this.dist = dist;
}
@Override
public int compareTo(Node n) {
if (this.dist != n.dist) return Integer.compare(this.dist, n.dist);
if (this.r != n.r) return Integer.compare(this.r, n.r);
return Integer.compare(this.c, n.c);
}
}
// 상, 좌, 하, 우 (제시 코드의 dirs와 동일 순서)
static int[] dr = {-1, 0, 1, 0};
static int[] dc = { 0,-1, 0, 1};
// 제시 코드의 playGame() 로직을 네 simulation() 틀에 이식
private static int simulation() {
int time = 0;
// 탐색 시작 상태
PriorityQueue<Node> pq = new PriorityQueue<>();
int[][] visited = new int[N][N];
visited[shark[0]][shark[1]] = 1;
pq.offer(new Node(shark[0], shark[1], 1));
while (!pq.isEmpty()) {
Node cur = pq.poll();
// 먹을 수 있는 물고기를 만났다면 즉시 먹기
if (map[cur.r][cur.c] != 9 && map[cur.r][cur.c] != 0 && map[cur.r][cur.c] < shark[2]) {
time += (cur.dist - 1);
// 상어 위치/맵 갱신
map[shark[0]][shark[1]] = 0;
map[cur.r][cur.c] = 9;
shark[0] = cur.r;
shark[1] = cur.c;
// 먹은 수/크기 갱신
shark[3] += 1;
if (shark[3] == shark[2]) {
shark[3] = 0;
shark[2] += 1;
}
// 탐색 리셋
pq.clear();
visited = new int[N][N];
visited[shark[0]][shark[1]] = 1;
pq.offer(new Node(shark[0], shark[1], 1));
continue; // 다음 먹이 탐색
}
// 사방 확장
for (int d = 0; d < 4; d++) {
int nr = cur.r + dr[d];
int nc = cur.c + dc[d];
if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
if (visited[nr][nc] > 0) continue;
if (map[nr][nc] > shark[2]) continue; // 더 큰 물고기는 통과 불가
visited[nr][nc] = visited[cur.r][cur.c] + 1;
pq.offer(new Node(nr, nc, visited[nr][nc]));
}
}
return time;
}
private static void init() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
sb = new StringBuilder();
N = Integer.parseInt(br.readLine());
map = new int[N][N];
for (int r = 0; r < N; r++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int c = 0; c < N; c++) {
int n = Integer.parseInt(st.nextToken());
map[r][c] = n;
if (n == 9) {
shark[0] = r;
shark[1] = c;
shark[2] = 2; // 초기 크기
}
}
}
}
}
개선 전
개선 후 (약 5배 이상 빨라짐!)
배운점
기존에는 물고기마다 BFS를 수행해 한 번 이동할 때마다 많은 탐색이 필요했지만, 이를 BFS 한 번으로 줄여 시간 복잡도를 크게 개선할 수 있었다.
하지만 BFS 한 번으로 고쳐도 처음에는 PriorityQueue를 무작정 사용해 큐에 모든 탐색 결과를 삽입하면서 매번 정렬이 발생해 오히려 시간 초과가 났다.
따라서 PQ에 불필요하게 많은 데이터를 넣지 않고, 최소한으로 삽입되도록 로직을 구성해야 했다. 즉, BFS 레벨 단위로 탐색하고 같은 거리 내에서만 후보를 관리하면서 먹을 수 있는 물고기를 찾자마자 탐색을 종료하는 방식으로 바꿔야 효율적으로 해결할 수 있었다.
해당 노드의 모든 인접 노드에 대해, 현재노드까지의 거리 + 간선 가중치가 더 짧으면 갱신한다.
모든 노드를 방문할 때까지 2~3 과정을 반복한다.
예를 들어 노드 5개, 시작 노드 1일 때의 dist 초기 상태는 다음과 같다.
dist = [0, 2, INF, 1, INF] (1번에서 직접 연결된 값)
1번 방문 → 2번과 4번 거리 갱신
다음으로 거리가 짧은 2번 방문 → 3번 거리 갱신
다음으로 4번 방문 → 5번 거리 갱신
이런 식으로 한 시작점에서의 최단거리를 완성한다.
시간복잡도
플로이드 워셜 : for문을 3번 돌기 때문에, O(N^3) 이다.
다익스트라 : 간선 수가 E라고 할 때, O(E logN)가 된다.
따라서 간선 수가 많을 수록 다익스트라는 불리해지고,
노드 수가 많을수록 플로이드 워셜이 불리해진다.
백준 14938 문제 예시 코드
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder sb = new StringBuilder();
static int N, M, R, max;
static final int INF = Integer.MAX_VALUE;
static int[] items;
static int[][] dist;
static int[][] dist_dijkstra;
static ArrayList<Site>[] adjList;
static class Site {
int v;
int l;
public Site(int v, int l) {
super();
this.v = v;
this.l = l;
}
}
public static void main(String[] args) throws IOException {
init();
long start = System.currentTimeMillis();
// 플로이드 워셜
floydWarshall();
// 다익스트라
dijkstra();
// 낙하위치별 최단거리 구하기
max = 0;
for (int i=1; i<=N; i++) {
int sum = items[i];
for (int j=1; j<=N; j++) {
if (i==j) continue;
if (dist_dijkstra[i][j] <= M) {
// if (dist[i][j] <= M) {
sum += items[j];
}
}
max = Math.max(max, sum);
}
System.out.println(max);
long end= System.currentTimeMillis();
System.out.println(end - start);
}
private static void floydWarshall() {
// i에서 j로 가는 모든 경로에서 k를 거쳐갈 때 최단거리
// 양방향 통행 => (i>j) == (j>i) 이므로 중복 계산 줄임
for (int k=1; k<=N; k++) {
for (int i=1; i<=N; i++) {
if (dist[i][k] == INF) continue;
for (int j=i+1; j<=N; j++) {
if (i==j) continue;
if (dist[k][j] == INF) continue;
if (dist[i][j] > dist[i][k]+dist[k][j]) {
dist[i][j] = dist[i][k]+dist[k][j];
dist[j][i] = dist[i][j];
}
}
}
}
}
static void dijkstra() {
dist_dijkstra = new int[N + 1][N + 1];
final int INF = Integer.MAX_VALUE;
for (int s = 1; s <= N; s++) {
Arrays.fill(dist_dijkstra[s], INF);
dist_dijkstra[s][s] = 0;
// (정점, 현재까지의 거리)로 사용
java.util.PriorityQueue<Site> pq = new java.util.PriorityQueue<>((a, b) -> Integer.compare(a.l, b.l));
pq.offer(new Site(s, 0));
while (!pq.isEmpty()) {
Site cur = pq.poll();
int u = cur.v;
int d = cur.l;
// 이미 더 짧은 경로가 있으면 스킵
if (d > dist_dijkstra[s][u]) continue;
// 인접 정점 완화
for (Site nx : adjList[u]) {
int v = nx.v;
int w = nx.l;
// d + w 연산 전 INF 가드 (오버플로 방지용)
if (d != INF && d + w < dist_dijkstra[s][v]) {
dist_dijkstra[s][v] = d + w;
pq.offer(new Site(v, dist_dijkstra[s][v]));
}
}
}
}
}
private static void init() throws IOException {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
R = Integer.parseInt(st.nextToken());
items = new int[N+1];
adjList = new ArrayList[N+1];
for (int i=1; i<=N; i++) {
adjList[i] = new ArrayList<>();
}
// 지역별 아이템 수 입력
st= new StringTokenizer(br.readLine());
for (int i=1; i<=N; i++) {
items[i] = Integer.parseInt(st.nextToken());
}
// 플로이드 워셜용 배열
dist = new int[N+1][N+1];
for (int i=1; i<=N; i++) {
for (int j=1; j<=N; j++) {
if (i==j) continue;
dist[i][j] = INF;
}
}
// 인접 정보 리스트 입력
for (int i=1; i<=R; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int l = Integer.parseInt(st.nextToken());
dist[a][b] = l;
dist[b][a] = l;
adjList[a].add(new Site(b, l));
adjList[b].add(new Site(a, l));
}
}
}
코드가 긴데, 플로이드 워셜과 다익스트라를 모두 구현해놓아서 그렇다.
주석 처리를 통해 시간을 비교할 수 있도록 코드를 작성해봤다.
문제에서는 범위가 N이 100 이내이고, 간선도 100 이내라서, 실행시간의 큰 차이를 보이지 않았다.
위가 다익스트라, 아래가 플로이드 워셜이다.
그래서,
N 범위를 더 크게 해서 테스트케이스를 만들어 실험해봤다!
테스트케이스는 GPT를 활용해 테스트케이스를 만드는 파이썬 코드를 생성하여 적용했다.
속도 비교 실험
1-1. 노드 수 :500개, 간선 수:120000개
1-2. 노드 수: 500개, 간선 수 : 60000개
1-3. 노드 수: 500개, 간선 수: 10000개
=> 간선 수가 줄어들수록 확실히 다익스트라는 빨라진다!!
=> 반면, 플로이드는 약간 느려졌는데, 큰 의미는 없는 수치로 보인다.
2-1. 노드 수: 1000개, 간선 수: 490000개
2-2. 노드 수: 1000개, 간선 수: 245000개
2-3. 노드 수: 1000개, 간선 수:100000개
2-4. 노드 수: 1000개, 간선 수:10000개
=> 플로이드는 O(N^3) 이므로 노드 수 500에 비해 이론상 10배 이상 실행시간이 늘어야 한다. 결과를 보면 얼추 10배 정도 나온 것으로 보인다.
=> 다익스트라는 간선 수에 비례하게 속도가 빨라지는 것으로 보인다. 노드수 500에 비해서는 이론 상 1.1배 실행시간 늘어나야 하는데, 244 -> 621이면 꽤 많이 늘어난 것 같다.
결론!!
모든 노드 간 최단 거리를 구해야 할 때, 노드 수 500까지는 웬만하면 플로이드 워셜이 빠르다.
다익스트라가 더 빨라지는 구간은 노드 수가 1000 이상쯤부터. 다만 간선 수가 매우 적어야 한다. 완전 그래프 N*(N-1)/2 에 비해 현저히 작아야 다익스트라가 유리해진다!!
