> For the complete documentation index, see [llms.txt](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/undefined-1/arraylist-less-than-integer-greater-than.md).

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

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

![](https://3269900549-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MIbwNq54Ge4eqsziHM7%2F-MgA185w4dnxA9sN-Xwb%2F-MgA1FtCeyRnSHuTg4og%2Fimage.png?alt=media\&token=7f65f05e-7e2e-4bbb-a086-2b374e473eb6)

각 (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개의 나이만 저장하면 된다.

```java
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, 리스트에서 해당 나무 삭제)

```java
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개 이상의 배열을 초기화 또는 입력을 받을 수 있다!

   ```java
   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());
   			}
   		}
   ```

   ```java

   		//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 = &#x30;**,** 3/2 = **1**,총 1만큼만 합산되는 것인데, 1+3으로 먼저 다 합산하고 2로 나눠버리면 2가 더해지기 때문에 양분 합산되기 때문에 양이 틀리게 된다!!!

5. LinkedList를 사용했을 때 시간초과가 나는 이유 : ArrayList와 LinkedList의 차이점\
   [참고 자료 : https://www.holaxprogramming.com/2014/02/12/java-list-interface/](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)이기 때문이다!

![](https://3269900549-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MIbwNq54Ge4eqsziHM7%2F-MlN_xCds1_XJMkSogYM%2F-MlNbNDsoMqHIHk-d-CF%2Fimage.png?alt=media\&token=dd9b4fa3-8365-4fc1-beb3-2b2bc435986f)

![ArrayList에 데이터를 추가하는 경우](https://3269900549-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MIbwNq54Ge4eqsziHM7%2F-MlNcJ_ukNKPwOop3iZW%2F-MlNcjWBM5t3uLu0ArJn%2Fimage.png?alt=media\&token=e7548fdb-1dc2-4f53-970a-f7f9116da9e1)