[LeetCode] - 2264. Largest 3 Same Digit Number in String

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

--> https://leetcode.com/problems/largest-3-same-digit-number-in-string/description/

 

문제 : 

You are given a string num representing a large integer. An integer is good if it meets the following conditions :

It is a substring of num with length 3.

It consists of only one unique digit.

 

Return the maximum good integer as a string or an empty string "" if no such integer exists.

Note:

A substring is a contiguous sequence of characters within a string.

There may be leading zeroes in num or a good integer.

---

Example 1 :

Input : num = "6777133339"

Output : "777"

Explanation : There are two distinct good integers: "777" and "333". "777" is the largest, so we return "777".

 

Example 2 :

Input : num = "2300019"

Output : "000"

Explanation : "000" is the only good integer.

 

Example 3 :

Input : num = "42352338"

Output : ""

Explanation : No substring of length 3 consists of only one unique digit.

Therefore, there are no good integers.

 

Constraints :

• 3 <= num.length <= 1000
• num only consists of digits.

---

이 문제는 주어진 문자열 num에서 길이가 3인 부분 문자열 중, 하나의 유일한 숫자로만 구성된 가장 큰 값을 찾는 문제입니다. 해당 조건을 만족하는 문자열이 없으면 빈 문자열을 반환합니다.

 

class Solution {
    public String largestGoodInteger(String num) {
        String largest = "";

        for (int i = 0; i <= num.length() - 3; i++) {
            char currChar = num.charAt(i);
            if (num.charAt(i+1) == currChar && num.charAt(i+2) == currChar) {
                String goodInteger = "" + currChar + currChar + currChar;

                if (goodInteger.compareTo(largest) > 0) {
                    largest = goodInteger;
                }
            }
        }

        return largest;
    }
}

 

제 첫 코드는 이랬습니다 : 

1. 변수 초기화 :
   • String largest = ""; 문장을 사용하여 조건을 만족하는 가장 큰 부분 문자열을 저장할 변수를 초기화합니다.
2. 부분 문자열 확인 :
   • for (int i = 0; i <= num.length() - 3; i++) { ... } 문장을 사용하여 문자열 num의 모든 길이 3인 부분 문자열을 확인합니다.
   • char currChar = num.charAt(i); 문장을 사용하여 현재 인덱스의 문자를 저장합니다.
   • if (num.charAt(i+1) == currChar && num.charAt(i+2) == currChar) { ... } 문장을 사용하여 현재 인덱스에서 시작하는 길이 3인 부분 문자열이 동일한 문자로 구성되어 있는지 확인합니다.
3. 조건 확인 및 업데이트 :
   • String goodInteger = "" + currChar + currChar + currChar; 문장을 사용하여 조건을 만족하는 부분 문자열을 생성합니다.
   • if (goodInteger.compareTo(largest) > 0) { ... } 문장을 사용하여 현재 부분 문자열이 largest보다 큰지 비교합니다.
   • 큰 경우 largest = goodInteger; 문장을 사용하여 largest를 업데이트합니다.
4. 결과 반환 :
   • 최종적으로 largest 값을 반환합니다.

• 시간 복잡도 : O(n)
  • 문자열 num의 길이를 n이라고 할 때, 문자열을 한 번 순회하면서 각 길이 3인 부분 문자열을 확인하므로 시간 복잡도는 O(n)입니다.
• 공간 복잡도 : O(1)
  • 추가적인 배열이나 리스트를 사용하지 않고, 상수 공간만 사용하므로 공간 복잡도는 O(1)입니다. 여기서 사용되는 변수들은 largest, currChar, goodInteger로, 모두 상수 공간을 차지합니다.

하지만 제 코드는 완전 비효율적인 결과를 줬습니다 시간, 공간 복잡도면에서도 좋은 것 같았지만 말이죠.

---

그래서 개선 시킨 코드가 이겁니다 : 

class Solution {
    public String largestGoodInteger(String num) {
        int i = 9;
        while(i >= 1){
            String search = String.valueOf(111*i);
            if(num.contains(search)){
                return search;
            }
            i--;
        }
        if(num.contains("000")){
             return "000";
        }


        return "";
    }
}

 

이 코드는 주어진 문자열 num에서 길이가 3인 부분 문자열 중, 하나의 유일한 숫자로만 구성된 가장 큰 값을 찾는 문제를 해결합니다. 해당 조건을 만족하는 문자열이 없으면 빈 문자열을 반환합니다. 이 접근 방식은 문자열 내에서 '000'부터 '999'까지의 숫자를 검색하는 방식입니다.

1. 숫자 검색 :
   • int i = 9; 문장을 사용하여 숫자를 9부터 시작합니다.
   • while(i >= 1) { ... } 문장을 사용하여 숫자를 1까지 감소시키면서 반복합니다.
   • String search = String.valueOf(111 * i); 문장을 사용하여 '111', '222', ..., '999' 형태의 문자열을 생성합니다.
   • if(num.contains(search)) { return search; } 문장을 사용하여 num 문자열 내에 해당 숫자가 포함되어 있는지 확인합니다. 포함되어 있다면 해당 문자열을 반환합니다.
2. '000' 확인 :
   • if(num.contains("000")) { return "000"; } 문장을 사용하여 '000'이 포함되어 있는지 확인합니다. 포함되어 있다면 '000'을 반환합니다.
3. 결과 반환 :
   • 모든 조건을 만족하지 않으면 빈 문자열을 반환합니다.

• 시간 복잡도 : O(n)
  • while 루프는 최대 9번 실행되며, 각 반복에서 num.contains(search) 호출이 이루어집니다. contains 메서드는 num 문자열의 길이를 n이라고 할 때 O(n) 시간 복잡도를 가집니다. 따라서 전체 시간 복잡도는 O(9 * n) = O(n)입니다.
  • '000'을 확인하는 조건도 O(n) 시간 복잡도를 가집니다.
• 공간 복잡도 : O(1)
  • 추가적인 배열이나 리스트를 사용하지 않고, 상수 공간만 사용하므로 공간 복잡도는 O(1)입니다. 여기서 사용되는 변수들은 i, search로, 모두 상수 공간을 차지합니다.

시간 공간 복잡도는 그대로입니다만, 아무래도 조건문 부분이 덜 무겁고, 오히려 접근방식이 더 심플해져서 그 작은 차이가 결과에 큰 영향을 준 것 같습니다. while 문이 또 이런 케이스에서도 유용합니다.

---

개선 시키기 전 후 Runtime 결과