[BOJ] 백준 16235번: 나무재태크

date

Jul 4, 2023

slug

boj-16235

author

status

Public

구현내용

나무 정보를 어떤 자료구조로 저장할 것인지가 중요한 문제

봄에 나무들이 양분을 먹을 때, 나무의 나이 순서대로(어린 순) 양분을 먹기 때문에 나무 나이 순으로 정렬 과정이 필요하다.

그러나 list를 사용하면서 매 봄마다 sort를 하게 되면 시간초과(TLE)를 피할 수 없다.

따라서 나는 우선순위큐를 사용하여, 정렬을 하지 않아도 항상 어린 순서로 나무를 조회할 수 있도록 하였다.

‘입력으로 주어지는 나무의 위치는 모두 서로 다름’ 이라고 되어 있기 때문에, 한 구역에 처음 심어지는 나무는 최대 1개로 제한된다.

따라서 봄-여름-가을-겨울 시기를 지나며 한 구역에 심어지는 나무의 수가 1개 이상으로 늘어나더라도 그 순서는 변하지 않는다. (가장 처음에 심어지는 나무 > 그 이후에 번식하는 나무 > 그 이후… > 그 이후… 순서로 유지)

따라서 가을 번식 때 심어지는 나이=1 의 나무는 left로 넣어준 후, 나무의 양분을 먹을 때에는 popleft()로 꺼내서 양분을 비교하면 된다.