16235번 문제의 시간 줄이기

문제를 잘 읽으면서 봄, 여름, 가을, 겨울을 하나씩 구현해보면 구현 자체는 쉽다.

 

이 문제에서 가장 어려운 점은 0.3초라는 시간제한을 뚫기위해 어떻게든 시간을 줄여야 한다는 점이다. 그래서 다음에 이러한 구현 문제를 풀 때 도움도 될겸 문제를 풀면서 찾은 시간을 줄이는 방법들을 정리해보는 것이다.

 

처음에 코드는 이렇게 구성했다.

for (int year = 0; year < k; year++) {

    if (trees.isEmpty()) break;

    trees.sort(new Comparator<tree>() {
        @Override
        public int compare(tree o1, tree o2) {
            return o1.old - o2.old;
        }
    });
    
    // spring
    ArrayDeque<tree> stk = new ArrayDeque<>();
    for (tree t : trees) {

        if (map[t.y][t.x] >= t.old) {
            map[t.y][t.x] -= t.old;
            t.old++;
        } else stk.push(t);
    }

    // summer
    while (!stk.isEmpty()) {
        tree t = stk.pop();
        trees.remove(t);

        map[t.y][t.x] += (t.old / 2);
    }

    // autumn
	ArrayList<tree> tmp = new ArrayList<>();
    int size = trees.size();
    for (int i = 0; i < size; i++) {
        tree t = trees.get(i);
        if (t.old % 5 == 0) {
            for (int d = 0; d < 8; d++) {
                int ny = t.y + dy[d];
                int nx = t.x + dx[d];
                if (ny < 0 || nx < 0 || ny >= n || nx >= n) continue;
                tmp.add(new tree(ny, nx, 1));
            }
        }
    }
	trees.addAll(tmp);

    for (int y = 0; y < n; y++) {
        for (int x = 0; x < n; x++) {
            map[y][x] += A[y][x];
        }
    }
}

 

코드를 분석해보면, 봄, 여름, 가을, 겨울을 하나씩 구현하였고 이를 year가 0부터 증가하는 반복문으로 감싸 모든 로직이 수행하면 1년이 지나도록 하였다.

 

봄 코드를 보면, 봄에서는 나무의 정보를 하나씩 꺼내서 자신의 나이만큼 양분을 먹고, 나이가 1 증가하거나 혹은 양분이 부족해서 죽는다. 이때, 여러 나무가 한 좌표에 있으면 나이가 어린 나무부터 양분을 먹는 조건이 있기 때문에 미리 나무 리스트를 정렬해주었다. 또, 죽은 나무는 여름에서 사용해야 하기때문에 스택에 죽은 나무들을 담아준다.

 

여름에는 스택에 담아두었던 죽은 나무들을 하나씩 꺼내면서 나무 리스트에서 해당 나무들을 지우고, 나이 / 2만큼을 map에 더해준다.

 

가을에는 tmp라는 새롭게 자라나는 나무들을 담을 배열을 선언해주고, 나무 리스트를 하나씩 방문하면서 5의 배수이면 8방향의 좌표에 나무들을 추가해준다. 모든 나무를 방문했으면 뒤에 tress.addAll(tmp);로 새롭게 자라나는 나무들을 리스트에 추가해준다.

 

겨울에는 단순히 모든 맵에다 A 배열의 값을 각각 더해준다.

 

딱보아도 구현에 집중하여 상당히 비효율적인 실행을 보여준다. 당연하게도 시간초과가 났다. 그럼 문제를 통해 어떻게 시간을 줄일 수 있을지 고민해보자. 일단, 문제의 봄, 여름, 가을, 겨울 내용을 한번보자.

 

봄에는 나무가 양분을 먹고 나이가 증가하며, 여름에는 죽은 나무들의 양분이 맵에 더해진다. 가을에는 번식만 한다. 겨울에는 맵에 양분들이 더해진다. 이렇게 보면 맵을 기준으로 봄에는 양분이 줄어들고, 여름과 겨울에는 양분이 증가하며 가을에는 변화가 없다. 그럼 봄 이후에 여름과 겨울을 묶어 처리하고 가을은 어떤 경우에 진행되어도 문제가 없지 않을까?

 

이러한 생각을 갖고 한번 접근해보자. 일단 여름과 겨울을 하나의 로직으로 처리하자. 겨울부터보면 겨울에는 무조건 S2D2가 모든 땅을 돌아다니며 양분을 더해야하니까 원소를 하나하나 접근하는 코드에서 더 줄일 수는 없을 것 같다. 그럼 여름을 줄여야한다. 이를 위해 여름도 겨울과 동일하게 n * n 크기의 2차원 배열을 사용하는 것이다. 죽은 나무 좌표마다 old / 2를 더해두고ㅡ하나의 좌표에는 여러 개의 나무가 있을 수 있으므로 여러 개의 나무가 죽었을 경우를 위해 더하기를 한다.ㅡ, 겨울과 같이 map에다가 더하면 되지 않을까?

 

즉, 다음과 같이 코드를 작성할 수 있을 것 같다.

// dies는 0으로 초기화
...
// 죽은 나무를 찾는 로직
dies[y][x] += (old / 2);
...

// 여름과 겨울을 동시에 진행
for (int y = 0; y < n; y++) {
	for (int x = 0; x < n; x++) {
		map[y][x] += A[y][x] + dies[y][x];
		dies[y][x] = 0; // 0으로 초기화 해줘야 다음 년도에 영향을 끼치지 않음
	}
}

 

 

죽은 나무를 찾는 로직은 결국 봄에서 해야하므로 봄이 진행하며 map[t.y][t.x] < t.old면 dies[t.y][t.x] += (t.old / 2)를 통해 해당 값들 저장할 수 있을 것 같다. 그럼 이제 봄을 한번 바꾸어보자.

trees.sort(new Comparator<tree>() {
    @Override
    public int compare(tree o1, tree o2) {
        return o1.old - o2.old;
    }
});

ArrayDeque<tree> stk = new ArrayDeque<>();
for (tree t : trees) {

    if (map[t.y][t.x] >= t.old) {
        map[t.y][t.x] -= t.old;
        t.old++;
    } else stk.push(t);
}

 

일단 스택은 이제 필요가 없다. 여름 코드 자체를 겨울과 합쳤기 때문이다. 그럼 어떻게 나무 리스트에서 해당 나무들을 지울 수 있을까? 이는 검색을 통해서 알았는데 Iterator를 통하면 iter.remove()를 통해 현재 진행 중인 원소를 원본 리스트에서 지울 수 있다. 여기까지하면 대충 이런 코드를 작성할 수 있겠다.

trees.sort(new Comparator<tree>() {
    @Override
    public int compare(tree o1, tree o2) {
        return o1.old - o2.old;
    }
});

Iterator iter = trees.iterator();
while (iter.hasNext()) {
	tree t = (tree)iter.next();

    if (map[t.y][t.x] >= t.old) {
        map[t.y][t.x] -= t.old;
        t.old++;
    } else {
		dies[t.y][t.x] += (t.old / 2);
		iter.remove();
	}
}

 

근데 Iterator는 ArrayList보다 LinkedList에서 더 효율적이다. 그리고, 삭제 과정에서 iter를 통해 remove를 하면 ArrayList는 뒤에 있는 나무들을 앞으로 당기는 시프트 작업을 해야해서 O(n)의 시간 복잡도가 생기지만 LinkedList는 리스트 연결 및 삭제만 해주면 되므로 O(1)이다. LinkedList를 사용하는 것이 오히려 타당한 것이다. 봄은 이정도로만 하고 가을을 한번 생각해보자.

 

가을은 나무가 번식한다. 봄을 진행하고 탐색하면서 번식을 하면 될까? 그것보다는 봄이 진행하면서 나무가 나이를 먹었다면, 걔를 바로 번식시키면 더더욱 로직의 시간을 줄일 수 있지 않을까? 라는 생각으로 시간을 줄여보자.

 

봄에서 나이를 먹는 상황은 if (map[t.y][t.x] >= t.old) 이 분기문 이후이다. 그럼 해당 분기문에 나이를 먹고, 바로 가을에서의 번식을 하면 될 것 같다.

trees.sort(new Comparator<tree>() {
    @Override
    public int compare(tree o1, tree o2) {
        return o1.old - o2.old;
    }
});

LinkedList<tree> tmp = new LinkedList<>();
Iterator iterator = trees.iterator();
while (iterator.hasNext()) {
    tree t = (tree) iterator.next();

    // 양분을 먹고 나이 증가 -> 번식
    if (map[t.y][t.x] >= t.old) {
        map[t.y][t.x] -= t.old;
        t.old++;

        if (t.old % 5 == 0) {
            for (int d = 0; d < 8; d++) {
                 int ny = t.y + dy[d];
                 int nx = t.x + dx[d];
                 if (ny < 0 || nx < 0 || ny >= n || nx >= n) continue;
                 tmp.add(new tree(ny, nx, 1));
             }
         }
    } else {
        dies[t.y][t.x] += t.old/2;
        iterator.remove();
    }
}

trees.addAll(tmp);

 

마지막으로 addAll에는 인덱스를 지정하여 추가할 수 있는 기능이 있다. 애초에 자라나는 나무들을 무조건 0번 인덱스부터 추가하면 정렬할 필요없이 무조건 어린 나이의 나무들이 앞에 있게 된다. 그럼 최종적으로 봄과 가을은 다음과 같다.

LinkedList<tree> tmp = new LinkedList<>();
Iterator iterator = trees.iterator();
while (iterator.hasNext()) {
    tree t = (tree) iterator.next();

    // 양분을 먹고 나이 증가 -> 번식
    if (map[t.y][t.x] >= t.old) {
        map[t.y][t.x] -= t.old;
        t.old++;

        if (t.old % 5 == 0) {
            for (int d = 0; d < 8; d++) {
                 int ny = t.y + dy[d];
                 int nx = t.x + dx[d];
                 if (ny < 0 || nx < 0 || ny >= n || nx >= n) continue;
                 tmp.add(new tree(ny, nx, 1));
             }
         }
    } else {
        dies[t.y][t.x] += t.old/2;
        iterator.remove();
    }
}

trees.addAll(0, tmp);

 

 

코드

import java.io.*;
import java.util.*;

public class Main {

    static int n, m, k;
    static int[][] map;
    static int[][] dies;
    static int[][] A;

    static LinkedList<tree> trees = new LinkedList<>();

    static int[] dy = {-1, -1, -1, 0, 0, 1, 1, 1};
    static int[] dx = {-1, 0, 1, -1, 1, -1, 0, 1};

    static class tree {
        int x, y, old;

        tree(int y, int x, int old) {
            this.y = y;
            this.x = x;
            this.old = old;
        }
    }

    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());
        k = Integer.parseInt(st.nextToken());

        map = new int[n][n];
        dies = new int[n][n];
        A = new int[n][n];

        for (int y = 0; y < n; y++) {
            st = new StringTokenizer(br.readLine());
            for (int x = 0; x < n; x++) {
                map[y][x] = 5;
                A[y][x] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());

            int y = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            int old = Integer.parseInt(st.nextToken());

            trees.add(new tree(y-1, x-1, old));
        }

		// 초기에는 나무의 나이가 무작위로 주어지므로 한번의 정렬이 필요하다.
        trees.sort(new Comparator<tree>() {
            @Override
            public int compare(tree o1, tree o2) {
                return o1.old - o2.old;
            }
        });

        for (int year = 0; year < k; year++) {

			if (trees.isEmpty()) break;

            // 봄 가을
            LinkedList<tree> tmp = new LinkedList<>();
            Iterator iterator = trees.iterator();
            while (iterator.hasNext()) {
                tree t = (tree) iterator.next();

                // 양분을 먹고 나이 증가 -> 번식
                if (map[t.y][t.x] >= t.old) {
                    map[t.y][t.x] -= t.old;
                    t.old++;

                    if (t.old % 5 == 0) {
                        for (int d = 0; d < 8; d++) {
                            int ny = t.y + dy[d];
                            int nx = t.x + dx[d];
                            if (ny < 0 || nx < 0 || ny >= n || nx >= n) continue;
                            tmp.add(new tree(ny, nx, 1));
                        }
                    }
                } else {
                    dies[t.y][t.x] += t.old/2;
                    iterator.remove();
                }
            }

            trees.addAll(0, tmp);

            // 여름, 겨울
            for (int y = 0; y < n; y++) {
                for (int x = 0; x < n; x++) {
                    map[y][x] += dies[y][x] + A[y][x];
                    dies[y][x] = 0;
                }
            }
        }

        System.out.println(trees.size());
    }
}