[JAVA] 백준 나무재테크

첫시도-시간초과(테스트케이스는 다 맞음)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

class Main {
    static class Tree {
        int age;
        boolean life = true;

        Tree() {
            this.age = 1;
        }

        Tree(int age) {
            this.age = age;
        }

    }

    static int[][] a, food;
    static int n, m, k;
    static int minusCount = 0;
    static ArrayList<ArrayList<ArrayList<Tree>>> trees = new ArrayList<>();

    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());
        for (int i = 0; i < n; i++) trees.add(new ArrayList<>());
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) trees.get(i).add(new ArrayList<>());

        a = new int[n][n];
        food = new int[n][n];
        for (int[] f : food) Arrays.fill(f, 5);
        for (int i = 0; i < n; i++) {//영양가 add배열
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                a[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        for (int i = 0; i < m; i++) {//tree위치
            //System.out.println(m);
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int z = Integer.parseInt(st.nextToken());
            trees.get(x - 1).get(y - 1).add(new Tree(z));
        }

        for (int years = 0; years < k; years++) {
            spring();
            summer();
            autumn();
            winter();
        }
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                count += trees.get(i).get(j).size();
            }
        }
        System.out.println(count - minusCount);
    }

    public static void spring() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                ArrayList<Tree> arrayt = trees.get(i).get(j);
                if (arrayt.size() == 0) continue;
                //어린 나무부터 양분을 먹는다.
                arrayt.sort(new Comparator<Tree>() {
                    @Override
                    public int compare(Tree o1, Tree o2) {
                        return Integer.compare(o1.age, o2.age);
                    }
                });
                for (int sz = 0; sz < arrayt.size(); sz++) {
                    Tree t = arrayt.get(sz);
                    if(t.age == 0) continue;
                    if (food[i][j] >= t.age) {
                        food[i][j] -= t.age;
                        ++t.age;//먹고 나이 증가
                    } else {
                        t.life = false;//안먹고 죽음
                    }
                }
            }
        }
    }

    public static void summer() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                ArrayList<Tree> arrayt = trees.get(i).get(j);
                if (arrayt.size() == 0) continue;
                int size = arrayt.size();
                for (int sz = 0; sz < size; sz++) {
                    Tree t = arrayt.get(sz);
                    if (t.age != 0 && t.life == false) {
                        food[i][j] += t.age / 2;
                        t.age = 0;
                        minusCount++;
                    }
                }
            }
        }
    }

    public static void autumn() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                ArrayList<Tree> arrayt = trees.get(i).get(j);
                if (arrayt.size() == 0) continue;

                for (int sz = 0; sz < arrayt.size(); sz++) {
                    Tree t = arrayt.get(sz);
                    if (t.life == true && t.age % 5 == 0) {//나이가 5의배수인경우(0인적은 없음므로 ㄱㅊ)
                        int[] rx = {-1, -1, -1, 0, 0, 1, 1, 1};
                        int[] ry = {-1, 0, 1, -1, 1, -1, 0, 1};
                        for (int r = 0; r < 8; r++) {
                            int srx = i + rx[r];
                            int sry = j + ry[r];
                            if (srx >= 0 && sry >= 0 && srx < n && sry < n) {
                                trees.get(srx).get(sry).add(new Tree());
                            }
                        }
                    }
                }
            }
        }
    }

    public static void winter() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                food[i][j] += a[i][j];
            }
        }
    }
}

 

짚고넘어가야 될 문제가 있다. 

remove메소드 효율관련.

LinkedList의 경우 주소 명시한 경우 remove는 O(1), 찾아서 지우는경우는 O(N)이다.

ArrayList의 경우 주소 명시한 경우 remove는 index를 한칸씩 당겨야하므로 O(N)이다.

 

 

아래에서는 ArrayList를 사용하였고, 삼중 ArrayList를 통해서 배열형태

의 그리드에 객체를 넣는 방식을 차용했다.

 

summer부분은 spring에 합쳐버렸다. 

 

나이가 어린 나무부터 양분을 먹는다.

-> 이 부분은 ArrayList 특성상 sort도 가능하지만 매번 정렬해주어야된다는 비효율성을 해결하고자, 탐색할때 뒷부분부터 탐색하는 방식으로 개선했다.

-> 문제 특성상 ArrayList<Tree>에 추가되는 Tree들은 가장 마지막에 추가한 나무가 제일 어릴수 밖에 없기 때문이다.

 

그리고 autum부분에서 재탐색을 생략하기위해,

spring부분에서 age==5의배수인 객체들의 위치를 모두 Queue에 저장해 두었다가 불러왔다.

일종의 메모이제이션의 역할로 사용한 것이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    static class Tree {
        int age;
        boolean life = true;
        int x, y, index;

        Tree() {
            this.age = 1;
        }

        Tree(int age) {
            this.age = age;
        }

        public void set(int x, int y, int index) {
            this.x = x;
            this.y = y;
            this.index = index;
        }

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }

        public int getIndex() {
            return index;
        }
    }

    static int[][] a, food;
    static int n, m, k;
    static int count = 0, minusCount = 0;
    static ArrayList<ArrayList<ArrayList<Tree>>> trees = new ArrayList<>();

    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());
        for (int i = 0; i < n; i++) trees.add(new ArrayList<>());
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) trees.get(i).add(new ArrayList<>());

        a = new int[n][n];
        food = new int[n][n];
        for (int[] f : food) Arrays.fill(f, 5);
        for (int i = 0; i < n; i++) {//영양가 add배열
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                a[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        for (int i = 0; i < m; i++) {//tree위치
            //System.out.println(m);
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int z = Integer.parseInt(st.nextToken());
            trees.get(x - 1).get(y - 1).add(new Tree(z));
        }

        for (int years = 0; years < k; years++) {
            spring();
            //summer();
            autumn();
            winter();
        }
        //int count = 0;
        /*for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                count += trees.get(i).get(j).size();
            }
        }*/
        System.out.println(m + count - minusCount);
    }

    static Queue<Tree> q = new LinkedList<>();

    public static void spring() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                ArrayList<Tree> arrayt = trees.get(i).get(j);
                if (arrayt.size() == 0) continue;
                //어린 나무부터 양분을 먹는다.

                int summerfood = 0;
                for (int sz = arrayt.size() - 1; sz >= 0; sz--) {
                    Tree t = arrayt.get(sz);
                    if (t.age == 0) continue;
                    if (food[i][j] >= t.age) {
                        food[i][j] -= t.age;
                        ++t.age;//먹고 나이 증가
                        if (t.age % 5 == 0) {
                            t.set(i, j, sz);
                            q.add(t);
                        }
                    } else {
                        t.life = false;//안먹고 죽음
                        summerfood += t.age / 2;
                        t.age = 0;
                        trees.get(i).get(j).remove(sz);
                        minusCount++;
                    }
                }
                food[i][j] += summerfood;
            }
        }
    }

    /*public static void summer() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                ArrayList<Tree> arrayt = trees.get(i).get(j);
                if (arrayt.size() == 0) continue;
                int size = arrayt.size();
                for (int sz = 0; sz < size; sz++) {
                    Tree t = arrayt.get(sz);
                    if (t.age != 0 && t.life == false) {
                        food[i][j] += t.age / 2;
                        t.age = 0;
                        minusCount++;
                    }
                }
            }
        }
    }*/

    public static void autumn() {
        while (!q.isEmpty()) {
            Tree t = q.poll();
            int[] rx = {-1, -1, -1, 0, 0, 1, 1, 1};
            int[] ry = {-1, 0, 1, -1, 1, -1, 0, 1};
            for (int r = 0; r < 8; r++) {
                int srx = t.getX() + rx[r];
                int sry = t.getY() + ry[r];
                if (srx >= 0 && sry >= 0 && srx < n && sry < n) {
                    trees.get(srx).get(sry).add(new Tree());
                    count++;
                }
            }
        }
    }

    public static void winter() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                food[i][j] += a[i][j];
            }
        }
    }
}