kotlin 프로그래머스 lv2 뒤에 있는 큰 수 찾기

해당문제를보고  for문에 담아서 현재i번째에있는 numbers의 요소와 i보다 큰 번째에있는 요소와 비교해서

현재요소가 작다면 큰요소를 현재위치에 삽입하고, 현재요소보다 큰요소가 없다면 -1을 대입하는 생각을 했다.

그래서 코드는 아래와 같이 바로 작성했다.

하지만 시간초과가 났고, for문때문에 시간이 오래걸린것이라 생각이 들었다.

다른 사람들의 풀이를 찾아보니 stack알고리즘을 이용하였다.

스택을 사용하는 이유를 찾아보았고, 다음과 같았다.

1.스택을 사용하여 이전에 처리한 요소들의 인덱스를 추적한다.

2. 주어진 배열을 왼쪽에서 오른쪽으로 반복하면서 각 요소에 대해 다음과 같이 수행한다.

-스택이 비어있지 않고, 현재 요소보다 작은 요소들의 인덱스가 스택에 남아있다면, 해당 작은 요소들에 대한 결과를 결정한다.

-스택의 top에있는 요소보다 현재 요소가 크다면, 해당 작은 요소들에 대한 결과가 현재 요소가 된다.

-이러한 과정을 거치면서 이전에 처리한 작은 요소들에 대한 결과를 업데이트하고, 스택에서는 더 이상 필요하지 않은

인덱스를 제거한다.

3. 스택에는 현재 요소의 인덱스가 남아있게 되는데, 이는 아직 오른쪽에 더 큰 값을 찾아야 함을 의미한다.

스택 알고리즘의 시간 복잡도는 O(n)이고 배열의 모든 요소를 한 번만 탐색하기 때문에 for문을 사용하는 것보다 더 효율적이다.

코드는 아래와 같이 작성했다.

 

스택은 각 요소의 인덱스를 저장한다.

작은 숫자가 나타나면 현재 위치보다 오른쪽에 더 큰 숫자를 찾을 때까지 요소의 인덱스를 저장해나간다.

while문은 스택이 비어있지 않고, 스택의 top요소가 현재 요소보다 작을 때까지 실행된다.

stack.peek()은 스택의 맨 위에 있는 요소의 인덱스를 반환한다.

이 인덱스를 사용하여 배열에서 값을 가져온다.

만약 현재 요소보다 큰 값을 발견하면, 해당 값을 저장하고 스택에서 해당 요소를 꺼낸다.

스택에 현재 요소의 인덱스를 추가하여 계속해서 다음 요소를 처리할 수 있도록 한다.

1. 의도와 이유: 배열에서 각 요소의 "뒤에 있는 더 큰 값"을 찾는 문제를 해결하는 것 스택을 사용하여 효율적으로 이 문제를 해결 스택은 현재 요소 이후에 처리해야 할 요소의 인덱스를 추적하면서, 더 큰 값이 나타나면 해당 값을 업데이트 2. 코드 동작 로직: 입력 배열을 왼쪽에서 오른쪽으로 반복하며 각 요소에 대해 다음을 수행 스택이 비어 있지 않고, 스택의 맨 위 요소가 현재 요소보다 작으면, 스택의 맨 위 요소가 나타내는 인덱스에 대한 답안 배열을 업데이트 현재 요소의 인덱스를 스택에 추가 이렇게하면 스택은 항상 현재 요소 이후에 처리해야 할 요소들의 인덱스를 유지하면서, 뒤에 있는 더 큰 값이 나타나면 해당 값을 답안 배열에 업데이트함 3. 버그 또는 오류와 해결책: 처음에 이중 for문 작성으로 시간초과 오류가 떴으나, 스택을 이용한 이후 에러 해결됨