[Leetcode]2161. Partition Array According to Given Pivot

문제 요약

• 알고리즘 분류:  배열, 구현
• 난이도: Medium
• 문제내용:
  • pivot 기준으로 pivot보다 작으면 원쪽으로 들어온 값 순서대로 정렬하고 pivot보다 크면 오르쪽으로 들어온 값 순서대로 정렬하세요.
• 사이트 주소: https://leetcode.com/problems/partition-array-according-to-given-pivot/description/

문제풀이

이번 문제는 단순한 구현 문제인 일반 적인 정렬 문제는 아니다. 만약 아래와 같이 단순 정렬 하면 오답처리가 될 것이다.

그래서 아래와 같이 들어온값 순서 대로 정렬 해야 정답 처리가 될것이다.

그래서 아래와 같이 pivot 기준으로 3가지로 구분한 다음 합치기만 하면 구현적인 부분은 끝이다.

• 왼쪽: pivot보다 작을 때
• 중간: pivot이랑 같을 때
• 오른쪽: pivot보다 클 때

위 와 같이 구현하면 시간 복잡도는 O(N)만큼 나올 것이다.

 

Code

Python

class Solution:
    def pivotArray(self, nums: List[int], pivot: int) -> List[int]:
        before = []  # pivot 이전 담을 리스트
        middle = []  # pivot 값 담을 리스트
        after = []  # pivot 이후 담을 리스트

        # pivot 기준으로 분기 처리
        for num in nums:
            # pivot 값 보다 클때
            if (num > pivot):
                after.append(num)
            # pivot 값 같을때
            elif (num == pivot):
                middle.append(num)
            # pivot 값 보다 작을때
            else:
                before.append(num)

        '''
        값 추가한 순서
        pivot 이전값 → pivot 값 → pivot 값 이후 순서 대로 저장
        '''
        return before + middle + after

Java

class Solution {
     public int[] pivotArray(int[] nums, int pivot) {

        int size = nums.length;

        List<Integer> before = new ArrayList<>(); // pivot 이전 담을 리스트
        List<Integer> middle = new ArrayList<>(); // pivot 값 담을 리스트
        List<Integer> after = new ArrayList<>();  // pivot 이후 담을 리스트

        // pivot 기준으로 분기 처리
        for(int num : nums){
            // pivot 값 보다 클때
            if(num > pivot){
                after.add(num);
            }
            // pivot 값 같을때
            else if (num == pivot) {
                middle.add(num);
            }
            // pivot 값 보다 작을때
            else{
                before.add(num);
            }
        }

        int[] result = new int[size]; // 결과값
        int beforeSize = before.size(); // 이전 값 크기
        int middleSize = middle.size(); // pivot 값 크기
        int afterSize = after.size(); // 이후 값 크기


        /*
         * 값 추가한 순서
         * pivot 이전값 → pivot 값 → pivot 값 이후 순서 대로 저장
         */
        for (int i = 0; i <beforeSize; i++) {
            result[i] = before.get(i);
        }

        for (int i = beforeSize; i <  beforeSize + middleSize; i++) {
            result[i] = middle.get(i - beforeSize);
        }

        for (int i = beforeSize + middleSize; i < beforeSize + middleSize + afterSize; i++) {
            result[i] = after.get(i - beforeSize - middleSize);
        }

        return result;
    }
}