dladydwo123   2년 전

히스토그램 문제의 풀이법에, 스택 쌓기를 이용한 O(N)풀이법에 영감을 받아서 O(NlgN)풀이법을 생각해 보았습니다. 논리를 설명해보자면,

 우선, info 배열은 초기 방어선 입력값입니다.

asm_info 배열은 info 배열을 정방향으로 진행하면서, 해당 index에서 부터 연속된 오름차순을 얼마나 쌓을 수 있는지를 저장.

dsc_info 배열은 info 배열을 역방향으로 진행하면서, 해당 index에서 부터, 연속된 내림차순을 얼마나 쌓을 수 있는지를 저장했습니다. 

마지막은 탐색 과정인데, info에서, 정방향으로 순회하면서, asm_info[index] + info[index]값보다 작은 값으로 시작하는 값중 최대길이 dsc_info[pos]을 더해서 전체 순회하여, 최댓값을 구해주었습니다. 이때, pos값은 오름차순으로 정렬된값이기 때문에 O(lgN)이라고 생각하여, index전체순회로 결국은

O(MlgN)풀이법이라고 생각했습니다. 

Q. 혹시 시간을 더 줄일 방법 없나요?

Q. 제가 생각한 시간복잡도는 유효한가요?

jseo   2년 전

  1. 일단 굳이 asm_info, dsc_info 를 스택을 이용해서 구할 필요는 없다고 생각합니다.

asc_info 같은 경우 역순으로 반복문을 돌면서 asc_info[i] = (info[i] < info[i + 1]) ? (asc_info[i + 1] + 1) : 1 같은 식으로 더 간단하게 구할수 있습니다 (dsc_info도 비슷함)

2. 탐색 과정은 N lg N이 아니라 N^2입니다.

 주어진 입력이 1, 2, 3, 4, 5, 6, ..., N인 경우를 생각해보세요.


map, set 같은 self-balancing BST 자료구조를 쓰지 않는 이상 풀기는 좀 힘들것 같습니다.

monotonicity를 유지할수 있는 자료구조가 필요한데, 이 문제 같은 경우 덱/스택 같은걸로 효율적이게 하기는 어렵거든요.

댓글을 작성하려면 로그인해야 합니다.