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.
Example 1:
Input: arr = ["d","b","c","b","c","a"], k = 2
Output: "a"
Explanation:
The only distinct strings in arr are "d" and "a".
"d" appears 1st, so it is the 1st distinct string.
"a" appears 2nd, so it is the 2nd distinct string.
Since k == 2, "a" is returned.
Example 2:
Input: arr = ["aaa","aa","a"], k = 1
Output: "aaa"
Explanation:
All strings in arr are distinct, so the 1st string "aaa" is returned.
Example 3:
Input: arr = ["a","b","a"], k = 3
Output: ""
Explanation:
The only distinct string is "b". Since there are fewer than 3 distinct strings, we return an empty string "".
Constraints:
- 1 <= k <= arr.length <= 1000
- 1 <= arr[i].length <= 5
- arr[i] consists of lowercase English letters.
1. Python
일단 내 힘으로 풀어봤는데, 좀 조잡하다
처음으로 list의 enumerate까지 적용시켜보았다.
class Solution:
def kthDistinct(self, arr: List[str], k: int) -> str:
dic = {}
for i,x in enumerate(arr):
if x not in dic :
dic[x] = [i,1]
else:
dic[x][1]+=1
lst = []
for x,y in dic.items():
if y[1] == 1:
lst.append([y[0],x])
lst.sort()
if len(lst) < k : return ""
else :
return lst[k-1][1]내 힘으로 함 풀어보았으니 답지를 봐보자
class Solution:
def kthDistinct(self, arr: List[str], k: int) -> str:
d={}
for i in arr:
if i in d:
d[i]+=1
else:
d[i]=1
c=""
n=0
for i,j in d.items():
if j==1:
c=i
n+=1
if n==k:
return i
return ""보아 하니 dic에는 저장 순서대로 element가 저장되나 보다..
2. C
GPT답안을 그냥 복붙해왔다.
좀 심각한데 이건;;
C로는 간단한 array문제도 이렇게 어렵게 풀어야 한다.
굉장히 비효율적인데 왜 배우는 지 모르겠다. C++이 마지노선일
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STRINGS 1000
char* kthDistinct(char** arr, int arrSize, int k) {
char* uniqueArr[MAX_STRINGS];
int uniqueCount[MAX_STRINGS];
int uniqueSize = 0;
// 빈도 계산
for (int i = 0; i < arrSize; i++) {
int found = 0;
for (int j = 0; j < uniqueSize; j++) {
if (strcmp(uniqueArr[j], arr[i]) == 0) {
uniqueCount[j]++;
found = 1;
break;
}
}
if (!found) {
uniqueArr[uniqueSize] = arr[i];
uniqueCount[uniqueSize] = 1;
uniqueSize++;
}
}
// 고유 문자열 찾기
int count = 0;
for (int i = 0; i < arrSize; i++) {
for (int j = 0; j < uniqueSize; j++) {
if (strcmp(uniqueArr[j], arr[i]) == 0 && uniqueCount[j] == 1) {
count++;
if (count == k) {
return arr[i];
}
}
}
}
return "";
}
두 string을 비교해서 같으면 0을 반환하는 strcmp (string.h include!) 을 사용하면 좀 더 수월하다.
char* kthDistinct(char** arr, int arrSize, int k) {
int cnt=0;
for(int i=0;i<arrSize;i++){
int j;
for(j=0;j<arrSize;j++){
if(j!=i && strcmp(arr[i],arr[j])==0){
break;
}
}
if(j==arrSize) cnt++;
if(cnt==k) return arr[i];
}
return "";
}
3. C++
class Solution {
public:
string kthDistinct(vector<string>& arr, int k) {
unordered_map<string,int> m;
for(auto x : arr){
if(m.count(x)==0){
m[x] = 1;
}else{
m[x]++;
}
}
int cnt = 0;
for(auto &x : arr){
if(m[x] == 1){
cnt++;
if(cnt==k){
return x;
}
}
}
return "";
}
};