백준 16235 나무 재테크

삼성 코딩테스트(역량테스트) 기출

해싱

각 칸마다 Map 자료구조로 나무의 상태를 관리한다

• { 나이 : 해당 나이인 나무 수} 형태

• TreeMap : 순서가 있는 Map 자료구조

  나이순으로 관리하기 위해 HashMap이 아니라 TreeMap을 이용했다

⇒ 나무 마다 관리하는 게 아니라 속도가 향상된다

⇒ 하지만 메모리는...포기한다!

오답노트

• Map을 순회하면서 요소를 삭제하면 안 된다

  concurrency 오류가 날 수 있다

  ⇒ 임시 자료구조에 저장해 놓고 for문이 끝난 후 한 번에 갱신하자

• Map을 비우고 나이 먹은 애들로 다시 Map을 구성한다

  ⇒ 이렇게 안 하면 나무 수가 0인 요소가 계속 남아있게 된다!

• survive>0인 경우에만 agedTree에 넣어줘야 함

가을 겨울은 간단하니까 봄 / 여름에 집중해보자

봄 / 여름 코드

각 칸마다 Map을 순회하며 살아남는 애들/죽는 애들을 카운팅한다

• hmap : (i, j)의 맵을 편하게 쓰기 위한 참조
• agedTree : 양분을 먹고 살아남아 1살 먹는 나무들을 담는 TreeMap

1. hmap.keySet()을 순회하며 나이 별로 처리한다

2. remain에 남은 양분을 저장한다

3. extra 변수 선언 : 여름에 추가될 양분

   따로 변수로 관리한 이유

   ⇒ 아직 봄의 일을 처리 중이므로 포문이 다 끝난 후에 처리해야 함

   이렇게 하지 않으면 봄에 죽은 애들의 양분을 추가하는 것과 같다

   다음 나이의 애들을 처리할 때 양분이 원래 값보다 더 많아지게 되어 오류

4. (남은 양분 / 나이)의 몫이 total보다 작으면 굶어 죽는 나무가 생긴다

   • dead 변수를 갱신한다

5. reamin 변수 갱신 : 먹은 양분을 빼 준다

6. extra 변수 갱신 : 죽은 애들을 양분으로 만들어 저장

7. 살아 남은 애들은 1살 먹이고 agedTree에 기록해둔다

포문이 끝나면

8. 땅의 양분 상태를 갱신 : remain + extra

여기서 extra를 더해주는 게 여름의 일

9. 일단 Map을 싹 비운다

10. 나이 먹은 애들로 다시 Map을 구성

static void SS() {
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                int remain = soil[i][j]; // 땅에 남아 있는 양분 
                Map<Integer, Integer> hmap = dict.get(i).get(j);
                Map<Integer, Integer> agedTree = new TreeMap<Integer, Integer>();
                int extra = 0;
                // 맵 순회 : 양분 자기나이만큼 먹을 수 있는가
                // 먹을 수 있으면 agedTree에 넣기
                // 없으면 죽이고 extra 갱신 
                for(Integer age:hmap.keySet()) {
                    int total = hmap.get(age); // 해당 칸의 age살 나무 수 
                    int dead = 0; // 죽을 애들 
                    // 모든 애들이 나이만큼 먹을 수 없으면 
                    if((remain/age) < total) {
                        // dead에 죽은 애들 수 갱신
                        dead = total - (remain/age);
                    }
                    int survive = total-dead; // 살아 남은 나무 
                    remain -= age * (survive); // 먹은 양분 빼주기 = 나이 * 살아남은 나무  
                    // 죽은 애들은 양분이 된다 
                    if(dead>0) { 
                        extra += dead*(age/2);
                    }
                    // 살아 남은 애들은 1살 먹이고 기록 
                    if(survive>0) { 
                        agedTree.put(age+1, survive);
                    }
                }
                soil[i][j] = remain+extra; // 남은 양분+죽은 애들이 준 양분으로 갱신 
                hmap.clear(); // 일단 싹 비운다 
                // 나이 먹은 애들로 다시 맵 구성 
                for(Integer age:agedTree.keySet()) {
                    hmap.put(age, agedTree.get(age));
                }
            }
        }
    }

Map 자료구조

선언

이중 리스트의 요소가 Map인 구조로 작성했다

1. 우선 new로 전체 자료구조를 생성한다
2. 첫 번째 포문을 돌면서 i마다 new ArrayList<Map<>>을 add한다
3. 두 번째 포문에서 j마다 dict.get(i)에 new TreeMap<>을 add한다

// 각 칸마다 트리맵 사용해 나무를 관리 {나이 : 해당 나이 나무 수}
static List<List<Map<Integer, Integer>>> dict;

// 각 칸마다 트리맵을 넣어준다
// 트리맵 => 어린 순으로 관리하기 위해 (어린 애들부터 양분을 먹기 때문)
dict = new ArrayList<List<Map<Integer, Integer>>>(); // 일단 동적 할당 
    for (int i = 0; i < h; i++) { // 행마다 ArrayList 할당  
        dict.add(new ArrayList<Map<Integer, Integer>>());
    for (int j = 0; j < w; j++) { // 칸마다 트리맵 할당 
        dict.get(i).add(new TreeMap<Integer, Integer>());
    }
}

참조

매번 get.(i).get(j)를 쓰기 귀찮아서

hmap이라는 Map을 통해 dict을 참조했다.

자바에서는 reference type을 대입하면 값에 의한 복사가 아니라 레퍼런스에 의한 복사가 된다

쉽게 말해 hmap에서 값을 변경하면 dict에도 그대로 갱신된다

Map<Integer, Integer> hmap = dict.get(i).get(j);

입력

• contiansKey()를 통해

  없으면 value를 1로 넣어주고

  있으면 원래 value에 +1한 값을 넣는다

• Map 자료구조는 중복 허용이 안 되기 때문에 value가 갱신되는 것과 동일해진다

if (hmap.containsKey(age)) {
        hmap.put(age, hmap.get(age) + 1);
} else {
        hmap.put(age, 1);
}

key값 순회

for문과 keySet() 메서드로 모든 키 값을 순회할 수 있다!

for(Integer age:hmap.keySet()) {

전체 코드

package test;

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.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class BOJ_16235_나무재테크 {
    static int h, w, m, k;
    static int[][] soil;  // 땅의 상태 (양분이 얼마나 있는지)
    static int[][] food; // 겨울에 뿌릴 양분 

     // 각 칸마다 트리맵 사용해 나무를 관리 {나이 : 해당 나이 나무 수} 
    static List<List<Map<Integer, Integer>>> dict;


    static void init() {
        food = new int[h][w];
        soil = new int[h][w];

        // 각 칸마다 트리맵을 넣어준다
        // 트리맵 => 어린 순으로 관리하기 위해 (어린 애들부터 양분을 먹기 때문)
        dict = new ArrayList<List<Map<Integer, Integer>>>(); // 일단 동적 할당 
        for (int i = 0; i < h; i++) { // 행마다 ArrayList 할당  
            dict.add(new ArrayList<Map<Integer, Integer>>());
            for (int j = 0; j < w; j++) { // 칸마다 트리맵 할당 
                dict.get(i).add(new TreeMap<Integer, Integer>());
            }
        }
        // 땅의 초기 상태 
        for(int i=0; i<h; i++) {
            for(int j=0; j<w; j++) {
                soil[i][j] = 5;
            }
        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        st = new StringTokenizer(br.readLine());
        h = w = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        init();
        for (int i = 0; i < h; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < w; j++) {
                food[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 나무 입력
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken()) - 1;
            int y = Integer.parseInt(st.nextToken()) - 1;
            int age = Integer.parseInt(st.nextToken());
            Map<Integer, Integer> hmap = dict.get(x).get(y);
            if (hmap.containsKey(age)) {
                hmap.put(age, hmap.get(age) + 1);
            } else {
                hmap.put(age, 1);
            }
        }
        // System.out.println(dict.get(0).get(0).get(1));

        for(int i=0; i<k; i++) {
            simul();
        }

        int ans = 0;
        for(int i=0; i<h; i++) {
            for(int j=0; j<w; j++) {
                Map<Integer, Integer> hmap = dict.get(i).get(j);
                for(Integer key:hmap.keySet()) {
                    ans += hmap.get(key);
                }
            }
        }
        System.out.println(ans);
    }

    static void simul() {
        // 봄/여름 : 나이먹기 & 죽은 애들이 양분으로 
        SS();
        // 가을 : 번식
        fall();
        // 겨울 : 양분 추가
        winter();
    }

    static void SS() {
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                int remain = soil[i][j]; // 땅에 남아 있는 양분 
                Map<Integer, Integer> hmap = dict.get(i).get(j);
                Map<Integer, Integer> agedTree = new TreeMap<Integer, Integer>();
                int extra = 0;
                // 맵 순회 : 양분 자기나이만큼 먹을 수 있는가
                // 먹을 수 있으면 agedTree에 넣기
                // 없으면 죽이고 extra 갱신 
                for(Integer age:hmap.keySet()) {
                    int total = hmap.get(age); // 해당 칸의 age살 나무 수 
                    int dead = 0; // 죽을 애들 
                    // 모든 애들이 나이만큼 먹을 수 없으면 
                    if((remain/age) < total) {
                        // dead에 죽은 애들 수 갱신
                        dead = total - (remain/age);
                    }
                    int survive = total-dead; // 살아 남은 나무 
                    remain -= age * (survive); // 먹은 양분 빼주기 = 나이 * 살아남은 나무  
                    // 죽은 애들은 양분이 된다 
                    if(dead>0) { 
                        extra += dead*(age/2);
                    }
                    // 살아 남은 애들은 1살 먹이고 기록 
                    if(survive>0) { 
                        agedTree.put(age+1, survive);
                    }
                }
                soil[i][j] = remain+extra; // 남은 양분+죽은 애들이 준 양분으로 갱신 
                hmap.clear(); // 일단 싹 비운다 
                // 나이 먹은 애들로 다시 맵 구성 
                for(Integer age:agedTree.keySet()) {
                    hmap.put(age, agedTree.get(age));
                }
            }
        }
    }
    static int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1};
    static int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
    private static void fall() {
        // 태어나는 애들을 따로 저장한 후 마지막에 한 번에 갱신 
        int[][] newKids = new int[h][w]; // (i, j)에 태어날 나무 수 저장 
        // 번식 (나이 % 5 ==0)
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                Map<Integer, Integer> hmap = dict.get(i).get(j);
                for (Integer age : hmap.keySet()) {
                    if(age%5==0) {
                        for(int d=0; d<8; d++) {
                            int nx = i+dx[d]; int ny = j+dy[d];
                            if(nx<0 || nx>h-1 || ny<0 || ny>w-1) continue;
                            newKids[nx][ny]+=hmap.get(age);
                        }
                    }
                }
            }
        }
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                Map<Integer, Integer> hmap = dict.get(i).get(j);
                hmap.put(1, newKids[i][j]);
            }
        }
    }

    private static void winter() {
        // 양분 뿌리기
        for(int i=0; i<h; i++) {
            for(int j=0; j<w; j++) {
                soil[i][j] += food[i][j];
            }
        }
    }

}