[LeetCode] - 2351. First Letter to Appear Twice

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

--> https://leetcode.com/problems/first-letter-to-appear-twice/description/

 

문제 : 

Given a string s consisting of lowercase English letters, return the first letter to appear twice.

Note :

• A letter a appears twice before another letter b if the second occurrence of a is before the second occurrence of b.
• s will contain at least one letter that appears twice.

---

Example 1 :

Input : s = "abccbaacz"

Output : "c"

Explanation : The letter 'a' appears on the indexes 0, 5 and 6. The letter 'b' appears on the indexes 1 and 4.

The letter 'c' appears on the indexes 2, 3 and 7.

The letter 'z' appears on the index 8.

The letter 'c' is the first letter to appear twice, because out of all the letters the index of its second occurrence is the smallest.

 

Example 2 :

Input : s = "abcdd"

Output : "d"

Explanation : The only letter that appears twice is 'd' so we return 'd'.

 

Constraints :

• 2 <= s.length <= 100
• s consists of lowercase English letters.
• s has at least one repeated letter.

---

이 문제는 주어진 문자열 s에서 두 번 나타나는 첫 번째 문자를 반환하는 문제입니다. 문자열은 최소한 하나의 문자가 두 번 이상 나타납니다.

 

class Solution {
    public char repeatedCharacter(String s) {
        Set<Character> letterSet = new HashSet<>();
        char ans = ' ';
        for (int i = 0; i < s.length(); i++) {
            if (!letterSet.contains(s.charAt(i))) {
                letterSet.add(s.charAt(i));
            } else {
                ans = s.charAt(i);
                break;
            }
        }
        return ans;
    }
}

 

저는 이번 문제에서 Set의 성질을 이용해서 풀었습니다. 코드 조건문에 break; 가 있어서 저희 교수님께서 이걸 보시면 눈살을 찌푸리실 수도 있지만, 한국말 못 하시니까 이 블로그를 볼 일이 없기 때문에 세이프입니다.

 

이 코드는 주어진 문자열 s에서 첫 번째로 두 번 나타나는 문자를 반환하는 문제를 해결합니다. 이를 위해 집합을 사용하여 문자의 등장 여부를 추적하고, 첫 번째로 두 번 나타나는 문자를 발견하면 반환합니다.

1. 집합 초기화 :
   • Set<Character> letterSet = new HashSet<>(); 문장을 사용하여 문자 등장 여부를 추적할 집합을 초기화합니다.
2. 변수 초기화 :
   • char ans = ' '; 문장을 사용하여 결과를 저장할 변수를 초기화합니다. 이 변수는 두 번 나타나는 첫 번째 문자를 저장합니다.
3. 문자열 순회 :
   • for (int i = 0; i < s.length(); i++) { ... } 문장을 사용하여 문자열 s의 각 문자를 순회합니다.
   • 현재 문자가 집합에 있는지 확인합니다.
     • 집합에 없으면, 현재 문자를 집합에 추가합니다.
     • 집합에 있으면, 현재 문자가 두 번 나타난 것이므로 ans에 현재 문자를 저장하고 반복을 종료합니다.
4. 결과 반환 :
   • 첫 번째로 두 번 나타나는 문자를 반환합니다.

• 시간 복잡도 : O(n)
  • 문자열 s의 길이를 n이라고 할 때, 문자열의 각 문자를 한 번씩만 순회하므로 시간 복잡도는 O(n)입니다.
• 공간 복잡도 : O(1)
  • 집합 letterSet에 최대 26개의 문자가 저장될 수 있으므로, 공간 복잡도는 상수 시간으로 O(1)입니다. 이는 영어 소문자의 수가 26개로 제한되어 있기 때문입니다.

---

코드 Runtime 결과