Algorithm Find higher number in the next element

알고리듬 Find higher number in the next element를 알아보겠습니다.

​
배열에서 각 숫자마다 뒤에 올 숫자 중에 큰 숫자가 있는지 확인하는 알고리듬을 알아봅시다.
8, 4, 2, 5가 들어있다고 칩시다.
4와 2가 큰 숫자가 나옵니다.

이것을 구하기는 쉽지 않습니다.

8의 결과를 보려면 5가 나올 때까지 기다려야 하기 때문이죠.

​

​

그래서 뒤집어서 생각합니다.

5 다음에 작은 숫자가 나오면, 5가 이전보다 큰 숫자라는 의미가 되니까요.

먼저 스택(Stack)에 5를 집어넣습니다.

2가 5 보다 작으므로 2를 집어넣습니다.

4는 2 보다 큼으로 2는 비교 대상에서 제거합니다.

4는 5 보다 작으므로 스택에 넣습니다.

8은 4 보다 큼으로 4를 비교 대상에서 제거합니다.

8은 5 보다 큼으로 5를 비교 대상에서 제거합니다.

아무것도 남아있지 않으므로 8보다 큰 값은 여기에 없습니다.

스택에 들어갔던 2와 4만이 다음 값에 큰 값을 가지고 있습니다.

​

이것은 함축적으로 모든 배열 값들과 비교하는 것과 같습니다. 8과 4를 비교하는 것은 8과 2를 비교하는 것을 포함하는 결과이기 때문입니다.

​

​

코드로 한 번 봅시다.

6 번째 줄에서 배열을 거꾸로 반복합니다.

7 번째 줄에서 스택이 비어있으면 큰 값이 없다는 뜻이므로 False를 넣습니다.

12 번째 줄에서 스택의 위에 값과 현재 배열의 값을 비교해서 현재 값이 작다면 스택에 넣습니다.

16 번째 줄에서 만약 아니라면 계속해서 위에 값을 비교합니다. 17 번째 줄에서 작은 값이 있다면 참이고, 22 번째 줄에서 스택이 비어 있다면 거짓을 넣습니다.

끝.

카테고리: Algorithm