C++ / 프로그래머스 / 억억단을 외우자

문제

https://school.programmers.co.kr/learn/courses/30/lessons/138475

프로그래머스

문제풀이

1. 사진을 절반으로 y와 x가 같은 부분을 기준으로 접으면 똑같이 일치한다.

따라서 절반의 부분만 이중 반복문을 통해 구할 것이다.

2. 그다음은 우선순위 큐를 이용해 top부분이 횟수가 가장 큰 수로 정렬한다.

3. 정렬된 우선순위 큐를 통해 starts의 원소들과 비교하고 answer에 값을 저장한다.

 

주의할 점으로는 우선순위 큐를 이용하기 때문에 starts벡터가 오름차순으로 정렬되어있어야 한다.

따라서 starts를 정렬하기 전에 숫자와 숫자의 위치를 저장하는 order벡터를 만들었다.

 

    for (idx = 1; idx * idx <= e; ++idx) {
        num[idx * idx] = 1;
        for (idx2 = idx + 1; idx * idx2 <= e; ++idx2) {
            num[idx * idx2] += 2;
        }
    }

idx * idx 부분은 겹쳐서 한 숫자만 나오는 곳, idx * idx2는 접었을 때 같은 수가 두 개 있으므로 2개씩 저장한다.

idx * idx = 1*1 (1개)

idx * idx2 = 1*2, 2*1 (2개)

 

 

struct cmp {
    bool operator()(pair<int, int>a, pair<int, int>b) {
        if (a.first == b.first)
            return a.second > b.second;
        else
            return a.first < b.first;
    }
};    
    
    for (idx = 1; idx <= e; ++idx) {
        pq.push({ num[idx],idx });
    }

우선순위 큐를 정렬하기 위해 임의의 조건을 만들었다.

first부분은 횟수, second부분은 숫자로 정의했다.

횟수가 같으면 숫자가 작은 거 먼저, 그 외는 횟수가 많은 것이 먼저 오도록 한다.

 

    for (idx = 0; idx < starts.size(); ++idx) {
        while (1) {
            if (starts[idx] <= pq.top().second) {
                answer[order[starts[idx]]] = pq.top().second;
                break;
            }
            else {
                pq.pop();
            }
        }
    }

정렬된 starts를 탐색하면서 pq의 top부분보다 작으면 order벡터를 통해 원래 위치를 찾고 answer[위치]에 해당 값을 저장한다.

top부분보다 크면 답이 될 수 없으므로 pop을 하여 다음 원소로 넘어간다.

문제의 입출력 예에 나와있는 1~8을 보면 4번 등장하는 6, 8이 있다.

작은 수부터 큰 수로 해야 우선순위큐를 이용할 수 있으므로 초반에 정렬을 했다.

 

코드

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;


struct cmp {
    bool operator()(pair<int, int>a, pair<int, int>b) {
        if (a.first == b.first)
            return a.second > b.second;
        else
            return a.first < b.first;
    }
};

vector<int> solution(int e, vector<int> starts) {
    int start(0), idx(0), idx2(0);
    vector<int>order(e + 1, 0);
    vector<int>num(e + 1, 0);
    vector<int> answer(starts.size(), 0);        
    priority_queue<pair<int, int>, vector<pair<int, int>>, cmp>pq;

    for (idx = 0; idx < starts.size(); ++idx) {
        order[starts[idx]] = idx;
    }

    sort(starts.begin(), starts.end());

    for (idx = 1; idx * idx <= e; ++idx) {
        num[idx * idx] = 1;
        for (idx2 = idx + 1; idx * idx2 <= e; ++idx2) {
            num[idx * idx2] += 2;
        }
    }
    
    for (idx = 1; idx <= e; ++idx) {
        pq.push({ num[idx],idx });
    }

    for (idx = 0; idx < starts.size(); ++idx) {
        while (1) {
            if (starts[idx] <= pq.top().second) {
                answer[order[starts[idx]]] = pq.top().second;
                break;
            }
            else {
                pq.pop();
            }
        }
    }
    return answer;
}