백준 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(" "));