5주차 알고리즘 복습 - 투 포인터

배열에서 두 개의 포인터를 사용하여 원하는 결과를 얻는 방법

 - 두 개의 포인터 배치 방법

   : 같은 방향에서 시작  - 첫 번 째 원소에 포인터 둘 다 배치

   : 서로 다른 방향에서 시작 - 첫 번째 원소와 마지막 원소에 배치

 

다중 for문의 복잡도를 좀 더 선형적으로 풀 수 있다. O(n^2) -> O(n)

p1, p2가 자료 n개까지 중첩이 아니라 +로 연산이 됨.

 

대표문제 : 특정한 합을 가지는 부분 연속 수열 찾기

 

<실습>

Main ) 특정한 수열이 주어졌을 때 연속된 부분 수열의 합이 target이 되는 구간의 좌표 시작, 끝 값 찾기

 

public static int[] twoPointers(int arr[], int target) {
        int result[] = {-1, -1};
        int p1 = 0;
        int p2 = 0;
        int total = 0;
        while (p2 != arr.length) {
            if (total < target) {
                total += arr[p2++];
            } else {
                total -= arr[p1++];
            }

            if (total == target) {
                result[0] = p1;
                result[1] = p2 -1 ;
                break;
            }
        }
        return result;
    }
    public static void main(String[] args) {
        int[] arr = {1, 2, 5, 3, 7, 2, 4, 3, 2};
        System.out.println(Arrays.toString(forLoop(arr, 9)));
        System.out.println(Arrays.toString(forLoop(arr, 14)));
        System.out.println();

        System.out.println(Arrays.toString(twoPointers(arr, 9)));
        System.out.println(Arrays.toString(twoPointers(arr, 14)));
    }

---

practice 1) 

// a, b, c, d 로 이루어진 알파벳 문자열에 대해서
// 다음과 같은 규칙으로 문자열을 정리한 후 남은 문자열을 반환하는 프로그램을 작성하세요.
// 양쪽의 문자를 비교한 후 같으면 삭제하는데, 연속해서 같은 문자가 등장하면 함께 삭제한다.
// 최종적으로 남은 문자열을 반환하세요.

// 입출력 예시
// 입력 s: "ab"
// 출력: "ab"

// 입력 s: "aaabbaa"
// 출력: (없음)

* 생각해야할 점 :

 1. p1은 첫 요소, p2는 끝 요소 가리키며 시작

 2. p1과 p2가 같으면

p1의 요소를 문자 변수 c에 담아놓고

while문 하나 돌면서 p1과 c가 같으면 p1++

또 while문 돌면서 p2와 c가 같으면 p2--

 3. return 할 때 p1인덱스와 p2인덱스 + 1까지 substring

import java.util.*;

public class Practice {
    public static String solution(String str) {
        int p1 = 0;
        int p2 = str.length() - 1;

        while (p1 <= p2 && str.charAt(p1) == str.charAt(p2)) {
            char c = str.charAt(p1);

            while (p1 <= p2 && c == str.charAt(p1)) {
                p1++;
            }
            while (p1 <= p2 && c == str.charAt(p2)) {
                p2--;
            }
        }
        return str.substring(p1, p2 + 1);
    }
    public static void main(String[] args) {
        // Test code
        System.out.println(solution("ab"));         // ab
        System.out.println(solution("aaabbaa"));    //
        System.out.println(solution("aabcddba"));   // cdd
    }
}

---

practice 2) 

// nums1 과 nums2 두 배열이 주어졌을 때
// 두 배열의 공통 원소를 배열로 반환하는 프로그램을 작성하세요.
// 결과 배열의 원소에는 중복 값이 없도록 하며 순서는 상관 없다.

// 입출력 예시
// nums1: 1, 2, 2, 1
// nums2: 2, 2
// 출력: 2

// nums1: 4, 9, 5
// nums2: 9, 4, 9, 8, 4
// 출력: 4, 9 (or 9, 4)

* 생각해야할 점 :

  1. 먼저 nums 배열 두 개를 sort

  2. p1은 nums1 배열의 첫 번째요소, p2는 nums2 배열의 첫 번째 원소를 가리키게 하고

    nums[p1] > nums[p2] 이면 p2++, 그 반대면 p1++

  3. p1이나 p2하나라도 각 배열의 마지막 인덱스면 while문 종료

import java.util.*;

public class Practice {
    public static int[] solution(int[] num1, int[] num2) {
        int p1 = 0; //num1 을 가리킬 포인터
        int p2 = 0; //num2를 가리킬 포인터
        Arrays.sort(num1);
        Arrays.sort(num2);
        HashSet <Integer> set = new HashSet<>();
        while (true) {
            if (num1[p1] < num2[p2]) {
                p1++;
            } else if (num1[p1] > num2[p2]) {
                p2++;
            } else {
                set.add(num1[p1]);
                p1++;
                p2++;
            }

            if (p1 == num1.length || p2 == num2.length) {
                break;
            }
        }
        return set.stream().mapToInt(x->x).toArray();
    }
    public static void main(String[] args) {
        // Test code
        int[] nums1 = {1, 2, 2, 1};
        int[] nums2 = {2, 2};
        System.out.println(Arrays.toString(solution(nums1, nums2)));

        nums1 = new int[]{4, 9, 5};
        nums2 = new int[]{9, 4, 9, 8, 4};
        System.out.println(Arrays.toString(solution(nums1, nums2)));

        nums1 = new int[]{1, 7, 4, 9};
        nums2 = new int[]{7, 9};
        System.out.println(Arrays.toString(solution(nums1, nums2)));
    }
}

 

---

practice 3) 

// 문자열 s 를 거꾸로 출력하는 프로그램을 작성하세요.
// 단, 각 단어의 알파벳 순서는 그대로 출력합니다.
// 문장에 공백이 여러개일 시, 단어와 단어 사이 하나의 공백을 제외한 나머지 공백은 제거하세요.

// 입출력 예시
// 문자열 s: "the sky is blue"
// 출력: "blue is sky the"

// 문자열 s: "      hello      java      "
// 출력: "java hello"

* 생각해야 할 점 :

 1. p1, p2 포인터를 어디로 짚을 것인가

 2. 단어 사이를 제외한 공백을 없애야함. removeSpace 메소드 -> 여기서 투포인터 알고리즘이 들어감

 3. 공백이 사라진 문자열 전체를 뒤집을 reverseString 메소드

 4. 전체 뒤집힌 문자열에서 공백 기준으로 다시 단어를 뒤집을 reverseWord 메소드 -> 투포인터 사용

 

import java.util.*;

public class Practice {
    public static String solution(String str) {
        if (str == null) {
            return null;
        }
        if (str.length() < 2) {
            return str;
        }
        String s = removeString(str);
        char []cArr = s.toCharArray();

        reverseString(cArr, 0, s.length() - 1);
        reverseWord(cArr, s.length());
        return new String(cArr);
    }
    public static String removeString(String str) {
        int p1 = 0;
        int p2 = 0;
        String result = "";

        char []cArr = str.toCharArray();
        int length = str.length();

        //p1은 공백을 없앤 문자들을 인덱스 1번부터 덮어쓰기하고 얼마나 차있나 체크하는 포인터
        //p2는 문자배열을 계속해서 나가면서 공백 기준으로 끊어주는 포인터
        while (p2 < length) {
            while (p2 < length && cArr[p2] == ' ') {
                p2++; // 한 단어의 앞 공백 없애고
            }
            while (p2 < length && cArr[p2] != ' ') {
                cArr[p1++] = cArr[p2++]; //단어들을 배열 앞에서부터 채워넣고
            }
            while (p2 < length && cArr[p2] == ' ') {
                p2++; //단어의 뒷 공백 없애고
            }
            if (p2 < length) {
                cArr[p1++] = ' ';
            }
        }
        return new String(cArr).substring(0, p1);
    }
    public static void reverseString(char cArr[], int start, int end) {
        while (start < end) {
            char tmp = cArr[start];
            cArr[start++] = cArr[end];
            cArr[end--] = tmp;
        }
    }

    public static void reverseWord(char cArr[], int length) {
        int p1 = 0;
        int p2 = 0;

        while (p1 < length) {
            while (p1 < p2 || p1 < length && cArr[p1] == ' ') {
                p1++;
            }//공백인 곳에서 멈춤

            while (p2 < p1 || p2 < length && cArr[p2] != ' ') {
                p2++;
            }
            reverseString(cArr, p1, p2 - 1);
        }
    }

    public static void main(String[] args) {
        // Test code
        System.out.println(solution("the sky is blue"));
        System.out.println(solution("  hello      java    "));

    }
}

---

practice 4) 

// 주어진 nums 배열에서 3 개의 합이 0이 되는 모든 숫자들을 출력하세요.
// 중복된 숫자 set은 제외하고 출력하세요.

// 입출력 예시
// nums: {-1, 0, 1, 2, -1, -4};
// 출력: [[-1, -1, 2], [-1, 0, 1]]

// nums: {1, -7, 6, 3, 5, 2}
// 출력: [[-7, 1, 6], [-7, 2, 5]]

* 생각해야할 것 :

 1. 일단 배열 정렬

 2. ArrayList <ArrayList<Integer>> 결과값 저장 리스트

 3.  기준값 맨 앞 값 , 기준값 다음이 p1 , 맨 마지막 요소 p2

     고정값 + p1 + p2 < 0이면 p1++

     고정값 + p1 + p2 > 0이면 p2--

 

import java.util.*;

public class Practice {
    public static ArrayList<ArrayList<Integer>> solution(int nums[]) {
        Arrays.sort(nums);
        ArrayList <ArrayList<Integer>> result = new ArrayList<>();

        for (int i = 0; i < nums.length - 2; i++) {
            if (i == 0 || i > 0 && nums[i] != nums[i - 1]) {
                int p1 = i + 1;
                int p2 = nums.length - 1;
                int sum = 0 - nums[i];

                // nums[i] + nums[p1] + nums[p2] = 0
                // nums[p1] + nums[p2] = sum
                while (p1 < p2) {
                    if (nums[p1] + nums[p2] == sum) {
                        result.add(new ArrayList(Arrays.asList(nums[i], nums[p1], nums[p2])));

                        while (p1 < p2 && nums[p1] == nums[p1 + 1]) {
                            p1++;
                        }
                        while (p1 < p2 && nums[p2] == nums[p2 - 1]) {
                            p2--;
                        }
                        p1++;
                        p2--;
                    } else if (nums[p1] + nums[p2] < sum) {
                        p1++;
                    } else {
                        p2--;
                    }
                }
            }
        }
        return result;
    }
    public static void main(String[] args) {
        // Test code
        int[] nums = {-1, 0, 1, 2, -1, -4};     // [[-1, -1, 2], [-1, 0, 1]]
        System.out.println(solution(nums));

        nums = new int[] {1, -7, 6, 3, 5, 2};   // [[-7, 1, 6], [-7, 2, 5]]
        System.out.println(solution(nums));
    }
}

---

3차 힌트문제 3번 투포인터

(백준/자바) 힌트문제3 03. 투 포인터 - 백준 2003번 문제 : 수들의 합2 (tistory.com)

(백준/자바) 힌트문제3 03. 투 포인터 - 백준 2003번 문제 : 수들의 합2