[LeetCode] 2053. Kth Distinct String in an Array

https://leetcode.com/problems/kth-distinct-string-in-an-array/description/?envType=daily-question&envId=2024-08-05

leetcode - Kth Distinct String in an Array

문제 유형 : 해시, 문자열처리

문제 난이도 : Easy

 

문제

A distinct string is a string that is present only once in an array.

Given an array of strings arr, and an integer k, return the kth distinct string present in arr. If there are fewer than k distinct strings, return an empty string "".

Note that the strings are considered in the order in which they appear in the array.

 

뚜렷한 문자열은 배열에 단 한 번만 등장하는 문자열을 말합니다.

 

문자열 배열 arr, 정수 k가 주어지는데, k번째 뚜렷한 문자열을 반환하시오.

k개보다 적다면, 빈 문자열을 반환하시오.

 

배열의 순서대로 문자열의 순서를 고려하면 됩니다.

 

풀이

해시맵에 string - int형태로 문자열에 대한 빈도를 저장하고,

arr을 한 번 순회하면서 개수를 누적한다.

다시 arr을 순회하면서 k번째로 빈도가 1인 문자열을 반환한다.

배열 순회가 끝나고도 없다면, 빈 문자열 ""을 반환한다.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    string kthDistinct(vector<string>& arr, int k) {
        unordered_map<string, int> mp;

        for(const auto &str : arr) {
            mp[str]++;
        }

        for(const auto &str : arr) {
            if(mp[str] == 1) {
                if(--k == 0) return str;
            }
        }

        return "";
    }
};