삽질 오래 했던 문제

문제 설명

소수의 개수 k, 찾아야 하는 소수가 몇 번째인지를 나타내는 n이 주어지고 그 다음줄에 소수들이 주어진다.

풀이방식을 30분~1시간정도 고민하다 답을 얻지 못하고 설명을 들었다. 아이디어를 떠올리기 힘들지만 풀이는 간단한 문제였다.

1. pq에 소수를 집어넣는다.
2. top을 pop함과 동시에 top과 소수를 곱한 수를 pq에 추가한다.

그러나 이 과정에서 pq의 수가 중복이 되는 경우가 발생한다.

4 19
2 3 5 7의 경우

2 3 5 7
(2 pop) 3 4 5 6 7 10 14
(3 pop) 4 5 6 6 7 9 10 14 15 21

6이 pq에 두 번 등장하는 걸 볼 수 있다.

하지만 pq는 순서대로 정렬되어있고, pq 안의 수는 pop된 수보다 무조건 같거나 크므로 중복체크는 아주 쉽게 할 수 있다.
이전 top과 현재 top이 같다면, 중복이라는 뜻이므로 cnt를 증가시키지 않고 pop만 해주면 된다.

#include <iostream>
#include <vector>
#include <functional>
#include <queue>

#define INT_MAX 2147483647

using namespace std;

vector<int> sosu;
priority_queue<int, vector<int>, greater<int> > pq;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int k, n;
    cin >> k >> n;
    for(int i = 0; i < k; i++) {
        int s;
        cin >> s;
        sosu.push_back(s);
        pq.push(s);
    }

	int top;
	int cnt = 0;
    int prev_top = 0;
    while(cnt < n) {
        top = pq.top();
        pq.pop();
        if (top == prev_top)
            continue;
        for(int i = 0; i < sosu.size(); i++) {
            long long s = (long long)sosu[i] * top;
            if (s <= INT_MAX)
                pq.push(s);
        }
		cnt++;
        prev_top = top;
    }
	cout << top;
}

삽질

cnt가 n-1 될 때까지만 pop시키고 답은 pq.top()으로 직접 출력해주었더니 "틀렸습니다"가 떴다.

cnt가 n-2일 때 top이 중복된 수가 아닌 경우 새로운 수를 추가해주는 과정에서 중복된 수가 유입될 수 있다. 이후 pq.top()을 출력하면 중복된 수가 그대로 출력돼버리는 거다.

교훈은.. for문 이후 마지막 인덱스까지도 조건이 만족되는지 확인할 것,
어정쩡하게 n-1까지 pop하고 top 출력하기보단 그냥 아싸리 pop해버리고 마지막으로 기억한 top을 출력하는 게 낫다는 것 정도가 될 것 같다.

#include <iostream>
#include <vector>
#include <functional>
#include <queue>

#define INT_MAX 2147483647

using namespace std;

vector<int> sosu;
priority_queue<int, vector<int>, greater<int> > pq;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int k, n;
    cin >> k >> n;
    for(int i = 0; i < k; i++) {
        int s;
        cin >> s;
        sosu.push_back(s);
        pq.push(s);
    }

	int top;
	int cnt = 0;
    int prev_top = 0;
    while(cnt < n - 1) {
        top = pq.top();
        pq.pop();
        if (top == prev_top)
            continue;
        for(int i = 0; i < sosu.size(); i++) {
            long long s = (long long)sosu[i] * top;
            if (s <= INT_MAX)
                pq.push(s);
        }
		cnt++;
        prev_top = top;
    }
    cout << pq.top();
}