[BOJ_16235] 나무 재테크
https://www.acmicpc.net/problem/16235
16235번: 나무 재테크
부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터
www.acmicpc.net
시간 : 1064ms
메모리 : 204064KB
시간을 줄이는 게 너무 어려운 문제였다. 계속 시간 초과로 틀리다가 겨우 통과하긴 했지만 아직 너무 오래 걸리는 것 같다...
처음 통과한 코드 ↓
시간 : 1516ms
메모리 : 147008KB
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); // 땅 크기 N*N
int M = Integer.parseInt(st.nextToken()); // 나무 개수
int K = Integer.parseInt(st.nextToken()); // K년 후
int[] dr = {-1, -1, -1, 0, 0, 1,1,1};
int[] dc = {-1,0,1,-1,1,-1,0,1};
int[][] s2d2 = new int[N][N];
int[][] map = new int[N][N];
PriorityQueue<Integer>[][] tree = new PriorityQueue[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
s2d2[i][j] = Integer.parseInt(st.nextToken());
map[i][j] = 5;
tree[i][j] = new PriorityQueue<>();
}
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
int z = Integer.parseInt(st.nextToken());
// 1
tree[r-1][c-1].add(z);
}
int count = M;
for (int k = 0; k < K; k++) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
// 2
List<Integer> tmp = new ArrayList<Integer>();
// 3
if(!tree[i][j].isEmpty()) {
int total = 0;
int size = tree[i][j].size();
boolean flag = false;
// 4
for (int s = 0; s< size; s++) {
int age = tree[i][j].poll();
if(map[i][j]-age < 0 || flag==true) {
flag = true;
total += age/2;
count--;
}else if(flag==false && map[i][j]-age>=0) {
// 5
map[i][j]-=age;
tmp.add(++age);
}
}
// 6
for (Integer integer : tmp) {
tree[i][j].offer(integer);
}
map[i][j] += total;
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
// 5
for (Integer lists : tree[i][j]) {
if(lists%5==0) {
for (int d = 0; d < 8; d++) {
int nr = i + dr[d];
int nc = j + dc[d];
if(nr<0 || nc <0 || nr >= N || nc >= N) continue;
tree[nr][nc].add(1);
count++;
}
}
}
map[i][j] += s2d2[i][j];
}
}
}
System.out.println(count);
}
}
바꾼 코드 ↓
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.Queue;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); // 땅 크기 N*N
int M = Integer.parseInt(st.nextToken()); // 나무 개수
int K = Integer.parseInt(st.nextToken()); // K년 후
int[] dr = {-1, -1, -1, 0, 0, 1,1,1};
int[] dc = {-1,0,1,-1,1,-1,0,1};
int[][] s2d2 = new int[N][N];
int[][] map = new int[N][N];
PriorityQueue<Integer>[][] tree = new PriorityQueue[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
s2d2[i][j] = Integer.parseInt(st.nextToken());
map[i][j] = 5;
tree[i][j] = new PriorityQueue<>();
}
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
int z = Integer.parseInt(st.nextToken());
tree[r-1][c-1].offer(z);
}
int count = M;
for (int k = 0; k < K; k++) {
int[][] age5 = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
Queue<Integer> tmp = new LinkedList<>();
boolean flag = false;
int total = 0;
while(!tree[i][j].isEmpty()) {
int age = tree[i][j].poll();
int diff = map[i][j] - age;
if(diff < 0 || flag==true) {
flag = true;
total += age/2;
count--;
}else if(flag==false && diff >=0) {
map[i][j] = diff;
tmp.offer(++age);
if(age%5==0) age5[i][j]++;
}
}
map[i][j] += total;
while(!tmp.isEmpty()) {
tree[i][j].offer(tmp.poll());
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int size = age5[i][j];
for (int j2 = 0; j2 < size; j2++) {
for (int d = 0; d < 8; d++) {
int nr = i + dr[d];
int nc = j + dc[d];
if(nr<0 || nc <0 || nr >= N || nc >= N) continue;
tree[nr][nc].offer(1);
count++;
}
}
map[i][j] += s2d2[i][j];
}
}
}
System.out.println(count);
}
}(숫자는 주석 번호)
1.
PriorityQueue를 사용했기 때문에 add 대신 offer로 모두 고쳐주었다.
원래 같은 코드를 돌려도 시간은 다 다르게 나오기 때문에 이것 때문인지는 모르겠지만, offer로 바꿔주었을 때 시간이 덜 나오긴 했다.
2.
살아있는 나무를 임시 저장하는 tmp를 List에서 Queue로 바꾸었다.
List의 get 함수가 시간이 많이 걸린다고 들었기 때문인데, 역시 시간이 아주 조금 줄었다.
3.
Queue 형식이기 때문에 isEmpty를 검사하고 for문으로 돌리는 것보다 while(!tree.isEmpty)로 바꾸었다.
검사하고 바로 넘어갈 수 있고, 굳이 size를 구하고 하는 것보다 검사할 것이 적어서인지 시간이 줄었다.
4.
매번 구해줘야 하는 map[i][j]-age같은 변수는 하나로 선언한 뒤 선언한 변수만 썼다.
예전에 배운 것 중에 for문 작성 시
for(int i = 0; i < map.length; i++)
보다
int len = map.length;
for(int i = 0; i < len; i++)
으로 쓰는 것이 효율적이라는 게 있었다. for문이 한 번 돌 때마다 배열 길이를 새로 연산해줘야하기 때문이다.
5.
원래는 아래에서 tree 배열에 있는 모든 list 원소를 다 검사해서 5로 나누어 떨어지는지 보았는데,
비교할 때 매번 새로 원소값을 가져오는 시간을 줄이기 위해 age를 늘리는 동시에 5의 배수인지 검사했다.
아래 for문에서는 아무 검사 없이 count 배열만큼 무조건 돌리도록 했다.
이 변경 사항으로 시간이 엄청 단축됐다.
6.
tmp를 Queue로 바꾸면서 foreach로 원소를 하나씩 옮기는 대신 que.poll()을 사용해 원소를 옮겼다.
시간이 1000ms가 넘기 때문에 다른 사람들은 어떻게 풀었는지도 살펴보았는데, Queue를 쓰지 않고 나무 리스트의 삽입/삭제를 직접 구현한 코드가 있었다. Queue가 같은 역할을 해줄 거라 생각했는데 다른 모양...
대부분의 사람들이 각각 나이가 같은 나무 개수를 구하고, 해당 나이 나무 모두에게 필요한 양분을 구한 뒤 한 번에 계산하는 것 같다.
2살인 나무 5개가 있는데, 양분이 8 남았다면 8 - 2*5 = -2 로 모두 다 살 수는 없다. 이 때 살 수 있는 건 8 / 2 = 4 그루 뿐이다.
이를 통해 현재 나이에서 살 수 있는 나무 개수 = Math.min(현재 나이 나무 개수, 양분 / 나이) 인 것을 알 수 있다..
이보다 나이 많은 나무는 다 죽는다.
또, sort를 할 필요가 없다는 걸 알게 되었다! 오름차순이라는 말에 자동으로 sort를 사용했는데, 처음 입력에 나무 위치는 모두 다르고, 이후 추가되는 나무는 모두 나이가 1이다. 매번 제일 앞에 추가해주면 된다. 아마 Queue 말고 직접 삽입/삭제를 구현한 경우 이런 비교 연산이 없기 때문에 시간이 절감되는 것 같다.