[C++ 백준 풀이] 15829번 : Hashing / 11866번 : 요세푸스 문제 0 / 1676번 : 팩토리얼 0의 개수

이 포스트는 프로그래밍 문제 풀이 사이트 백준 Online Judge의 Solved.ac 기준 Silver 정도의 난이도를 가지고 있는 문제들인 15829번 : Hashing, 11866번 : 요세푸스 문제 0, 1676번 : 팩토리얼 0의 개수의 풀이 코드와 해설을 다루고 있습니다.

 

이번 포스트는 적절하게 실버 난이도의 문제들 중에서 어렵지 않은 것들로 풀어보도록 하겠습니다.

다만 풀어볼 의미가 없는 것이 아닌, Solved.ac의 Class에 수록되어 있는 에센셜 문제들 중에서 골랐습니다.

큐를 사용하면 배울 점이 많은 문제가 있어 C++로 풀이하였습니다.

 

 

15829번 : Hashing

 

Hash 함수에 대해 설명하고 있는 문제이며 그렇기 때문에 문제가 길지만, 간단히 필요한 부분만 편집한 것이 위의 이미지입니다.

Hash 함수를 위와 같이 정의할 때, 입력되는 문자열을 적절히 바꾸어 계산한 값을 출력하는 문제입니다.

위에서 r의 값은 31, M의 값은 1234567891이라고 정해주었으므로 거기에 대입만 해서 계산해주면 됩니다.

유의할 부분은 오직 int 범위를 넘어서는 시그마의 값입니다.

 

 

↓ 복사가 가능한 풀이 코드는 아래 접은 글에 포함되어 있습니다.

#include <iostream>
#include <string>
using namespace std;

int main() {
    int n;
    long long int temp, sum = 0;
    char c;
    cin >> n;
    for(int i=0; i<n; i++) {
        cin >> c;
        temp = c - 'a' + 1;
        for(int j=0; j<i; j++) temp = (temp*31)%1234567891;
        sum += temp;
    }
    cout << sum%1234567891;
}

 

풀이는 위와 같고, 우선 각 c를 하나씩 입력받는 방법을 선택하였습니다.

c를 입력받고 이를 a=1, b=2, ...와 같이 매칭되도록 'a'를 빼고 1을 더해주었으며, 계산을 수행할 때 수가 너무 커지지 않도록 계속해서 M에 대한 나머지로 값을 유지시켰습니다.

최종 계산 값에 대한 M의 나머지는 어차피 식 어디서 나머지를 계속 취하든 같으므로, 반복문으로 곱을 해줄 때마다 나머지를 구해줘도 됩니다.

계산 이후에는 sum에 temp 값을 더해주어서 최종적으로 올바른 값이 나올 수 있도록 합니다.

sum으로 더하는 과정에서도 M을 넘어가는 수가 발생할 수 있으므로, 마지막 출력해주는 부분에서도 나머지 처리를 해주어야 합니다.

 

 

위 코드로 풀이를 제출해보면 모든 서브테스크에 대해 통과가 된 것을 확인할 수 있습니다.

풀이 시간은 0ms에 수렴하여 시간 초과는 전혀 걱정할 필요가 없는 문제였습니다.

 

 

11866번 : 요세푸스 문제 0

 

요세푸스 문제는 사실 이미 이전에도 풀이한 적이 있습니다.

↓ 해당 풀이는 아래 링크를 남겨두겠습니다.

[C언어 백준 풀이][Silver V] 1158번 : 요세푸스 문제 / 1181번 : 단어 정렬 / 1183번 : 약속

 

위 포스트에서 이미 풀이를 한 적이 있기 때문에, 여기서는 C로 풀지 않고 C++의 queue 라이브러리를 이용하여 풀이하도록 하겠습니다.

요세푸스 문제는 남아있는 숫자들 중에서 K개를 건너뛰면서 수를 제거해나가는 방식대로 수를 제거할 때 마지막에 남는 수를 고르는 문제인데, 수를 고르는 과정을 큐를 넘기며 뒤로 보내는 것으로 생각하면 (쉽게 생각하면 카드 덱을 뒤로 넘기면서 제거해나가는 과정으로 생각하면) 쉽게 해결이 가능합니다.

 

 

↓ 복사가 가능한 풀이 텍스트 코드는 아래 접은 글에 정리되어 있습니다.

#include <iostream>
#include <queue>
using namespace std;

int main() {
    int N, K, temp, cnt = 1, pop_count = 1, arr[1005];
    queue<int> group;
    cin >> N >> K;
    for(int i=1; i<=N; i++) group.push(i);
    while(!group.empty()) {
        temp = group.front();
        if(cnt%K == 0) {
            arr[pop_count++] = temp;
            group.pop();
        }
        else {
            group.pop();
            group.push(temp);
        }
        cnt++;
    }
    cout << "<" << arr[1];
    for(int i=2; i<pop_count; i++) cout << ", " << arr[i];
    cout << ">";
}

 

풀이를 보면 위와 같고, queue를 선언하여 group에 번호를 저장합니다.

번호를 저장한 이후에는 큐가 빌 때까지 계속해서 번호를 확인해 나가는데, 만약 K로 나눈 나머지가 0인, 즉 매 K번째 번호는 pop만 해서 제거해주도록 합니다.

이 때 저는 제거된 수들을 배열 arr에 저장해 두었다가 마지막에 모두 출력하는 방식을 선택했기 때문에, 출력을 하지 않고 배열에 저장했습니다.

K번째 숫자가 아니라면 pop을 하기 전에 temp에 저장하고, 이 temp를 pop 한 뒤 다시 뒤에 push 해주는 방식을 선택했습니다.

그러면 이 숫자는 맨 뒤로 돌아가서 다시 다음 루프 때 나올 수 있게 됩니다.

 

 

위 코드를 제출해보면 0ms에 수렴하는 소요 시간이 나오므로, 시간이 거의 걸리지 않고 문제가 해결되었음을 알 수 있습니다.

 

 

1676번 : 팩토리얼 0의 개수

 

이 문제는 N 팩토리얼을 계산했을 때 10의 몇 거듭제곱이 들어가는지를 구하는 문제입니다.

소인수분해를 할 줄 안다면, 10은 2와 5의 곱이므로 2와 5의 곱이 총 몇 번 포함되었는지를 카운트해보면 된다는 사실을 쉽게 알 수 있습니다.

다만 2와 5의 곱해진 수가 다르다면, 더 작은 것이 10의 거듭제곱의 횟수가 될 것입니다.

 

 

↓ 역시 풀이 코드는 아래 접은 글에 정리되어 있습니다.

#include <iostream>
using namespace std;

int main() {
    int N, two = 0, five = 0, temp;
    cin >> N;
    for(int i=1; i<=N; i++) {
        temp = i;
        while(temp%2 == 0 || temp%5 == 0) {
            if(temp%2 == 0) temp/=2, two++;
            if(temp%5 == 0) temp/=5, five++;
        }
    }
    cout << (two<five?two:five);
}

 

풀이를 보면 어렵지 않은데, 우선 two는 2의 거듭제곱 횟수를 의미하고 five는 5의 거듭제곱 횟수를 의미하는 변수입니다.

N을 입력받고 i=1부터 시작해서 모든 i에 대해 2와 5가 나누어떨어질 수 있을 때까지 계속해서 나누어주면서, two와 fiv를 count 해주었습니다.

N까지 검사가 끝난 이후에는 two와 five 중에서 더 작은 것이 10의 거듭제곱 수가 되므로 더 작은 수를 출력해주도록 함으로써 코드를 작성하였습니다.

 

 

코드를 제출해보면 정답임을 알 수 있고, 역시 소요 시간이 0ms에 수렴하여 오래 걸리지 않는 프로그램임을 알 수 있습니다.