백준 js 17299: 오등큰수

문제

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오등큰수 NGF(i)를 구하려고 한다.

Ai가 수열 A에서 등장한 횟수를 F(Ai)라고 했을 때, Ai의 오등큰수는 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오등큰수는 -1이다.

예를 들어, A = [1, 1, 2, 3, 4, 2, 1]인 경우 F(1) = 3, F(2) = 2, F(3) = 1, F(4) = 1이다. A1의 오른쪽에 있으면서 등장한 횟수가 3보다 큰 수는 없기 때문에, NGF(1) = -1이다. A3의 경우에는 A7이 오른쪽에 있으면서 F(A3=2) < F(A7=1) 이기 때문에, NGF(3) = 1이다. NGF(4) = 2, NGF(5) = 2, NGF(6) = 1 이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

출력

총 N개의 수 NGF(1), NGF(2), ..., NGF(N)을 공백으로 구분해 출력한다.

예제 입력 1 복사

7

1 1 2 3 4 2 1

예제 출력 1 복사

-1 -1 1 2 2 1 -1

 

접근

17298과 비슷하다.

다른 부분은 배열 input의 값에 해당하는 input[i]의 중복 count를 비교해야 한다.

예를 들어 input = [1, 1, 2, 3, 4, 2, 1]이라면,

중복 count(F(i)), F(0) = 3 이된다. 이 F를 배열로 표현하면

F=[3,3,2,1,1,2,3] 이 된다. 이 F에서 F[i]오른쪽에 있는 수 중 가장 큰 왼쪽에 있는 수를 구하면 된다.

 

그래서 처음에 문제를 풀 때는 각 input[i]에 중복 count를 구해서 F배열에 F[i]에 해당하는 중복 count를 넣었다.

let F = [];
for (let x of input) {
  let re = `${x}`;
  const reg = new RegExp(re, "g");
  F.push(strInput.match(reg).length);
}
console.log(F);

그리고 루프를 통해 F[i]와 F[stack.top()]을 비교해서 답을 구하려했는데,

메모리 초과가 떴다. 아마 F[] 배열이 새로 생성되는 과정에서 메모리가 초과된 듯해서 다시 고민을 했다.

 

메모리를 잡아먹는 배열을 최소화해서 풀기 위해서 F라는 배열을 따로 만들지 않고,

중복 없이 input의 각 값들을 key로, 중복 count를 value로  하는 count 객체를 하나 생성했다.

예) count = {1: 3, 2: 2, 3: 1, 4:1}

그리고 나서 똑같이 루프문 내에서 비교를 하는데, 따로 배열이 없으니 count의 key에 해당하는 input[i]의 value를 찾는 식으로 조건문을 바꿨다.

for (let i = 0; i < input.length; i++) {
  // input[i]에 대응하는 count value와 input[stack[stack.top()]]에 value
  // 1️⃣
  while (
    stack.length &&
    count[input[stack[stack.length - 1]]] < count[input[i]]
    // ①stack에 top에 있는 수를 인덱스로 갖는 input의 값을 key로 갖는 count의 value와 
    // ②input[i]를 key로 갖는 count의 value 를 비교
  ) {
    result[stack.pop()] = input[i];
  }
  // 2️⃣
  stack.push(i);
}

①과②에서 구하려는 count[input[stack[stack.top()]] || input[i]] 는 모두 앞서 구했던 F[stack[stack.top()] || F[i] 와 같다.

 

input = [1, 1, 2, 3, 4, 2, 1]

count = { '1': 3, '2': 2, '3': 1, '4': 1 }

result = [-1, -1, -1, -1, -1, -1, -1]

1️⃣과 2️⃣를 구하는 과정을 보면

i = 0 일 때:

1️⃣stack = [] 이므로 넘어간다

2️⃣stack = [0] 이 된다.

 

i = 1 일 때:

1️⃣stack = [0]

stack[stack.top] 은 0,

input[0]은 1,

count[1] = 3

①은 3, ②는 3 이므로 넘어간다.

2️⃣

stack = [0,1]이 된다.

 

i =  2일 때:

1️⃣stack = [0, 1]

stack.top = 1

① 은 3, ②는 2 이므로 넘어간다.

2️⃣

stack = [0, 1, 2] 된다.

 

i = 3 일 때:

1️⃣stack = [0, 1, 2]

stack.top = 2

① 은 2, ②는 1 이므로 넘어간다.

2️⃣

stack = [0, 1, 2, 3] 된다.

 

i = 4 일 때:

1️⃣stack = [0, 1, 2, 3]

stack.top = 3

① 은 1, ②는 1 이므로 넘어간다.

2️⃣

stack = [0, 1, 2, 3, 4] 된다.

 

i = 5 일 때:

1️⃣ stack = [0, 1, 2, 3, 4]

stack.top = 4

① 은 1, ②는 2 이므로

.result = [-1, -1, -1, -1, 2, -1, -1]가 되고

stack.pop() 된다.

 

stack.top = 3

① 은 1, ②는 2 이므로

.result = [-1, -1, -1, 2, 2, -1, -1]가 되고

stack.pop() 된다.

 

stack.top = 2

① 은 3, ②는 3 이므로 넘어간다.

2️⃣

stack = [0, 1, 2] 된다.

 

i = 6 일 때:

1️⃣stack = [0 ,1, 2, 5]

stack.top = 5

① 은 2, ②는 3 이므로

.result = [-1, -1, -1, 2, 2, 1, -1]가 되고

stack.pop() 된다.

 

stack.top = 2

① 은 2, ②는 3 이므로

.result = [-1, -1, 1, 2, 2, 1, -1]가 되고

stack.pop() 된다.

 

stack.top = 1

① 은 2, ②는 2 이므로 넘어간다.

2️⃣

stack = [0, 1] 된다.

 

i = 7 일 때:

넘어간다.

stack = [0, 1, 7] 이 된다.

 

전체 코드

시도

1️⃣F배열 만들어서 돌리기 -> 시간 초과

// match용 str
const strInput = input.join("");

// F[] = F(Ai) = Ai의 중복개수,
// index = i,
// input[i] = A
let F = [];
for (let x of input) {
  let re = ;
  const reg = new RegExp(re, "g");
  F.push(strInput.match(reg).length);
}

let stack = [];
for (let i = 0; i < F.length; i++) {
  // F[stack.top()]보다 큰 F[i]를 찾아
  // result[i]에 input[i] 넣기
  while (stack.length && F[stack[stack.length - 1]] < F[i]) {
    result[stack.pop()] = input[i];
  }
  stack.push(i);
}

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