[Baekjoon] 17299 오등큰수(파이썬/자바스크립트/NodeJS)

이번 문제는 아래 링크에서 풀어볼 수 있습니다.

17298번: 오큰수

---

문제

크기가 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

---

정답 코드

나의 코드
파이썬 Ver.

import sys


n = int(sys.stdin.readline().rstrip())
nums = list(map(int, input().split()))


def mySolution(n, nums):
    ngf = [-1] * n
    stack = []
    appear = dict()

    for num in nums:
        try:
            appear[num] += 1
        except:
            appear[num] = 1

    for i in range(n):
        while stack and appear[nums[stack[-1]]] < appear[nums[i]]:
            ngf[stack.pop()] = nums[i]
        stack.append(i)

    print("mySolution", *ngf)


mySolution(n, nums)

자바스크립트/NodeJS Ver.

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let [n, ...input] = fs.readFileSync(filePath).toString().trim().split('\n');

n = parseInt(n);
const data = input[0].split(' ').map((val) => parseInt(val));

const solution1 = (data) => {
    let ngf = Array(n).fill(-1);
    const stack = [];
    const appear = {};

    for (let num of data) {
        if (!appear[num]) appear[num] = 1;
        else appear[num]++;
    }

    for (let i in data) {
        while (
            stack.length &&
            appear[data[stack[stack.length - 1]]] < appear[data[i]]
        )
            ngf[stack.pop()] = data[i];
        stack.push(i);
    }

    return ngf.map((val) => String(val)).join(' ');
};

console.log('solution1');
console.log(solution1(data));

 

Counter 모듈 활용

from collections import Counter
import sys


n = int(sys.stdin.readline().rstrip())
nums = list(map(int, input().split()))


def answer1(n, nums):
    cnt = Counter(nums)
    ngf = [-1] * n
    stack = []

    for i in range(n):
        while stack and cnt[nums[stack[-1]]] < cnt[nums[i]]:
            ngf[stack.pop()] = nums[i]
        stack.append(i)

    print("answer1", *ngf)


answer1(n, nums)

---

문제 풀이

 앞선 오큰수 문제와 거의 유사하다. 차이점이라면 수열 내의 특정 숫자가 등장한 횟수를 리스트로 만들어 해당 리스트를 활용해서 문제를 풀어야 한다는 점이다.

 나는 수열 내 특정 숫자가 등장한 횟수를 구하기 위해 try except문과 dict을 활용했다. 수열을 for 반복문으로 돌면서 탐색하는 숫자에 해당하는 key 값이 없다면 해당 숫자를 key로 설정하고 등장횟수인 value를 1로 한다. 이미 key로 존재한다면 중복 등장이므로 value를 1 증가시킨다. 이후 풀이는 오큰수를 풀 때와 같다. 차이점이라면 등장횟수가 담긴 딕셔너리의 값을 비교해서 등장횟수가 많은 쪽의 값을 nums에서 추출하여 ngf 리스트에 저장한다는 점이다.

 Counter를 활용한 풀이는 파이썬의 내장 모듈인 Counter를 활용한 풀이다. Counter의 매개변수로 리스트를 삽입하면 리스트의 각 요소를 key, 요소별 등장 횟수를 value로 하는 딕셔너리가 생성된다. 이로써 리스트의 요소가 몇 번 등장했는지 간편하게 알 수 있다.

---

함께 보기

https://honggom.tistory.com/68

[백준] 17299번 문제 (오등큰수) 파이썬(Python) 풀이

https://www.daleseo.com/python-collections-counter/

파이썬 collections 모듈의 Counter 사용법