매번 이진힙 정렬, 쌩짜 정렬을 하지 않아도 되도록 deque 정도만 떠올린다면 생각없이 주어지는대로 구현해도 1172ms로 통과됩니다.
1차원일 경우 나무들을 복사한 임시 배열에서 번식 여부를 테스트 후 자손을 원 배열에 추가해야 하고 이 때문에 임시 배열 만드는 과정에서 시간이 소요되고, 2차원일 경우 (r, c) 지역에서는 번식을 해도 자손이 자기 자신 지역에게는 안 생기기 때문에 임시 배열을 만들 필요가 없어서 조금 더 빠른 걸로 보입니다. 계속 들여다봤는데 이거말고는 딱히 시간복잡도든 상수든 차이날 일이 없어보입니다.
딕셔너리로 관리하면 중복을 효율적으로 연산할 수 있으니 빠르단 건 알겠는데 매번 정렬을 해도 시간 초과가 안 난다는 것은 조금 이해하기, 떠올리기 어렵네요.
leeingyun96 2년 전
매번 이진힙 정렬, 쌩짜 정렬을 하지 않아도 되도록 deque 정도만 떠올린다면 생각없이 주어지는대로 구현해도 1172ms로 통과됩니다.
1차원일 경우 나무들을 복사한 임시 배열에서 번식 여부를 테스트 후 자손을 원 배열에 추가해야 하고 이 때문에 임시 배열 만드는 과정에서 시간이 소요되고, 2차원일 경우 (r, c) 지역에서는 번식을 해도 자손이 자기 자신 지역에게는 안 생기기 때문에 임시 배열을 만들 필요가 없어서 조금 더 빠른 걸로 보입니다. 계속 들여다봤는데 이거말고는 딱히 시간복잡도든 상수든 차이날 일이 없어보입니다.
딕셔너리로 관리하면 중복을 효율적으로 연산할 수 있으니 빠르단 건 알겠는데 매번 정렬을 해도 시간 초과가 안 난다는 것은 조금 이해하기, 떠올리기 어렵네요.