나무 재테크-ArrayList<Integer>[ ][ ]로 풀기

처음에 이 문제 접근 방식, 자료구조는 다음과 같았다. 그런데 아래와 같은 자료구조를 정의하거나 구현해내지 못해서 문제 풀이를 실패했다.

각 (x,y)는 정수형 리스트이다. - List<Integer> tree 문제에서 땅 크기는 NxN 이기 때문에 이러한 리스트도 NxN개가 있으며 이것은 2차원 정수형 리스트라고 할 수 있다! - List<Integer>[ ][ ] trees

초기화⭐️⭐️⭐️⭐️⭐️NPE 조심!! 초기화 : List<Integer> tree = new ArrayList<Integer>[N][N] 2차원이기 때문에 2중 for문으로 각 (x,y)의 리스트 초기화하는 것도 잊어선 안된다!!!!!

위의 그림처럼 나무의 정보를 저장할 때는 (x,y)에 나무 M개의 나이만 저장하면 된다.

for(int i=0;i<M;i++){
    int x = sc.nextInt()-1;
    int y = sc.nextInt()-1;
    int age = sc.nextInt()-1;
    tree[i][j].add(age);
}

계절 별 구현 봄, 여름 : 같은 메서드 내에서 2중 for문으로 구현 가을, 겨울 : 같은 메서드 내에서 2중 for문으로 구현

• 봄 : (x,y)에 있는 나무 리스트를 뒤에서부터 순회하면서 양분-나이값 >= 0인 경우에 나이만큼 양분 감소. 나이 증가

• 여름 : 봄에 죽은 나무가 있다면 그 나무 나이/2만큼 해당 위치에 양분 더해지고, 나무는 사라진다.

boolean변수 flag를 왜 만드는가?⭐️⭐️⭐️⭐️⭐️ LinkedList로 풀었던 풀이에서는 사계절별로 스코프가 분리되어있었다. 전역 변수인 Tree리스트만 전역 스코프였기 때문에 Tree리스트의 각 트리 클래스의 속성값으로 죽었는지 살았는지 검사한다.

봄 : 1. 양분-나이>=0일 때{양분 감산 연산, 나무 나이 증가} 2. 양분-나이<0 :나무 사망. 여름 : 사망한 나무(양분-나이<0) {양분 증가 연산, 나무 삭제}

하지만 이번 코드에서는 하나의 2중 for문으로 양분이 감산, 증가하는 연산하는 봄, 여름을 동시에 구현하기 때문에 변수 양분 값에 유의해야한다.(조건문인 동시에 변하는 변수!)⭐️⭐️⭐️⭐️⭐️

if (양분-나이<0 ) : 나무 사망으로 판단하고 여름 연산해도 될 거라고 생각하지만 양분 부족이 처음 발생하면, 해당 위치에 양분은 죽는 나무로 인해 양분값이 나이/2만큼 증가한다! 이후의 모든 나무들은 현재 나무보다 나이가 많을 것이기 때문에 한번 양분 부족 발생하면 이후 나무들도 양분 부족 발생한다! 죽은 나무로 인해 양분이 증가했다고 해도, 이후의 모든 나무들도 여름 연산(죽은 나무 연산) 해야한다.

조건문의 변수와 증감하는 변수가 동일하기 때문에 boolean 변수로 양분 부족 처음 발생하면 false->true로 마킹하여 이후의 모든 나무들에 대해서 boolean 변수로 조건문 검사해서 여름 연산(죽는 나무 연산) 처리해준다!

(x,y)위치에서 양분 부족이 처음 발생하는 경우 그 나무는 죽어서 (x,y)위치에 나이/2만큼 양분이 증가한다. (i,j)위치의 k번째 나무 나이를 x라고 할 때 조건문을 Map[i][j] - x <0 으로 하 나무가 죽는 처리를 해버리면, 조건문에서 검사하는 조건이 Map[i][j]인데 조건문을 만족할 때 조건에 해당하는 Map[i][j]는 계속해서 증가하기 때문에, 별도의 조건 판단 장치가 추가적으로 필요하다.

(x,y) 위치의 나무 나이 저장하는 리스트는 나이가 1인 나무들이 뒤에 추가되고, 4 3 1 1 형태이다. 그러므로 리스트의 뒤에서부터 탐색하는데, 처음 양분 부족이 발생하면 더 진행하더라도 나이가 많은 나무들이기 때문에 이후의 나무들은 다 죽는다! => 처음 발생하는 양분 부족으로 죽는 나무 뿐만 아니라 이후에 발생하는 모든 죽는 나무들을 처리해야한다!(양분 += 죽는 나무/2, 리스트에서 해당 나무 삭제)

for(int i=0;i<N;i++){
   for(int j=0;j<N;j++){
      boolean flag = false;
      int sz = tree[i][j].size();
      for(int k=sz-1; k>=0;k--){//뒤에서부터 순회.
         int x = tree[i][j].get(k);//(i,j)에 있는 k번째 나무 나이
         //양분-나이>=0
         if(F[i][j] - x >=0){
            F[i][j] -= x;
            tree[i][j].set(k,x+1);
         } else{//양분-나이<0 : 나무 사망.
            flag = true;
            F[i][j] += x/2;
            tree[i][j].remove(k);//k번째 나무 삭제.
         }
      }
               

• 가을 : 나이가 5배수이면 인접 8칸에 나이 1인 나무 추가 => Map[nx][ny].add(1) // 주의할 점 : 리스트의 add는 뒤에 노드가 추가되기 때문에 봄에 나이 적은 순서로 양분 먹을 때, 리스트의 앞에서부터가 아니라 뒤에서부터 순회해야한다!

• 겨울 : F[i][j] += A[i][j] //다른 솔루션과 동일

2번째 풀었을 때 틀린 이유

1. K계절만큼 반복해야하는데 한번만 해서 틀림

2. K 만큼 반복하는 반복문 걸어주고 Index:0 Size:0 에러 발생한 이유 : 나이 오름차순으로 저장해서 0번째 요소부터 양분 먹게하고, 가을에 번식하는 나이1인 나무도 addFirst(1)로 처리했다. 나이 오름차순 되있을 때의 문제점 : k번째 요소가 양분 부족할 때, 뒤의 나무들도 다 죽게 된다. [i][j] 위치의 나무 리스트를 순회하는 반복문에서 증가하는 반복문으로 리스트를 k번째 요소를 삭제하고, k를 인위적으로 감소시켜서 +- 제로섬으로 만들어주더라도 index:0 size:0이 될 수밖에 없다. 예제 2에서 3번째 사계절을 반복할 때, 양분이 부족하게 되어 (0,0)에 위치한 1개의 나무를 삭제 처리한다. 이 때, 크기가 1이기 때문에 k=0부터 1번만 반복문을 실행하면 된다. 하지만 k=0->k=-1->k=0이 되어 list.size는 0인데 index=0에 접근하게 된다?! k=0번째 요소는 이미 삭제했는데. => 일단 기본적으로, 반복문으 리스트를 순회하면서 값을 변경하는 것은 하지 않도록 하자. 초기 리스트의 크기를 size에 담아두고, size만큼 반복해서 k번째 요소를 삭제하려고 할 때, k를 인위적으로 감소시켜서 요소를 삭제할 순 있어도, 이 size는 변경되기 전의 리스트 크기이고, 그만큼 반복을 하기 때문에 리스트가 반복문 돌 때마다 크기가 작아져도 스트 크기가 0이 되어도 반복문은 계속 실행된다. 즉, 크기가 0임에도 불구하고 size만큼 k번째 요소에 접근하여 삭제하려고 하는 것. =>다시 정리하면, 반복변수k와 반복 조건 size는 변하지 않기 때문에 반복문을 계속하느 ㄴ것이다!!! 반복변수 k를 1씩 인위적으로 감소시켜서 원하는 대로 k번째 부터 size-1번째 원소들을 다 합산할 수 있더라도, 이 때문에 k는 계속 k로 남아있고, size 또한 초기 리스트 크기로 남아있다!!!! 그렇기 때문에 k=0, size=3로 계속 남아있기 때문에 반복문 돌 때마다 리스트 크기 줄어듦에도 불구하고 반복문ㄴ을 계속해서 반복하는 것이고, index=0, size=0이 발생하는 것이다!!!!!!!!!!! => 따라서 리스트의 끝에서부터 요소를 삭제해야한다.=> 나이 내림차순으로 저장해야 한다. 끝에서부터 리스트 순회해서 나이 작은 것부터 양분 먹게 하고, 양분 부족하게 되더라도 끝에서부터 삭제하면 문제 없다.

3. 리토링 : NxN크기의 배열이 3개 필요하다. 2중 for문을 최소 3번 정도는 돌아야 하지만, 동일한 크기의 배열이기 때문에 하나의 2중 for문으로 2개 이상의 배열을 초기화 또는 입력을 받을 수 있다!

   for(int i=0;i<N;i++) 
   			for(int j=0;j<N;j++)Nutrition[i][j] = 5;
   		//S2D2 양분 추가값 입력 저장
   		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());
   			}
   		}

   
   		//S2D2 양분 추가값 입력 저장과 동시에 양분 배열 초기값 5로 셋팅!
   		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());
   				Nutrition[i][j] = 5;
   			}
   		}

4. 죽은 나무가 생길 때, 그 나무들의 나이를 합산하고 마지막에 한번에 /2로 하면 틀리는 이유 소수점을 버리기 때문에 나이가 1,3인 나무가 죽는다고 하자. 그러면 합산되는 양분의 양 1/2 = 0, 3/2 = 1,총 1만큼만 합산되는 것인데, 1+3으로 먼저 다 합산하고 2로 나눠버리면 2가 더해지기 때문에 양분 합산되기 때문에 양이 틀리게 된다!!!

5. LinkedList를 사용했을 때 시간초과가 나는 이유 : ArrayList와 LinkedList의 차이점 참고 자료 : https://www.holaxprogramming.com/2014/02/12/java-list-interface/ => 이 문제에서 리스트를 사용할 때, 데이터 검색이 많으면 ArrayList가 유리하고, 데이터 추가/삭제가 많으면 LinkedList가 유리할 것이다. 그런데 LinkedList를 사용했을 때, 시간초과가 난다는 것은 데이터 검색이 많은데 LinkedList를 사용함으로써 성능이 최악이 되어 시간 초과가 발생했다고ㅗ 해석할 수 있다. ArrayList로 바꿨을 때, 시간초과 문제가 해결됐다. => 한칸에 나무의 최대갯수(NxN개의 칸마다 k개의 나무들 요소 조회) vs 나무가 생기고 없어지는 횟수 => 전자는 검색 횟수, 후자는 데이터 삽입/삭제 횟수이다. 이 문제에서는 전자의 경우에 효율적인 자료구조인 ArrayList를 선택하는 것이 일반적인 better choice라고 할 수 있겠다. =>LinkedList를 이용해서도 풀 수 있다.(느리긴 하지만) 최초로 죽는 나무가 발생하면 이후의 요소들은 방문하지 않아도 되기 때문이다. 근데 이렇게 하면? 봄과 여름을 따로 구현해야한다?! 봄 : 양분 감소, 나이 증가 여름 : 양분 부족한 나무들 리스트에서 삭제, 죽는 나무 나이/2만큼 양분 증가 => 결론 : LinkedList를 사용해서 시간 초과가 난다면 ArrayList를 사용하자! LinkedList는 앞에서부터 탐색하기 때문에 최악의 경우 O(N)이지만, ArrayList는 O(1)이기 때문이다!

ArrayList에 데이터를 추가하는 경우