코딩테스트 복기 - 배열에서 특정 수보다 작은 수 중 가장 가까운 수를 찾는 방법(find nearest element than smaller one on the left side)

1. 문제

 

배열이 주어질때, 특정한 수보다 작으면서 가장 가까운 수를 찾고자 한다.

 

예를 들어 [3,1,2,10,5,6,4]가 주어질때, 10보다 작으면서 가까운 수는 바로 옆에 2와 5가 있다

 

이 경우 인덱스가 더 작은 2를 출력하고 싶고

 

1의 경우는 만족하는 원소가 없으므로 -1을 출력한다.

 

 

2. 풀이 - 왼쪽에서 더 작은 원소의 위치를 찾기

 

생각보다 어렵던데..? 그냥 많이 어려운데

 

적어도 생각나는건 $O(N^{2})$ 브루트 포스뿐.. 하지만 n이 10만이 넘어가는데 브루트 포스가 통과할리는 없을 것 같고

 

스택을 이용해서 O(N)에 효율적으로 풀 수 있다고 한다

 

알고리즘을 보면 의외로 간단하네.. 생각하기가 어렵지

 

일단 A의 i번째 원소에 대해 왼쪽에서 작으면서 가장 가까운 원소를 찾는다

 

그래서 A의 왼쪽에서부터 순회해서 스택이 비어있으면, A의 원소를 스택에 넣고 result에 -1을 넣는다

 

0번째 3보다 작은 원소는 존재하지 않으니까 -1

 

 

다음, A를 순회하다가 stack에 원소가 존재한다면, stack의 맨 위에 있는 원소와, 현재 A의 원소 크기를 비교한다.

 

stack의 원소는 A의 현재 i번째 원소보다 왼쪽에 있는 원소들이다.

 

또한, stack의 맨 위에 있는 원소일 수록 현재 i번째 원소와 위치상으로 가까운 원소이다.

 

stack에 든 원소 3은 현재 A의 원소 1보다 크므로, stack의 맨 위 원소를 제거

 

 

 

그리고 stack에 원소가 존재하지 않으므로, result에 -1을 넣어주고, 현재 i번째 원소 1을 stack에 넣어준다

 

 

 

이제 다음에 검사할 원소는 2인데 stack에 맨 위의 원소 1은 2보다 작다.

 

그러므로 2보다 작으면서 왼쪽에서 가장 가까운 원소는 1이다.

 

stack에서 빼지 않고, 2를 그대로 stack에 넣어주고 1은 result에 넣어준다

 

 

위 과정을 계속 반복한다면 result를 채울 수 있을 것 같다.

 

10의 경우 stack의 맨 마지막 2가 10보다 작으므로, 2를 result에 넣어주고, 10을 그대로 stack에 넣어주고

 

 

다음 5를 보면, stack의 맨 위인 10은 5보다 크니까 stack에서 제거하고,

 

그 다음 2가 5보다 작으므로... 2를 result에 넣어주고 5는 stack에 넣어주고

 

 

 

다음 6을 보면 stack의 마지막 5보다 크므로, 바로 6을 stack에 넣어주고 5는 result에 넣어주고

 

 

마지막으로 4를 보면, stack의 마지막 6은 4보다 크므로 stack에서 제거하고

 

다음 5도 4보다 크므로 stack에서 제거하고..

 

다음 2가 4보다 작으니 2를 result에 넣어주고 4는 stack에 넣어주면 알고리즘 종료

 

 

위는 특정 수와 가장 가까우면서 더 작은 정수 자체를 찾는 방법이고

 

다음 코드는 실제 문제로 나온 특정 수와 가까우면서 더 작은 원소의 인덱스를 찾는 과정

 

살짝 응용해서 스택에 원소를 담지 말고 index를 담으면 된다.

 

그리고 크기 비교할때는 index로 리스트에 접근해서 비교하면 될거고

 

#특정 수보다 왼쪽에서 가장 가까우면서 더 작은 원소를 찾는 과정

A = [3,1,2,10,5,6,4]

n = len(A)

result = []

#A의 i번째 원소보다 작은 원소를 담는다
stack = []
len_s = 0

#A를 왼쪽부터 차례대로 순회함
for i in range(n):
    
    #스택에 원소가 존재하지 않을때
    if len_s == 0:
        
        #가까운 원소가 존재하지 않는다
        result.append(-1)
        
        #현재 원소의 인덱스를 넣고, 스택의 길이 + 1
        stack.append(i)
        len_s += 1
    
    #스택에 원소가 존재하는 경우
    else:
        
        #스택에 원소가 존재하면서,
        #스택의 맨 위에 있는 원소가 현재 지정된 A의 i번째 원소보다 크거나 같을때,
        while (len_s != 0 and A[i] <= A[stack[-1]]):
            
            #스택에서 계속해서 원소를 제거한다
            stack.pop()
            len_s -= 1
        
        #반복문이 끝나고, 스택의 길이가 0이면,
        if len_s == 0:
            
            #A의 i번째 원소보다 작은 원소는 왼쪽에 존재하지 않는다
            result.append(-1)
        
        #스택에 원소가 존재한다면,
        #스택의 맨 위 원소는 A의 i번째 원소보다 작으면서 위치상으로 가장 가깝다
        else:
            
            result.append(stack[-1])
        
        #현재 i번째 원소를 스택에 넣어주고, 다음 i+1번째 원소를 검사하러 
        stack.append(i)
        len_s += 1

print(*result)
-1 -1 1 2 2 4 2

 

3. 풀이 - 오른쪽에서 더 작은 원소의 위치를 찾기

 

다음은 특정 수보다 더 작으면서 오른쪽으로 위치상 가장 가까운 원소를 찾는 과정

 

아이디어는 위와 동일하다

 

당연히 반대로 순회를 시작하는게 편하겠지?

 

오른쪽에서 왼쪽으로 차례대로 역으로 순회하기 시작해서,

 

스택에 원소가 존재하지 않는다면 result에 -1을 넣어주고,

 

스택에 현재 원소를 넣어주고

 

스택에 원소가 존재한다면, 스택의 길이가 0이 아니면서, 마지막 원소와 현재 A의 원소를 비교해서,

 

스택의 마지막 원소가 더 크다면, 스택에서 제거하고 

 

마지막 원소가 더 작다면, 스택에 현재 A의 원소를 넣어준다

 

#특정 수보다 작으면서 오른쪽에 가장 가까운 원소의 인덱스를 찾는 과정
A = [3,1,2,10,5,6,4]

result = []

stack = []
len_s = 0

#오른쪽에서 순회를 시작
for i in range(len(A)-1,-1,-1):
    
    #스택에 원소가 비어있다면,
    if len_s == 0:
        
        #현재 i번째 원소보다 오른쪽에서 더 작은 원소는 존재하지 않는다 
        result.append(-1)
        
        #결과에 원소를 담으면, 스택에 현재 원소의 인덱스를 담고
        stack.append(i)
        len_s += 1
    
    #스택에 원소가 존재한다면,
    else:
        
        #스택의 길이가 0이 아니면서,
        #스택의 맨 위 원소가 현재 i번째 원소보다 크거나 같다면,
        #스택의 맨 위 원소를 계속해서 제거한다
        while (len_s != 0 and A[i] <= A[stack[-1]]):
            
            stack.pop()
            len_s -= 1
        
        #반복문이 끝났을때, 스택에 원소가 존재하지 않는다면
        if len_s == 0:
            
            #결과에 -1을 넣어주고
            result.append(-1)
        
        #반복문이 끝나더라도 스택에 원소가 남아있다면
        else:
            
            #스택의 마지막 원소는 현재 i번째 원소보다 더 작으면서 
            #오른쪽에서 가장 가까운 원소이다.
            result.append(stack[-1])
        
        #결과를 담으면 스택에 현재 i번째 원소를 담는다
        stack.append(i)
        len_s += 1

#결과 리스트는 역순으로 담겨있다
print(*result)
print(*result[::-1])
-1 6 6 4 -1 -1 1
1 -1 -1 4 6 6 -1

 

주의할 점은 결과 리스트 result에 역순으로 담기기 때문에

 

제대로 볼려면 결과 리스트를 다시 재배열시키든지, 접근할때 n-i 이런식으로 접근하든지

 

그러면 두 방식으로 특정 i번째 원소보다  왼쪽에서 더 작으면서 가장 가까운 원소의 위치를 찾았고

 

오른쪽에서 더 작으면서 가장 가까운 원소의 위치를 찾았으니까..?

 

문제에서 요구하는 정답은?

 

왼쪽 result랑 오른쪽 result를 동시에 순회해서 둘 다 -1이라면... 더 작은 원소는 존재하지 않는거고

 

왼쪽이 -1인데 오른쪽이 -1이 아니라면? 오른쪽 값을 출력하고

 

왼쪽이 -1이 아니라면? 왼쪽 값을 출력하고

 

왼쪽도 -1이 아니고, 오른쪽도 -1이 아니라면? 왼쪽 값을 출력하고?

 

--------------------------------------------------------------------------------------------------------------------------------

 

이건 1차원적인 생각이고...

 

거리상으로 가까운 위치는 왼쪽이랑 오른쪽이랑 상관 없잖아

 

둘중 하나가 -1이면 -1이 아닌 곳의 위치를 출력하면 되겠지만

 

둘 다 -1이 아니라면? 왼쪽과의 거리랑, 오른쪽과의 거리를 비교해서 왼쪽, 오른쪽이랑은 상관없이 거리가 가까운 인덱스를 출력해야겠지

 

근데 둘이 거리가 같다면? 왼쪽 인덱스를 출력해야할거고

 

그래서 최종 코드는...

 

#특정 수보다 작으면서 가장 가까운 위치의 인덱스를 찾는 알고리즘

n = int(input())
A = list(map(int,input().split()))

right_side = []
left_side = []

stack = []
len_s = 0

#왼쪽에서 더 작은 원소를 찾는 과정
#A를 왼쪽부터 차례대로 순회함
for i in range(n):
    
    #스택에 원소가 존재하지 않을때
    if len_s == 0:
        
        #가까운 원소가 존재하지 않는다
        left_side.append(-1)
        
        #현재 원소의 인덱스를 넣고, 스택의 길이 + 1
        stack.append(i)
        len_s += 1
    
    #스택에 원소가 존재하는 경우
    else:
        
        #스택에 원소가 존재하면서,
        #스택의 맨 위에 있는 원소가 현재 지정된 A의 i번째 원소보다 크거나 같을때,
        while (len_s != 0 and A[i] <= A[stack[-1]]):
            
            #스택에서 계속해서 원소를 제거한다
            stack.pop()
            len_s -= 1
        
        #반복문이 끝나고, 스택의 길이가 0이면,
        if len_s == 0:
            
            #A의 i번째 원소보다 작은 원소는 왼쪽에 존재하지 않는다
            left_side.append(-1)
        
        #스택에 원소가 존재한다면,
        #스택의 맨 위 원소는 A의 i번째 원소보다 작으면서 위치상으로 가장 가깝다
        else:
            
            left_side.append(stack[-1])
        
        #현재 i번째 원소를 스택에 넣어주고, 다음 i+1번째 원소를 검사하러 
        stack.append(i)
        len_s += 1

stack = []
len_s = 0

#오른쪽에서 더 작은 원소의 인덱스를 찾는 과정
#오른쪽에서 순회를 시작
for i in range(n-1,-1,-1):

    #스택에 원소가 비어있다면,
    if len_s == 0:
        
        #현재 i번째 원소보다 오른쪽에서 더 작은 원소는 존재하지 않는다 
        right_side.append(-1)
        
        #결과에 원소를 담으면, 스택에 현재 원소의 인덱스를 담고
        stack.append(i)
        len_s += 1
    
    #스택에 원소가 존재한다면,
    else:
        
        #스택의 길이가 0이 아니면서,
        #스택의 맨 위 원소가 현재 i번째 원소보다 크거나 같다면,
        #스택의 맨 위 원소를 계속해서 제거한다
        while (len_s != 0 and A[i] <= A[stack[-1]]):
            
            stack.pop()
            len_s -= 1
        
        #반복문이 끝났을때, 스택에 원소가 존재하지 않는다면
        if len_s == 0:
            
            #결과에 -1을 넣어주고
            right_side.append(-1)
        
        #반복문이 끝나더라도 스택에 원소가 남아있다면
        else:
            
            #스택의 마지막 원소는 현재 i번째 원소보다 더 작으면서 
            #오른쪽에서 가장 가까운 원소이다.
            right_side.append(stack[-1])
        
        #결과를 담으면 스택에 현재 i번째 원소를 담는다
        stack.append(i)
        len_s += 1

#현재 위치 i와 left,right사이 거리를 계산하고, 
#최종 결과, 왼쪽 오른쪽에서 가장 가까운 원소의 위치를 찾는다.

result = []

for i in range(n):
    
    #right_side에는 역순으로 담겨있으니, 역으로 접근해야한다는 점에 주의해야한다
    if left_side[i] == -1 and right_side[n-i-1] == -1:
        
        result.append(-1)
    
    elif left_side[i] == -1 and right_side[n-i-1] != -1:
        
        result.append(right_side[n-i-1])
    
    elif left_side[i] != -1 and right_side[n-i-1] == -1:
        
        result.append(left_side[i])
    
    else:

        a = i - left_side[i]
        b = right_side[n-i-1] - i

        if a > b:
            
            result.append(right_side[n-i-1])
        
        else:
            
            result.append(left_side[i])

print(*result)
7
3 1 2 10 5 6 4
1 -1 1 2 2 4 2

 

스택 연습이 부족했나... 허허

 

알고보면 간단한데.. 복기해보니 더 놀랍다