[99클럽 코테 스터디 21일차 TIL] 문자열

qk·2024년 6월 18일
0

회고

목록 보기
21/33
post-thumbnail

📖 오늘의 학습 키워드
문자열

오늘의 회고

문제

[Next Greater Element III]
https://leetcode.com/problems/next-greater-element-iii/description/

나의 해결

class Solution {
    public int nextGreaterElement(int n) {
        char[] digits = String.valueOf(n).toCharArray();
        int len = digits.length;
        int left = len - 2;
        while (left >= 0 && digits[left] >= digits[left + 1]) {
            left--;
        }
        if (left < 0) {
            return -1;
        }
        int right = len - 1;
        while (digits[left] >= digits[right]) {
            right--;
        }
        swap(digits, left, right);
        reverse(digits, left + 1, len - 1);
        long result = Long.parseLong(new String(digits));
        return result > Integer.MAX_VALUE ? -1 : (int) result;
    }
    public void swap(char[] arr, int i, int j) {
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
     public void reverse(char[] array, int start, int end) {
        while (start < end) {
            swap(array, start, end);
            start++;
            end--;
        }
    }
}
  1. 정수 n의 모든 자릿수로 이루어진 char 배열 digits를 생성한다.
  2. left를 digits 배열의 길이에서 2를 뺀 수로 초기화한다.
    • 정수 n의 뒤에서 두 번째 자릿수
  3. left가 0보다 크고 digits[left]가 digits[left + 1]보다 크거나 같을 때까지 left의 값을 하나씩 줄여나간다.
  4. 위 과정을 통해 left 값이 -1이 되면 digits가 내림차순으로 정렬되어 있다는 의미이다.
    • 정수 n의 자릿수들을 조합해서 만들 수 있는 숫자 중 최댓값이라는 뜻이므로 n보다 더 큰 값을 만들 수 없어 -1을 반환한다.
      예) 54321
  5. right를 digits 배열의 길이에서 1을 뺀 수로 초기화한다.
    • 정수 n의 마지막 자릿수
  6. digits[left]가 digits[right]보다 크거나 같을 때까지 right의 값을 하나씩 줄여나간다.
  7. swap 함수를 이용해 left와 right에 위치한 두 숫자를 각각 서로의 위치로 옮긴다.
  8. reverse 함수를 이용해 left 이후부터 digits 배열의 마지막까지 배열의 순서를 반전시킨다.
  9. digits 배열을 다시 합쳐 이를 long 형태로 변환한다.
    • 합친 결과가 정수 최댓값보다 클 수 있기 때문이다.
  10. 9의 결과 정수 최댓값보다 크다면 -1을 반환한다. 그렇지 않으면 이를 다시 정수형으로 변환하여 반환한다.

0개의 댓글