[투 포인터] Day 2. Two Pointers

[투 포인터] Day 2. Two Pointers

Day 2는 투 포인터 입니다.

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

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

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

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

문제 바로가기

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

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

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

그럼 두 번째 문제..

문제 바로가기

요 문제가 진국입니다. 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; } }

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

from http://yoon1fe.tistory.com/249 by ccl(A) rewrite - 2021-11-26 05:28:21