배열에서 자신보다 큰, 가장 가까운 숫자 찾기 : Programming Story

배열에서 자신보다 큰, 가장 가까운 숫자 찾기

배열이 있고, 배열에서 자신 index에서 가장 가까운, 자기보다 큰 숫자를 찾고 싶다면 어떤 식으로 구현할 수 있을까?

즉 예를 들어, 2 6 4 8 5 라는 배열이 있다면 6에서 가장 가까운 자신보다 큰 숫자는 8이고, 4에서 가장 가까운 자신보다 큰 숫자는 6 또는 8이 된다.

이를 위해서는 먼저 배열의 왼쪽 index부터 시작하면서 Stack을 하나 만들어 자신보다 오른쪽에 있는 값 중에 큰 값을 먼저 검사하고, 자신 index의 왼쪽에 있어도 큰 숫자가 있을 수 있기 때문에 배열의 오른쪽 index부터 시작하여 역순으로 또 Stack을 검사해준다.

먼저 배열의 왼쪽 index부터 검사하여 자신보다 오른쪽에 있는 원소 중에서 큰 값을 찾는 부분을 살펴보겠다.

class Pair {
    int first, second;
    Pair(int first, int second) {
        this.first = first;
        this.second = second;
    }
}

우선 class Pair를 만들어서 first에는 index를 저장하고, second에는 값을 저장하는 식으로 진행해보겠다.

그런 다음에 각각 배열에 자신보다 큰 값의 index를 저장할 수 있도록 새로운 배열을 추가로 두 개 만들어준다.

int[] lg = new int[n+1]; // 자신보다 왼쪽에 있는 수들 중에 큰 값의 index
int[] rg = new int[n+1]; // 자신보다 오른쪽에 있는 수들 중에 큰 값의 index

그리고 lg의 값은 0으로 초기화해주고, rg의 값은 배열의 크기 +1로 초기화해준다. 나중에 검사할 때 여전히 0 또는 배열의 크기 +1 인 경우에는, 왼쪽/오른쪽에 자신보다 큰 값이 없다는 것을 뜻해주는 것이기 때문이다.

 for (int i=1; i<=n; i++) {
            lg[i] = 0;
            rg[i] = n+1;
        }

그리고 Stack을 만들어주고 첫 번째 원소를 push해준다.

Stack<Pair> sg = new Stack<>();
sg.push(new Pair(1, a[1]));

이제 우리는 rg 배열의 값부터 찾아볼 것인데 이러면 배열 index의 가장 왼쪽부터 시작하면서 아래와 같은 코드를 반복하면 된다.

 for (int i=2; i<=n; i++) {
                while (!sg.isEmpty() && a[i] >= sg.peek().second) {
                    rg[sg.peek().first] = i;
                    sg.pop();
                }
                sg.push(new Pair(i, a[i]));
                }

이러면 이미 stack에 있던 원소들보다 해당 원소가 클 경우 해당 원소의 index가 rg 배열의 값으로 들어가기 때문에 자신보다 오른쪽에 있는 수 중에 큰 값을 찾을 수 있다.

반면 가장 큰 원소의 경우에는 오른쪽에도 자신보다 큰 원소가 없을 것이기 때문에 pop()이 한 번도 되지 않아 원래 초기의 값이 유지되고 있을 것이다.

위에까지가 자신의 배열 index보다 큰 index의 수들 중 가장 가까운 큰 값의 index를 저장하는 과정이었다. 이제 반대로 자신의 배열 index보다 작은 index의 수들 중 가장 가까운 큰 값의 index를 lg에다 저장해보자. lg는 왼쪽에서 찾아야 하기 때문에 for문을 오른쪽에서 왼쪽으로 돌아야 한다.

이 부분도 마찬가지로,

Stack<Pair> sg = new Stack<>(); // stack greater
sg.push(new Pair(n, a[n]));

stack을 하나 만들어주고 첫 번째 원소를 push해준다. 하지만 lg를 구할 때는 가장 오른쪽 index부터 for문을 돌기 때문에 첫 번째 원소가 n번째 원소가 되게 된다.

그런 다음에 for문을 위와 완벽하게, 반대로 돌면 우리는 lg 배열을 구할 수 있다.

for (int i=n-1; i>=1; i--) {
                while (!sg.isEmpty() && a[i] > sg.peek().second) {
                    lg[sg.peek().first] = i;
                    sg.pop();
                }
                sg.push(new Pair(i, a[i]));
                }

이런식으로 하면 rg에는 자신의 index보다 오른쪽에 있는 수 중 가장 가까운 큰 수의 index가 저장되어 있을 것이고, lg에는 자신의 index보다 왼쪽에 있는 수 중 가장 가까운 큰 수의 index가 저장되어 있을 것이다. 전체적으로 가장 가까운 index의 수를 찾기 위해서는 rg와 lg 중에서 min 값을 찾아주면 된다. 만약 두 값이 같다면 문제에서 요청하는 대로 풀어주면 될 것이다.

Programming Story

배열에서 자신보다 큰, 가장 가까운 숫자 찾기

배열에서 자신보다 큰, 가장 가까운 숫자 찾기

관련 백준 문제

문제

입력

출력