소프티어

어떤 방식으로 해도 배열을 탐색하면서 다시 특정 배열을 탐색해야하는데, 이것은 최악의 경우 O(n^2)이 나올꺼라고 판단됩니다.

그리고 코테에서는 최악의 경우 또한 고려해서 문제를 만들었을 것이 분명하다고 생각하기에, 그냥 항시 O(n^2)이 나오는 코드로 작성했습니다

class List {
    constructor(length) {
        // 편의를 위해 배열 0 은 비워두기
        // [0] => index(v) 보다 큰 것을 찾아야하는 개수
        // [1] => index(v) 보다 작은 것을 찾아야하는 개수
        // [1] 이 만족되면 - 시키고 result에 개수 추가
        this.list = Array.from({length}, () => [0,0]);
        this.result = 0
    }

    add(value) {
        // 신규 값 추가
        // 이것보다 작은 것에 대해서 탐색 후, 해당 값의 [0] 값을 [1] 로 더해주기, [0] 을 제거하는게 아님
        // 이것보다 큰 값에 대해서 탐색 후, 해당 값의 [1] 값을 result 로 더해주기, [1] 을 제거하는게 아님
        // 따라서 기본적으로 배열을 전부 탐색하는 건 어쩔 수 없다.
        // 기본 배열 탐색이 O(n), 탐색 때 마다 List를 탐색해야하니 이것도 O(n), 결국 시간복잡도는 O(n^2)
        this.list.forEach((_, currentValue) => {
            if (currentValue < value) {
                // 1 < 2 를 만족하는 수열이 this.list[currentValue][0] 만큼 새로 생겼으니, 그것을 [1]에 추가
                this.list[currentValue][1] += this.list[currentValue][0]
            }
            else if (currentValue > value) {
                // 1 > 3 을 만족하는 수열이 this.list[currentValue][1] 만큼 새로 생겼으니, 그것을 result 에 추가
                this.result += this.list[currentValue][1]
            }
            else if (currentValue === value) {
                // 같으면 그냥 추가
                this.list[currentValue][0]++
            }
            else {
                // 그 외에는 무시
            }
        })
    }

    getResult() {
        return this.result
    }


}


// 입력처리
const fs = require('fs')
const input = fs.readFileSync('input.txt', 'utf8')
    .trim()
    .split(/\n+/)
const sequence = input[1].split(' ').map(Number)

const list = new List(5001)

sequence.forEach(v => {
    list.add(v)
})

console.log(list.getResult())

/*
수열을 앞에서 부터 읽어나감
특정 값보다 크거나 작은 것만 고려하면 됨, 1 < 2, 1 > 3. 여기서 1 2 3 의 수열 완성을 위해서는 1하고 2, 3을 각각 비교하면 되기에 2, 3의 값은 저장할 필요가 없음
따라서 배열은 1의 값만을 저장하고, 현재까지 배열을 *순서* 대로 읽어나가서 몇 단계에 몇개의 부분 수열들이 대기 중인지만 기록
 */