[LeetCode] - 2710. Remove Trailing Zeros From a String

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

--> https://leetcode.com/problems/remove-trailing-zeros-from-a-string/description/

 

문제 : 

Given a positive integer num represented as a string, return the integer num without trailing zeros as a string.

---

Example 1:

Input: num = "51230100"

Output: "512301"

Explanation: Integer "51230100" has 2 trailing zeros, we remove them and return integer "512301".

 

Example 2:

Input: num = "123"

Output: "123"

Explanation: Integer "123" has no trailing zeros, we return integer "123".

 

Constraints:

• 1 <= num.length <= 1000
• num consists of only digits.
• num doesn't have any leading zeros.

---

이 문제는 정말 한 줄로 요약이 됩니다 : 양의 정수 num이 문자열로 주어집니다. 이 문자열에서 후행하는 모든 0을 제거하고, 결과를 문자열로 반환합니다. 끝

class Solution {
    public String removeTrailingZeros(String num) {
        StringBuilder sb = new StringBuilder(num);
        
        // 뒤에서 시작
        int i = sb.length() - 1;
        while (i >= 0 && sb.charAt(i) == '0') {
            i--;
        }
        
        // If i < the length - 1 ==>  means we have 0s at the end
        if (i < sb.length() - 1) {
            sb.delete(i + 1, sb.length());
        }
        
        return sb.toString();
    }
}

 

이 코드에서는 StringBuilder를 써봤는데, 예상보다 퍼포먼스가 좋지 않았습니다. 그래서 나중에 가서는 Substring 메소드를 썼는데 더 효율적이었습니다. 이 코드부터 설명드리고 바로 보여드리겠습니다.

1. StringBuilder 초기화 :
   • 주어진 문자열 num을 StringBuilder 객체로 변환하여 수정 가능하게 합니다.
2. 후행 0 탐색 :
   • 문자열의 끝에서부터 첫 번째 0이 아닌 문자를 찾을 때까지 인덱스 i를 감소시킵니다. i는 첫 번째 0이 아닌 문자의 인덱스가 됩니다.
3. 후행 0 제거 :
   • 만약 i가 문자열의 끝보다 작다면, 즉 후행 0이 있다면, i 이후의 모든 문자를 제거합니다.
4. 결과 반환 :
   • 수정된 문자열을 반환합니다.

시간 및 공간 복잡도 :

1. 시간 복잡도 :
   • O(n) : 문자열의 길이를 n이라 할 때, 문자열의 끝에서부터 탐색하므로 최악의 경우 모든 문자를 한 번씩 검사합니다. 문자열 삭제 연산은 O(n)입니다. 따라서 전체 시간 복잡도는 O(n)입니다.
2. 공간 복잡도 :
   • O(n) : StringBuilder 객체를 생성하므로 입력 문자열의 길이 n에 비례하는 공간을 사용합니다.

---

 

class Solution {
    public String removeTrailingZeros(String num) {
        int count = 0;
        int n = num.length();
        for(int i = n-1;i>=0;i--){
            char c = num.charAt(i);
            if(c=='0'){
                count++;
            }
            else{
                break;
            }
        }
        return num.substring(0,n-count);
    }
}

 

더 효과적입니다.

---

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