[LeetCode] - 3120. Count the Number of Special Characters

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Count the Number of Special Characters" 문제입니다.

-->  https://leetcode.com/problems/count-the-number-of-special-characters-i/description/

 

문제 : 

You are given a string word. A letter is called special if it appears both in lowercase and uppercase in word. Return the number of special letters in word.

---

Example 1:

Input: word = "aaAbcBC"

Output: 3

Explanation: The special characters in word are 'a', 'b', and 'c'.

 

Example 2:

Input: word = "abc"

Output: 0

Explanation: No character in word appears in uppercase.

 

Example 3:

Input: word = "abBCab"

Output: 1

Explanation: The only special character in word is 'b'.

 

Constraints:

• 1 <= word.length <= 50
• word consists of only lowercase and uppercase English letters. 

---

이 문제는 주어진 문자열에서 대문자와 소문자 모두로 등장하는 문자를 '특수 문자'라고 합니다. 주어진 문자열에서 특수 문자의 개수를 반환하는 문제입니다. 예를 들어, "aaAbcBC" 문자열에서 특수 문자는 'a', 'b', 'c'이며, 총 3개입니다.

제 코드를 보시겠습니다 : 

class Solution {
    public int numberOfSpecialChars(String word) {
        Set<Character> speChSet = new HashSet<>();
        for (int i = 0; i < word.length(); i++) {
            speChSet.add(word.charAt(i));
        }
        List<Character> speChList = new ArrayList<>(speChSet);
        
        // Tri de la liste
       

        int speCount = 0;

        for (int j = 0; j < speChList.size(); j++) {
            char lowerCaseChar = Character.toLowerCase(speChList.get(j));
            if (Character.isUpperCase(speChList.get(j))) {
                if (speChList.contains(lowerCaseChar)) {
                speCount++;   
                }
            }
                

        }

        return speCount;
    }
}

/* 
2 Ways to solve this (my opinion)

1. Once we put all the characters in a Set-ed List, we transform all Character into LowerCase then check if there's duplicates character
==> ex) if speChList = {'A', 'a'} then we gon do toLowerCase() ==> it will give {'a', 'a'} which means 'a' is a special character

2. We do a double if : if speCh has uppercase, then we check (second if : ) that  it contains its lowercase  

*/

 

위 코드를 상세하게 설명드리자면 : 

1. 문자 집합 생성:
   • 주어진 문자열 word의 각 문자를 HashSet에 추가하여 중복을 제거합니다.
2. 리스트 변환:
   • 집합을 리스트로 변환하여 각 문자를 순회할 수 있게 합니다.
3. 특수 문자 개수 계산:
   • 리스트의 각 문자를 순회하면서, 대문자인 경우 해당 소문자가 리스트에 있는지 확인합니다.
   • 해당 조건을 만족하면 speCount를 증가시킵니다.
4. 끝

시간 및 공간 복잡도 분석:

1. 시간 복잡도:
   • 문자열의 각 문자를 집합에 추가하는 데 O(n) 시간이 소요됩니다.
   • 집합을 리스트로 변환하는 데 O(n) 시간이 소요됩니다.
   • 리스트의 각 문자를 순회하고 대문자인지 확인하고 소문자를 찾는 데 O(n^2) 시간이 소요됩니다.
   • 따라서 전체 시간 복잡도는 O(n^2)입니다. 흠... 만족스럽진 않은 결과입니다. 하지만 이것은 그저 초기 코드라는 것 알아두십시오. 코드는 개선하면 되는 거니까요.
2. 공간 복잡도:
   • 집합과 리스트를 사용하는 데 O(n) 공간이 필요합니다.

---

개선된 코드 : 

class Solution {
    public int numberOfSpecialChars(final String word) {
        final boolean[] chars = new boolean[26 * 2]; // 소문자 및 대문자를 추적하는 배열
        final boolean[] seen = new boolean[26]; // 이미 확인된 특수 문자를 추적하는 배열
        int count = 0;

        for (int i = 0; i < word.length(); ++i) {
            final int idx = word.charAt(i) - (word.charAt(i) < 'a' ? 'A' : 'a'); // 현재 문자의 인덱스 계산

            chars[idx + (word.charAt(i) < 'a' ? 26 : 0)] = true; // 소문자 또는 대문자 여부에 따라 배열에 표시

            if (!seen[idx] && chars[idx] && chars[idx + 26]) { // 이미 확인되지 않았고, 대문자와 소문자가 모두 존재하면
                seen[idx] = true; // 특수 문자로 표시
                count++; // 특수 문자 개수 증가
            }
        }

        return count; // 특수 문자의 개수 반환
    }
}

 

1. 배열 초기화:
   • chars 배열은 대문자와 소문자의 존재 여부를 추적합니다.
   • seen 배열은 이미 확인된 특수 문자를 추적합니다.
   • count는 특수 문자의 개수를 저장합니다.
2.  
3. 문자열 순회:
   • 문자열의 각 문자를 순회합니다.
   • 현재 문자의 인덱스를 계산합니다.
   • 소문자 또는 대문자 여부에 따라 chars 배열에 해당 문자의 존재 여부를 표시합니다.
   • 특수 문자 조건(대문자와 소문자가 모두 존재)을 만족하면 seen 배열에 표시하고 count를 증가시킵니다.
4. 결과 반환:
   • 특수 문자의 개수를 반환합니다.

시간 및 공간 복잡도:

1. 시간 복잡도:
   • 문자열의 각 문자를 한 번씩 순회하고, 각 연산이 상수 시간에 수행되므로 시간 복잡도는 O(n)입니다. 여기서 n은 문자열의 길이입니다.
2. 공간 복잡도:
   • 두 개의 boolean 배열(chars와 seen)을 사용하여 문자의 존재 여부를 추적하므로, 공간 복잡도는 O(1)입니다. 배열의 크기는 문자열의 길이에 비례하지 않고 고정 크기(52)입니다.

이제야 볼만한 코드가 되었습니다.

---

코드 개선되기 전 후의 Runtime 결과