[LeetCode] - 1903. Largest Odd Number in String

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

--> https://leetcode.com/problems/largest-odd-number-in-string/description/

 

문제 : 

You are given a string num, representing a large integer.

Return the largest-valued odd integer (as a string) that is a non-empty substring of num,

or an empty string "" if no odd integer exists.

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

---

Example 1 :

Input : num = "52"

Output : "5"

Explanation : The only non-empty substrings are "5", "2", and "52". "5" is the only odd number.

 

Example 2 :

Input : num = "4206"

Output : ""

Explanation : There are no odd numbers in "4206".

 

Example 3 :

Input : num = "35427"

Output : "35427"

Explanation : "35427" is already an odd number.

 

Constraints :

• 1 <= num.length <= 10^5
• num only consists of digits and does not contain any leading zeros.

---

이 문제는 주어진 문자열 num에서 가장 큰 값의 홀수를 찾는 문제입니다. 이 문제를 해결하기 위해 문자열을 뒤에서부터 순회하면서 홀수를 찾으면 그 위치까지의 모든 문자를 포함하는 서브스트링을 반환하면 됩니다. 이렇게 하면 가장 큰 값의 홀수를 찾을 수 있습니다.

class Solution {
    public String largestOddNumber(String num) {
        List<Integer> oddIndices = new ArrayList<>();
        
        for (int i = 0; i < num.length(); i++) {
            if ((num.charAt(i) - '0') % 2 != 0) {
                oddIndices.add(i);
            }
        }

        if (oddIndices.isEmpty()) return "";

        Collections.sort(oddIndices);
        int lastIndex = oddIndices.get(oddIndices.size() - 1);

        return num.substring(0, lastIndex + 1);
        
    }
}

 

제 첫 코드는 이거였습니다. 

주어진 문자열 num에서 가장 큰 값의 홀수를 찾는 문제를 해결합니다. 주어진 접근 방법은 먼저 문자열에서 모든 홀수 인덱스를 찾아 리스트에 저장하고, 가장 큰 인덱스를 사용하여 결과를 반환합니다.

1. 홀수 인덱스 저장 :
   • List<Integer> oddIndices = new ArrayList<>(); 문장을 사용하여 홀수 인덱스를 저장할 리스트를 초기화합니다.
   • for (int i = 0; i < num.length(); i++) { ... } 문장을 사용하여 문자열 num을 순회하면서 각 문자가 홀수인지 확인합니다.
   • 홀수인 경우, oddIndices.add(i); 문장을 사용하여 해당 인덱스를 리스트에 추가합니다.
2. 홀수 인덱스 확인 :
   • if (oddIndices.isEmpty()) return ""; 문장을 사용하여 리스트가 비어있는지 확인합니다. 비어 있으면 문자열에 홀수가 없다는 의미이므로 빈 문자열을 반환합니다.
3. 가장 큰 인덱스 사용 :
   • Collections.sort(oddIndices); 문장을 사용하여 홀수 인덱스 리스트를 정렬합니다.
   • int lastIndex = oddIndices.get(oddIndices.size() - 1); 문장을 사용하여 가장 큰 인덱스를 가져옵니다.
4. 결과 반환 :
   • return num.substring(0, lastIndex + 1); 문장을 사용하여 가장 큰 홀수 인덱스까지의 서브스트링을 반환합니다.

• 시간 복잡도 : O(n log n)
  • 문자열의 길이를 n이라고 할 때, 문자열을 한 번 순회하면서 홀수 인덱스를 찾으므로 O(n) 시간이 소요됩니다.
  • 홀수 인덱스 리스트를 정렬하는 데 O(n log n) 시간이 추가로 소요됩니다.
  • 따라서 전체 시간 복잡도는 O(n log n)입니다.
• 공간 복잡도 : O(n)
  • 모든 홀수 인덱스를 저장하기 위해 리스트 oddIndices를 사용하므로 공간 복잡도는 O(n)입니다.

보시다시피 시간 복잡도 면에서 굉장히 비효율적입니다. 개선해야 할 점이 많습니다.

---

class Solution {
    public String largestOddNumber(String num) {
        // Iterate through the string from the end
        for (int i = num.length() - 1; i >= 0; i--) {
            // Check if the current character is an odd digit
            if ((num.charAt(i) - '0') % 2 != 0) {
                // Return the substring from the start to the current index (inclusive)
                return num.substring(0, i + 1);
            }
        }
        // If no odd digit is found, return an empty string
        return "";
    }
}

 

처음 코드에서는 불필요한 Collections.sort() 를 해버렸습니다.

 

이 코드는 주어진 문자열 num에서 가장 큰 값의 홀수를 찾기 위해 문자열을 끝에서부터 순회하며 첫 번째 홀수를 찾으면 해당 위치까지의 서브스트링을 반환합니다. 이렇게 하면 가장 큰 값의 홀수를 효율적으로 찾을 수 있습니다.

1. 문자열을 끝에서부터 순회 :
   • for (int i = num.length() - 1; i >= 0; i--) 문장을 사용하여 문자열 num을 끝에서부터 순회합니다.
2. 홀수 확인 :
   • if ((num.charAt(i) - '0') % 2 != 0) 문장을 사용하여 현재 문자가 홀수인지 확인합니다.
   • 문자를 정수로 변환하여 2로 나눈 나머지가 1이면 홀수입니다.
3. 결과 반환 :
   • 홀수를 찾으면 return num.substring(0, i + 1); 문장을 사용하여 해당 위치까지의 서브스트링을 반환합니다.
   • 문자열을 끝까지 순회한 후에도 홀수를 찾지 못하면 return ""; 문장을 사용하여 빈 문자열을 반환합니다.

• 시간 복잡도 : O(n)
  • 문자열의 길이를 n이라고 할 때, 문자열을 한 번 순회하므로 시간 복잡도는 O(n)입니다.
  • 문자열의 끝에서부터 순회하기 때문에 최대 n번의 비교 연산이 필요합니다.
• 공간 복잡도 : O(1)
  • 추가적인 배열이나 리스트를 사용하지 않고, 상수 공간만 사용하므로 공간 복잡도는 O(1)입니다.
  • 필요한 공간은 단지 몇 개의 변수(i)를 저장하는 데 사용됩니다.

결론적으로 개선된 코드는 기존 코드에 비해 효율성이 높습니다. 불필요한 리스트와 정렬을 제거함으로써 시간 복잡도는 O(n)으로 줄었고, 공간 복잡도는 O(1)로 최적화되었습니다. 이는 특히 문자열의 길이가 길어질수록 성능 향상에 큰 도움이 됩니다.

•  

 

---

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