99클럽 코테 스터디 29일차 TIL - 문자열 (LeetCode 556번)

항해99 코테 스터디 29일차 문제인 리트코드 556번은 주어진 양의 정수의 숫자들 위치를 바꾸어, 기존 정수보다 큰 정수 중 가장 작은 값을 구하는 문제다. 난이도는 Medium이며 완전탐색 또는 Greedy를 통해 해결할 수 있다.

 

오늘의 문제 - XXX 문제 정보

문제 키워드

- 문자열

난이도

- Medium

 

문제 요약

• 양의 정수 n이 주어진다. n에 존재하는 숫자들을 사용해서 n보다 큰 정수 중 가장 작은 값을 구하여라.
  • 그러한 양의 정수가 없으면 -1을 반환한다.
  • 정답은 32bit 정수여야 하므로, 32bit를 벗어날 경우에도 -1을 반환한다.

 

문제 풀이 과정  

• 풀이 1 (비효율적)
  • 숫자는 어차피 int 범위 안이라서 자리수가 최대 10자리이기 때문에 DFS를 통해 모든 가능한 숫자를 구하고, 그 중 기존 값보다 크면서 가장 작은 값을 구하는 풀이로 풀었다.
  • 그치만 생각보다 오래 걸려서 시간초과가 떴고, 어떻게 잘 해서 시간 내에 통과는 했으나 문제에서 의도하는 바가 아니었다.
• 풀이 2 (효율적)
  • 현재 숫자보다 큰, 바로 다음 숫자만 구하면 되기 때문에 기존 숫자에서 숫자를 바꿔가면서 조건에 맞는 수를 구하는 방식을 구상하였다.
  • 기존 숫자에서 두개를 swap하여 숫자가 커지는 경우 중, 바꾼 뒤의 숫자가 가장 작은 경우를 구하였다.
    • 그러기 위해서는 바뀌어지는 숫자가 가장 오른쪽(작은 자리)에 있는 경우를 찾으면 된다.
  • 위 과정을 통해 일단 숫자를 기존보다 크게 만들었다면, 숫자가 바뀐 구간을 가장 작게 만들어야 한다.
    • 위 과정과 비슷하게, 두개를 swap하여 숫자가 작아지는 경우 중 바뀌어지는 숫자가 가장 왼쪽(큰 자리)에 있는 경우를 찾았다.
    • 이 과정을 반복하여 가장 작은 수를 만들었다.

코드 (풀이2)

class Solution {
    public int nextGreaterElement(int n) {
        StringBuilder sb = new StringBuilder(String.valueOf(n));
        int l = 0, r = sb.length(); // 문자열 비교 범위

        while(l < r) {
            // 맨 처음에만 더 커지기 위한 조건, 그 이후로는 더 작아지기 위한 조건
            // 더 커지거나 작아지기 위해 바꿔야 하는 숫자의 인덱스를 구함
            int[] change = (l == 0) ? findChangeToGreater(sb.substring(l, r))
                : findChangeToSmaller(sb.substring(l, r));

            // 더 커지거나 작아질 수 없으면 종료
            if (change[0] == -1 || change[1] == -1) break;
            
            // 위에서 구한 결과에 맞춰 숫자를 바꾸기
            changeChar(sb, l+change[0], l+change[1]);

            // 바뀐 부분만 다시 검사하도록 범위 조정
            l += (change[0] + 1);
        }

        // 최종적으로 구한 결과가 정상적인 범위 안이면 답으로 반환, 아니면 -1 반환
        long nextNumber = Long.parseLong(sb.toString());
        return nextNumber <= Integer.MAX_VALUE && nextNumber > n ? (int) nextNumber : -1;
    }

    // 숫자로 구성된 문자열에서, 두 숫자를 바꿀 경우 전체 숫자가 커지는 부분을 구함
    private int[] findChangeToGreater(String str) {
        int len = str.length();
        char[] charArr = str.toCharArray();
        int l = -1, r = -1;

        for(int s=1; s<len; s++) {
            for(int d=0; d<s; d++) {
                if (charArr[d] < charArr[s] && l <= d) {
                    l = d; r = s;
                }
            }
        }

        return new int[]{l, r};
    }

    // 숫자로 구성된 문자열에서, 두 숫자를 바꿀 경우 전체 숫자가 작아지는 부분을 구함
    private int[] findChangeToSmaller(String str) {
        int len = str.length();
        char[] charArr = str.toCharArray();
        int l = -1, r = -1;

        for(int s=1; s<len; s++) {
            for(int d=s-1; d>=0; d--) {
                if (charArr[d] > charArr[s]) {
                    l = d; r = s;
                }
            }
        }

        return new int[]{l, r};
    }

    // 문자열에서 b위치의 문자를 a위치로 이동
    private String changeChar(StringBuilder sb, int a, int b) {
        return sb.insert(a, sb.charAt(b))
            .deleteCharAt(b+1)
            .toString();
    }
}

• 시간복잡도: O(L^3) → L: 숫자의 자리수 (최대 10)
• 공간복잡도: O(L)