[투 포인터] Day 2. Two Pointers

Day 2는 투 포인터 입니다.

이거 사실 매일 해야되는건데;; 그냥 내킬때 하렵니다.

 

투 포인터가 무엇이냐.. 말 그대로 두 개의 포인터를 갖고 문제를 해결하는 알고리즘입니다.

사실 제가 이때까지 접했던 투 포인터 문제들은 누가 봐도 투 포인터를 사용해서 푸는 문제들이었습니다.

근데 요기 문제는;; 감이 안와서 그냥 검색해서 보고 풀었습니다 ^^~

 

문제 바로가기

Squares of a Sorted Array - LeetCode

 

사실 첫 문제는 투 포인터를 안써도 됩니다;; 투 포인터로 어떻게 푸는지도 잘 모르겠네여.

 

class Solution {
    public int[] sortedSquares(int[] nums) {
        return Arrays.stream(nums)
                .map(num -> num * num)
                .sorted()
                .toArray();
    }
}

 

자바 인 액션으로 람다랑 스트림 공부좀 해야겠습니다..

 

그럼 두 번째 문제..

 

문제 바로가기

Rotate Array - LeetCode

요 문제가 진국입니다. k만큼 배열을 돌리랍니다. 아주 쉬워 보이죠잉. 하라는 대로 하면 될겁니다 아마. 근데 얘는 꼭 투 포인터로 풀어봅시다.

 

사실 얘도 딱 봤을 때 투 포인터로 어떻게 푸나 감도 안왔습니다.

요렇게 보시죠.

 

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]

[1,2,3,4,5,6,7], 3

=> 다 뒤집어

[7,6,5,4,3,2,1]

=> 0~2 얘들 뒤집어

[[5,6,7],[4,3,2,1]]

=> 3~6 얘들 뒤집어

[[5,6,7],[1,2,3,4]]

완성!!

 

이 아름다운 풀이가 보이심니까..

 

풀이 영상

 

캬 이 아저씨 기가 맥히게 설명해줍니다..

 

암튼 저렇게 아주 쉽게 배열을 돌릴 수 있는데요.

뒤집을 때! 투 포인터 개념이 사용됩니다. 사실 이 때까진 투 포인터 문제라고 하면 범위를 갖고 노는 문제만 투 포인터라고 생각했는데.. 아니더군여.

 

left, right 두 포인터를 갖고 양 끝을 잡고 서로 바꿔주면 배열이 뒤집어 지는 것이죵. 크.. 기가 맥힙니다 증말.

 

class Solution {
    public void rotate(int[] nums, int k) {
        k = k % nums.length;        
        // 전체 뒤집기
        reverse(nums, 0, nums.length - 1);
        // 왼쪽 뒤집기
        reverse(nums, 0, k - 1);
        // 오른쪽 뒤집기
        reverse(nums, k, nums.length - 1);
    }

    private void reverse(int[] nums, int left, int right) {
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }

    private void swap(int[] nums, int a, int b) {
        int t = nums[a];
        nums[a] = nums[b];
        nums[b] = t;
    }
}

 

코드 뿌리고.. 이만 총총...