(JAVA) 백준 16235번 : 나무 재테크

https://www.acmicpc.net/problem/16235

16235번: 나무 재테크

 

 

삼성 SW A형 코딩테스트 기출 문제 중 하나이다.

 

시뮬레이션이고

 

 

요구 조건에 대해 알고리즘을 작성하면 되지만

 

 

 

제한 시간

 

제한 시간 ..

 

제한 시간 ....!!

 

 

제한 시간이 너무 짧아서

 

 

처음에는 LinkedList 를 쓰다가

 

시간 초과로 

 

PriorityQueue 를 썼는데도

 

시간 초과로

 

찾다가 찾다가

 

Deque를 사용하니 되었다.

 

 

하지만

 

어떤 자료구조를 사용했냐가 아니라

 

 

" 정렬을 사용하지 않고 자료구조의 시간복잡도를 줄이는 것 "

 

 

이 핵심이다!

 

맨 처음 입력받을 때만 정렬해주고

 

이후에는 정렬할 필요가 없는 이유가

 

 

  - 어차피 나이의 증가는 동일하게 1이다.

  - 새로운 나무들의 나이는 무조건 1이다.

 

 

이기 때문에

 

 

봄에는 하나씩 앞에서부터 꺼내서 나이만 증가시키면 되고

가을에는 새로운 나무들을 맨 앞에 넣기만 하면 된다.

 

*** 삭제는 어디에서 해도 상관이 없다. 맨 처음 정렬되어있기 때문에.

**** 근데 굳이 Deque를 사용하지 않고 LinkedList 2차원 배열로 사용해도 해결 가능하다.

 

 

 

*** Deque에 대한 간단한 설명 포스팅

요소 추가하기(출처 : https://drive.google.com/file/d/1kdEOJ92mNALKBrCdyU6KJJE_JsFLNWJV/view)

 

요소 제거하기(출처 : https://drive.google.com/file/d/1kdEOJ92mNALKBrCdyU6KJJE_JsFLNWJV/view)

 

 

매커니즘

---

1.  2차원 int 배열 (현재 양분 지도), (겨울마다 제공받는 양분의 크기 지도) 생성

*** class Tree(int x, int y, int year) 클래스 생성

 

 

2.  양분, 나무 입력받기

*** 나무를 임시 ArrayList에 저장한 후 ArrayList를 오름차순 정렬, 그 뒤 Deque에 집어넣는다.

*** Deque는 sort할 라이브러리가 없어서! 

 

 

3.  while문을 통해 year이 k가 될 때 까지 사계절 반복

 

 

4.  봄 + 여름 같이 진행

4-1.  임시 Deque 객체, ArrayList 객체 생성

 

4-2.  나무 객체들 저장한 Deque Empty() 까지 while문 수행

 

4-3.  양분이 부족한 경우 ArrayList에 poll()한 Tree 추가

 

4-4.  양분이 충분한 경우 사용한 양분 감소 , 임시 Deque에 offerLast 수행.

 

4-5.  임시 Deque 객체 기존 Tree Deque 객체와 Copy

 

4-6.  여름 - 죽은 나무 양분 주기 : ArrayList 탐색하며 양분 값 감소시키기 (Math.floor() 사용해서 소수점 버림)

 

 

5. 가을 진행

5-1.  나무 객체들 저장한 Deque Empty() 까지 while문 수행

 

5-2.  나무의 나이 % 5 == 0 (5의 배수) 체크하기

 

5-3.  5의 배수인 경우 주위 8곳에 나무 심기 (당연히 Map 범위 체크)

 

5-4.  새로운 나무 심게 되는 경우 임시 Deque 객체에 offerFirst() 로 front에 집어넣기

 

5-5.  기존 나무 임시 Deque 객체에 offerLast()로 rear에 집어넣기

 

5-6.  임시 Deque 객체 기존 Tree Deque 객체와 Copy

 

 

6.  겨울 진행

6-1.  map을 돌며 양분 추가

 

 

 

*** Deque Copy하지 않는 방법도 생각해보면 좋겠다.

 

 

감사합니다.

 

 

소스코드

---