[LeetCode] 31번 문제를 풀어보았다. (ft. java)

2022년 04월 03일 일요일 - 오늘을 데이뚜

오늘 올려볼 문제는 31번 Next Permutation 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.

거의 다 풀고 틀려서 힌트 봤지만 올릴거임!

입력

사진에서도 볼 수 있듯이 int 배열 1개가 입력으로 들어온다.

---

풀이 및 코드

해당 배열로 만들 수 있는 조합들중 다음 조합에 해당하는 배열을 만드는 문제이다.

이 때 입력으로 들어온 배열을 수정하는 방식으로 구현해야한다.

오늘은 틀렸지만 방향성은 맞았다.

일단 앞의 숫자가 뒤에 나오는 숫자보다 작을 때를 찾는다.

이 숫자 뒤에 나오는 숫자중 가장 작은 수랑 위치를 바꾸고 이 숫자 뒤로 정렬을 하는 식으로 구현했다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public void nextPermutation(int[] nums) {
        int lastIndex = -1;
        for(int i = 0; i < nums.length - 1; i++)
        {
            if(nums[i] < nums[i + 1]) lastIndex = i;
        }

        if(lastIndex == -1)
        {
            Arrays.sort(nums);
        }
        else
        {
            int minIndex = lastIndex + 1;
            for(int i = lastIndex + 1; i < nums.length; i++)
            {
                if(nums[lastIndex] < nums[i] && nums[i] < nums[minIndex]) minIndex = i;
            }

            int temp = nums[minIndex];
            nums[minIndex] = nums[lastIndex];
            nums[lastIndex] = temp;

            Arrays.sort(nums, lastIndex + 1, nums.length);
        }
    }
}

---

제출 화면

오늘은 마음이 급해서 힌트를 빨리봤는데 아마 고민을 좀만 더 했으면 힌트 없이 문제를 풀었을 것이다.

내일은 성인군자와 같은 마음으로 문제를 풀어야겠다.

내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.