기초 알고리즘 1/2. 201 - 자료 구조 1(연습)
17298번. 오큰수

문제

17298번 문제 링크

메모리 초과

const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const N = Number(input[0]);

const arr = input[1].split(" ").map((item) => Number(item));

// 답을 넣을 배열
let ans = [];

for(let i = 0; i < N; i++){
    // A_i를 정해준다.
    let pivot = arr[i];
    
    // NGE 후보자들을 넣을 배열
    let candidate = [];
    
    // pivot의 오른쪽부터 연산을 진행해야하므로 j는 i+1 부터 시작한다.
    for(let j = i + 1; j < N; j++){
        // 하나씩 NGE 변수에 넣어서 조건 판별을 해보자.
        let NGE = arr[j];
        
        // NGE 후보가 될 숫자를 정한다.
        if(NGE > pivot){
            // 조건을 만족하면 후보자 배열에 넣는다.
            candidate.push(NGE);
        }
    }
    
    // candidate 배열은 arr에서 인덱스가 작은 것부터 앞에 들어가는 스택 구조를 가진다.
    // 따라서, arr에서 가장 왼쪽에 있던 것을 NGE로 설정하기 위해 candidate 배열 가장 앞에 있는 것을 사용한다.
    // 단, candidate 배열에 아무것도 없다면 -1을 ans에 넣어준다.
    if(candidate.length > 0){
        ans.push(candidate[0]);
    } else {
        ans.push(-1);
    }
}

console.log(ans.join(" "));

아무래도 candidate 배열을 사용한 것이 메모리 초과의 원인이 아니었을까싶다.
사용하지 않아도 구현할 수 있기 때문이다.
한번 제거해보자.

시간 초과

const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const N = Number(input[0]);

const arr = input[1].split(" ").map((item) => Number(item));

// 답을 넣을 배열
let ans = [];

outer:for(let i = 0; i < N; i++){
    // A_i를 정해준다.
    let pivot = arr[i];
    
    // 두 번째 for문에서 NGE가 없다면, ans의 length는 noNGE일 것이다.
    let noNGE = ans.length;
    
    // pivot의 오른쪽부터 연산을 진행해야하므로 j는 i+1 부터 시작한다.
    inner:for(let j = i + 1; j < N; j++){
        // 하나씩 NGE 변수에 넣어서 조건 판별을 해보자.
        let NGE = arr[j];
        
        // NGE 후보가 될 숫자를 정한다.
        if(NGE > pivot){
            // 조건을 만족하면 후보자 배열에 넣는다.
            // arr에서 가장 왼쪽에 있던 것을 NGE로 설정하기 때문에
            // 가장 먼저 조건을 만족하는 숫자가 곧 NGE가 된다.
            ans.push(NGE);
            
            // NGE를 찾았으므로 다음 pivot을 설정한다.
            continue outer;
        }
    }
    
    // 두 번째 for문이 완료되었는데도 ans의 length가 변하지 않았다면, -1을 넣는다.
    if(ans.length === noNGE){
        ans.push(-1);
    }
}

console.log(ans.join(" "));

메모리 초과 문제를 해결하기 위해서 candidate 배열을 사용하지 않고 구현했는데, 이번에는 시간 초과 문제가 발생했다.
똑같이 이중 for문을 사용했는데, 심지어 사용하는 배열 숫자는 줄었는데..

outer, inner를 없애고 continue를 break로 바꿔도 시간 초과 문제는 해결되지 않았다.

그렇다면...자료 구조를 이용하는 수밖에 없겠다고 판단된다.

solution

const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const N = Number(input[0]);

let arr = input[1].split(" ").map((item) => Number(item));

let stack = [];

for(let i = 0; i < N; i++){
    while(stack.length > 0 && arr[stack[stack.length - 1]] < arr[i]){
        arr[stack.pop()] = arr[i];
    }
    
    stack.push(i);
}

while(stack.length > 0){
    arr[stack.pop()] = -1;
}

console.log(arr.join(" "));

이번 문제는 다른 분들 풀이를 봐도 이해가 잘 안됐다.
예시를 직접 작성해서 이해를 해보고자한다.

입력 데이터
4
3 5 2 7

초기 상태는 다음과 같다.
첫 번째 숫자 4는 데이터의 길이 N
arr = [3,5,2,7]
stack = []

for문이 시작된다. i = 0.

현재 stack의 상태는 []. 빈 배열이다. 즉, length는 0.
따라서, stack에 i가 push된다.
stack = [0]
arr = [3,5,2,7]

다음 for문이 실행된다. i = 1.
이번엔 stack.length가 1이다.

arr[stack[stack.length - 1]]에 값을 대입해보면 다음과 같다.
arr[stack[0]] -> arr[0] -> 3
arr[i]는 arr[1] -> 5
따라서 arr[stack[stack.length - 1]] < arr[i]는 true이므로
while문 조건이 만족된다. 반복이 시작된다.

arr[stack.pop()] = arr[i]
위 식은 다음과 같다.
arr[0] = arr[1]
따라서 arr은
[3,5,2,7] -> [5,5,2,7]이 된다.
stack은 pop으로 인하여 []. 빈 배열이 된다.

stack = []
arr = [5,5,2,7]

따라서, while문의 조건을 불만족.
아래의 stack.push(i)가 실행된다.
stack = [1]
arr = [5,5,2,7]

다음 for문으로 넘어간다.
다음 for문. i = 2.
stack.length는 1이다.
arr[stack[stack.length - 1]] < arr[i]
-> arr[stack[0]] < arr[2]
-> arr[1] < arr[2]
-> 5 < 2
-> false
while문의 조건을 만족하지 않기 때문에
stack.push(i)가 실행된다.

stack = [1,2]
arr = [5,5,2,7]

다음 for문으로 넘어간다.
다음 for문. i = 3.
stack.length가 2이다.
arr[stack[stack.length - 1]] < arr[i]
-> arr[stack[1]] < arr[3]
-> arr[2] < arr[3]
-> 2 < 7
-> true

while문 조건을 만족한다.
따라서, arr[stack.pop()] = arr[i]
-> arr[2] = arr[3]
-> arr = [5,5,7,7]
stack = [1]

다시 while문이 실행한다.
stack.length는 1이다.
arr[stack[stack.length - 1]] < arr[i]
-> arr[stack[0]] < arr[3]
-> arr[1] < arr[3]
-> 5 < 7
-> true
조건을 만족하므로 내부를 실행한다.

arr[stack.pop()] = arr[i]
-> arr[1] = arr[3]
-> arr = [5,7,7,7]

stack = []
arr = [5,7,7,7]

또 다시 while문이 실행된다. 이번에는 length 조건이 false.
따라서 stack.push(i)가 실행된다.
stack = [3]

이제 반복문이 끝났다.
아래쪽 while문으로 이동한다.
stack.length가 2이므로 조건을 만족, 실행된다.
stack에서 pop을 통해 length를 줄여나가고, length가 0이 되면 반복이 종료된다.

arr[stack.pop()] = -1

arr[3] = -1
-> arr = [5,7,7,-1]

while 반복 종료.

예시를 쭉 나열해봤는데, 아직도 이해가 어렵긴하다..

참고 자료 2에 있는 분의 설명을 인용하겠다.

stack에 arr 원소값의 인덱스를 넣어주고,
다음 인덱스의 arr값이 stack에 들어있는 인덱스의 arr값보다 크다면,
그 앞의 값들의 오큰수는 해당 arr의 값이 되므로,
해당 arr의 값을 아예 오큰수의 값으로 바꿔주는 방식이다.
(이 방법이 필자가 해결하지 못했던 메모리 초과에 대한 부분을 해소해주는 것으로 생각된다.)

만약 stack에 값이 남아있다는 것은,
stack의 값을 인덱스로 가지는 arr의 값이 가장 큰 수로,
해당 값의 오른쪽에 더 큰 수가 없거나,
아예 비교할 다음 값이 없는 경우를 의미한다.
이 때는 -1을 넣어줘야한다.

참고 자료

참고 자료 1
참고 자료 2