[LeetCode] - 1796. Second Largest Digit in a String
LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Remove Trailing Zeros From a String " 문제입니다.
--> https://leetcode.com/problems/second-largest-digit-in-a-string/description/
문제 :
Given an alphanumeric string s, return the second largest numerical digit that appears in s, or -1 if it does not exist.
An alphanumeric string is a string consisting of lowercase English letters and digits.
Example 1 :
Input : s = "dfa12321afd"
Output : 2
Explanation : The digits that appear in s are [1, 2, 3].
The second largest digit is 2.
Example 2 :
Input : s = "abc1111"
Output : -1
Explanation : The digits that appear in s are [1].
There is no second largest digit.
Constraints :
1 <= s.length <= 500
s consists of only lowercase English letters and/or digits.
이 문제는 주어진 문자열 s에서 두 번째로 큰 숫자 문자를 찾아 반환하는 문제입니다. 문자열 s는 소문자 영어 문자와 숫자로 구성된 문자열입니다. 두 번째로 큰 숫자가 존재하지 않으면 -1을 반환해야 합니다.
class Solution {
public int secondHighest(String s) {
char[] c=s.toCharArray();
TreeSet<Integer> set=new TreeSet<>();
for(int i=0;i<c.length;i++) {
if(c[i]>='0' && c[i]<='9') {
set.add(c[i]-'0');
}
}
if(set.size()==0 || set.size()==1) return -1;
set.pollLast();
return set.last();
}
}
이 코드는 주어진 문자열 s에서 두 번째로 큰 숫자 문자를 찾아 반환합니다. 문자열 s는 소문자 영어 문자와 숫자로 구성된 문자열입니다. TreeSet을 사용하여 자동으로 정렬된 고유 숫자를 저장하고, 가장 큰 숫자를 제거한 후 두 번째로 큰 숫자를 반환합니다.
- 문자 배열 생성 :
- 문자열 s를 문자 배열 c로 변환합니다.
- 숫자 집합 생성 :
- TreeSet<Integer>를 사용하여 고유 숫자를 저장합니다. TreeSet은 자동으로 요소를 정렬하며 중복을 제거합니다.
- 문자 배열 c를 순회하며, 숫자 문자를 TreeSet에 추가합니다.
- 두 번째로 큰 숫자 확인 :
- TreeSet의 크기가 0 또는 1이면, 두 번째로 큰 숫자가 존재하지 않으므로 -1을 반환합니다.
- 그렇지 않으면, TreeSet에서 가장 큰 숫자를 제거하고, 현재 가장 큰 숫자를 반환합니다.
- 시간 복잡도 : O(n log k)
- 문자열 s를 한 번 순회하면서 숫자를 TreeSet에 추가하는 작업은 O(n log k) 시간이 소요됩니다. 여기서 n은 문자열의 길이, k는 서로 다른 숫자의 개수(최대 10)입니다. 숫자를 추가하는 작업은 O(log k) 시간이 걸립니다.
- TreeSet에서 가장 큰 숫자를 제거하는 pollLast 메소드는 O(log k) 시간이 걸립니다.
- 따라서 전체 시간 복잡도는 O(n log k)입니다.
- 공간 복잡도 : O(k)
- 숫자를 저장하는 TreeSet의 공간 복잡도는 O(k)입니다. 여기서 k는 서로 다른 숫자의 개수(최대 10)입니다.
오랜만에 TreeSet 을 써볼 수 있는 기회가 생겨서 감회가 새로웠었는데, 문제는 제 코드가 그다지 효율적이지 못했다는 것입니다. 그래서 저는 다른 유저들이 어떻게 풀었나 한 번 서칭 해봤습니다. 그렇게 하여 찾은 솔루션이 이 분 코드인데, 공유해 드리겠습니다 :
class Solution {
public int secondHighest(String s) {
// Integer map for storing digits
int map = 0;
// For keeping count of digits processed
int bCount = 0;
for(char c : s.toCharArray()){
// If current character is a digit and is not stored
// in the map
if(Character.isDigit(c) && (map&(1<<(c-'0'))) == 0){
// Turn the bit on at respective digit position in map
map|=(1<<(c-'0'));
bCount++;
// Since we need second largest, after 2 unique digits
// we need to discard smallest digit in the map
if(bCount > 2) map&=(map-1);
}
}
if(bCount < 2) return -1;
for(int i = 0; i < 32; i++,map>>=1) if((map&1) == 1) return i;
return -1;
}
}
// sanchayharjai37 유저의 코드
이분의 코드는 비트 마스크를 사용하여 숫자를 추적하고 처리합니다. 이 접근 방식은 효율적이고 공간을 절약하는 방법입니다. 저로서는 상상도 못한 접근 방식이어서 더더욱 제 주목을 받았고, 제가 더 공부하게 된 기분이 들게 해 줘서 정말 고마운 코드입니다. 위 코드를 연구하자면 :
- 비트 마스크 초기화 :
- map 변수는 정수형으로, 각 비트는 특정 숫자가 문자열에 있는지 추적합니다.
- bCount 변수는 서로 다른 숫자의 개수를 추적합니다.
- 문자열 순회 :
- 문자열 s를 순회하면서 각 문자가 숫자인지 확인합니다.
- 숫자인 경우, 해당 숫자가 map에 이미 저장되어 있는지 확인합니다.
- 숫자가 map에 없으면 map에 해당 숫자를 추가하고, bCount를 증가시킵니다.
- 두 번째로 큰 숫자 확인 :
- bCount가 2보다 크면 가장 작은 숫자를 map에서 제거합니다.
- 이는 map & (map - 1) 연산을 통해 이루어집니다. 이 연산은 map의 가장 오른쪽 비트를 끕니다.
- 결과 반환 :
- bCount가 2보다 작으면 두 번째로 큰 숫자가 없으므로 -1을 반환합니다.
- 그렇지 않으면, map을 순회하여 두 번째로 큰 숫자를 찾습니다.
- 비트가 1인 위치를 찾아 반환합니다.
- 시간 복잡도 : O(n)
- 문자열 s를 한 번 순회하면서 숫자를 처리하는 작업은 O(n) 시간이 소요됩니다. 여기서 n은 문자열의 길이입니다.
확실히 시간 복잡도 면에서 제 코드와 확연히 다르고 더 효율적인게 보입니다.
- 공간 복잡도 : O(1)
- 숫자를 저장하는 데 사용되는 map 변수는 정수형이므로 고정된 크기의 공간을 사용합니다.
- 추가적인 변수 bCount와 루프 변수를 제외하면 상수 공간만 사용됩니다.
