[c++] 2309. Greatest English Letter in Upper and Lower Case

Given a string of English letters s, return the greatest English letter which occurs as both a lowercase and uppercase letter in s. The returned letter should be in uppercase. If no such letter exists, return an empty string.

An English letter b is greater than another letter a if b appears after a in the English alphabet.

 

Example 1:

Input: s = "lEeTcOdE"
Output: "E"
Explanation:
The letter 'E' is the only letter to appear in both lower and upper case.

Example 2:

Input: s = "arRAzFif"
Output: "R"
Explanation:
The letter 'R' is the greatest letter to appear in both lower and upper case.
Note that 'A' and 'F' also appear in both lower and upper case, but 'R' is greater than 'F' or 'A'.

 

  한줄해석 

소문자랑 대문자가 같이 있는 문자중 가장 큰값을 반환해라. 

 

  풀이 포인트 

1. char 에서 대소문자 비교를 할 수 있는가. 

2. map을 활용하여 저장된 값을 비교 할 수 있는가. 

 

  추가상식 

map자료형을 사용 할 경우,  아래와 같이 3가지 경우를 활용 할 수 있다. 

1) unordered_map , 

2) map 

3) unordered_set

 

unordered_map 과 map 은  성능차이가 좀 있다.  기억이 안나면 아래 접은 글을 확인하고...

결론만 쓰자면... 

1) 속도 map -- O(logN)   /     unordered_map O(1) 

2) 숫자형 키 사용시 데이터 양이 많아질수록 unordered_map 이 map보다 월등한 성능을 보인다. 

3) map은 문자열 비교시, 앞에서 한글자씩 차례대로 비교하므로 문자열 길이가 길어지더라도 민감하게 반응하지 않으며,
    따라서 문자열 전체를 hashing하는 것(=unordered_map) 보다 우수할 수 있다.

   ( 해석1. 문자열을 키로 사용하는 경우 문자열이 길어질수록 unordered_map이 map에 비해 성능이 떨어질 수있다.) 
   ( 해석2. 하지만, 유사도가 높은 문자열 집합을 키로 사용할경우 map의 성능이 떨어질수있다) 

 

4) key 를 이용하여 정렬이 필요하다면  map을 써라, 대량의 데이터 사용할때는 unordered_map이 더 좋을 수도.. (?)

 

자세한 비교 분석

https://gracefulprograming.tistory.com/3

 

    코드     

 

class Solution {
public:
    string greatestLetter(string s) {
  
        unordered_set<char> small;
        unordered_set<char> upper;
        
        
        for(int i=0; i<s.size();i++){
            if(s[i]-'Z'> 0 ) { // ASCII코드상 A~Z(65~ 90) / a~z (97~122)
                small.insert(s[i]);
            }else{
                upper.insert(s[i]);
            }           
        }
        
        string s1; int a=0;
        for (auto key : upper) {
            if(small.find(key+32) != small.end()){ // 'A'-'a' =32 
                if(key > a){                       // 이전꺼보다 크면 업데이트 
                    s1 = key;
                    a=key;
                }
            }            
        }    
    
        return s1;
        
    }
};