ksh021144

ksh021144

Learn more, Do more.

Gemstones

2 분 소요

HackerRank 알고리즘 문제 풀이

분류

Practice > Algorithms > Strings

문제 링크 : https://www.hackerrank.com/challenges/gem-stones/problem

풀이

길이 n인 string벡터가 주어질 때, 전체 n개의 문자열에 공통적으로 포함된 최소 알파벳 개수를 찾는 문제이다.

다음과 같은 예시가 있을 때, 3개의 문자열에서 공통적으로 나타나는 부분이 이므로, 답은 2이다.

문제 조건에 의해 , 문자열 길이도 이고, 출제자의 의도는 아닌 것 같지만 비트 마스킹을 활용해서도 으로 해결할 수 있다.

우선 알파벳 개수를 카운팅하기 위해 int cnt[100][26] = 0을 정의하고 첫 번째 문자열부터 n번째 문자열까지 순회하면서 i번째 문자열에 각각의 알파벳이 몇 개씩 나타내는지 카운팅한다.

그리고 하나의 문자열에서 나타나는 알파벳을 비트의 집합으로 표현하여 AND(&)연산을 하면 공통적으로 나타나는 알파벳 위치를 찾을 수 있고, 이를 코드로 나타내면 다음과 같다.

int duplicateBit = ~(1 << 31); // int의 최댓값을 표현하는 방법 중 하나다.
for (int i = 0; i < N; ++i) {
    int alpBit = 0;
    for (char c : arr[i]) {
        alpBit |= (1 << (c - 'a'));
        ++cnt[i][c - 'a'];
    }
    // AND연산을 하면 각 문자열에서 공통적으로 출현된 알파벳 위치만 남게 된다.
    duplicateBit &= alpBit;
}

만약 ‘abc’, ab’라는 문자열이 있다면 duplicateBit가 정수형이므로 3값을 갖고 있을 것이고 이진법으로 표현하면 ‘0011’인데, 아래의 표를 보면 사용하고 있는 알파벳 위치를 나타내는 방식이 이해가 될 것이다.

d c b a
0 0 1 1

이 과정이 끝나면 duplicateBit는 전체 n개의 문자열에서 공통적으로 나타나는 알파벳의 위치를 갖고 있게 된다.

알파벳이 26개이므로 [0, 26)까지 반복하고 알파벳 a가 사용되는지, b가 사용되는지, …, z가 사용되는지 확인한다.

j번째 문자열 중에서 i번째 알파벳이 몇 개 사용되는지 확인하면 되는데, (이때 0번째 알파벳은 a이다.) 공통적으로 나타나는 알파벳 개수를 찾는다는 의미는 공통적으로 나타나는 알파벳의 최솟값을 찾는다는 의미이므로 이다.

최종적으로 temp를 구해서 ans에 누적하면 답을 구할 수 있다.

int ans = 0;
for (int i = 0; i < 26; ++i) {
    if ((duplicateBit & (1 << i)) != 0) {
        int temp = 100;
        for (int j = 0; j < N; ++j) {
            if (temp > cnt[j][i]) {
                temp = cnt[j][i];
            }
        }
        ans += temp;
    }
}

소스 코드

#include <bits/stdc++.h>

using namespace std;

// Complete the gemstones function below.
int gemstones(vector<string> arr) {
    int cnt[100][26] = { 0 };
    const int N = (int)arr.size();
    int duplicateBit = ~(1 << 31);
    for (int i = 0; i < N; ++i) {
        int alpBit = 0;
        for (char c : arr[i]) {
            alpBit |= (1 << (c - 'a'));
            ++cnt[i][c - 'a'];
        }
        duplicateBit &= alpBit;
    }

    int ans = 0;
    for (int i = 0; i < 26; ++i) {
        if ((duplicateBit & (1 << i)) != 0) {
            int temp = 100;
            for (int j = 0; j < N; ++j) {
                if (temp > cnt[j][i]) {
                    temp = cnt[j][i];
                }
            }
            ans += temp;
        }
    }
    return ans;
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    int n;
    cin >> n;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');

    vector<string> arr(n);

    for (int i = 0; i < n; i++) {
        string arr_item;
        getline(cin, arr_item);

        arr[i] = arr_item;
    }

    int result = gemstones(arr);

    fout << result << "\n";

    fout.close();

    return 0;
}

참고