16235번 - 나무 재테크
우선 ArrayList 에 모든 나무들을 add하여 해당 list를 탐색하며 진행합니다.아래와 같이 소스 짰는데 시간초과가 뜹니다.
ArrayList[][] map 이렇게 해서 map의 좌표별로 ArrayList 를 받아와서 돌린 것과
map의 x,y 좌표와 상관없이 아래 처럼 하나의 ArrayList 로 돌리다 다 똑같지 않나요...?
전자 (map 좌표별로 ArrayList 받아오기) 의 경우는 시간안에 들어옵니다...
ArrayList remove 함수 호출 시에 list의 size가 커진 만큼 Shift 하는데 오래 걸려서 그런걸까요?
ArrayList<T> 의 remove함수의 시간복잡도는 O(N)입니다.
예상이 맞았네요 ㅠ 감사합니다.
댓글을 작성하려면 로그인해야 합니다.
windy10928 4년 전 1
우선 ArrayList 에 모든 나무들을 add하여 해당 list를 탐색하며 진행합니다.
아래와 같이 소스 짰는데 시간초과가 뜹니다.
ArrayList[][] map 이렇게 해서 map의 좌표별로 ArrayList 를 받아와서 돌린 것과
map의 x,y 좌표와 상관없이 아래 처럼 하나의 ArrayList 로 돌리다 다 똑같지 않나요...?
전자 (map 좌표별로 ArrayList 받아오기) 의 경우는 시간안에 들어옵니다...
ArrayList remove 함수 호출 시에 list의 size가 커진 만큼 Shift 하는데 오래 걸려서 그런걸까요?