투 포인터

투 포인터 (Two Pointers)

배열에서 두 개의 포인터를 사용하여 원하는 결과를 얻는 방법
두 개 포인터의 배치 방법
같은 방향에서 시작: 첫 번째 원소에 둘 다 배치
서로 다른 방향에서 시작: 첫 번째 원소와 마지막 원소에 배치
다중 for 문의 복잡도를 좀 더 선형적으로 풀 수 있음

투 포인터 예시

아래 배열에서 부분합이 9가 되는 구간을 찾는 방법
기존 단순 for 문 이용 방법

투 포인터 예시

아래 배열에서 부분합이 9가 되는 구간을 찾는 방법
투 포인터 방법

// 알고리즘 - 투 포인터
// for-loop vs two pointers

import java.util.Arrays;

public class Main {
    public static int[] forLoop(int[] arr, int target) {
        int[] result = {-1, -1};

        for (int i = 0; i < arr.length; i++) {
            int sum = arr[i];
            for (int j = i + 1; j < arr.length; j++) {
                if (sum == target) {
                    result[0] = i;
                    result[1] = j - 1;
                    break;
                }
                sum += arr[j];
            }

            if (sum == target) {
                break;
            }
        }

        return result;
    }

    public static int[] twoPointers(int[] arr, int target) {
        int p1 = 0;
        int p2 = 0;
        int sum = 0;
        int[] result = {-1, -1};
        
        while (true) {
            // 합계가 target 보다 크면 p1 포인터 이동
            if (sum > target) {
                sum -= arr[p1++];
            } else if (p2 == arr.length){
                // 합계가 target 보다 크지 않은 상황에서 p2 이 끝에 도달했으면 해당 구간 없음
                break;
            } else {
                // 합계가 target 보다 작으면 p2 포인터 이동
                sum += arr[p2++];
            }
            
            // 합계가 target 과 같을 때 해당 구간 업데이트 후 반환
            if (sum == 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)));
    }
}

[4, 5]
[-1, -1]

[4, 5]
[-1, -1]

문제풀이

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

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

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

public class Practice1 {
    public static String solution(String s) {
        if (s == null || s.length() == 0) {
            return null;
        }

        int p1 = 0;
        int p2 = s.length() - 1;

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

            // 오른쪽 끝과 같은 왼쪽을 계속 지움
            while (p1 <= p2 && s.charAt(p1) == c) {
                p1++;
            }

            // 오른쪽도 자기 자신과 같은 알파벳은 계속 지움
            while (p1 <= p2 && s.charAt(p2) == c) {
                p2--;
            }
        }
        return s.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
    }
}

ab

cdd

// Practice
// 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)

import java.util.Arrays;
import java.util.HashSet;

public class Practice2 {
    public static int[] solution(int[] nums1, int[] nums2) {
        HashSet<Integer> set = new HashSet<>();
        
        // 우선 두 배열을 정렬
        Arrays.sort(nums1);
        Arrays.sort(nums2);

        int p1 = 0;
        int p2 = 0;
        // 각 배열 범위 안에서 반복문
        while (p1 < nums1.length && p2 < nums2.length) {
            // nums1 쪽이 작으면 p1 증가
            if (nums1[p1] < nums2[p2]) {
                p1++;
            } else if (nums1[p1] > nums2[p2]) {
                // nums2 쪽이 작으면 p2 증가
                p2++;
            } else {
                // 같으면 hash set 에 추가
                set.add(nums1[p1]);
                p1++;
                p2++;
            }
        }
        
        // Hashset -> 배열
        int[] result = new int[set.size()];
        int idx = 0;
        for (Integer n : set) {
            result[idx++] = n;
        }
        return result;
    }

    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)));
    }
}

[2]
[4, 9]
[7, 9]

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

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

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


public class Practice3 {
    public static String solution(String s) {
        if (s == null) {
            return null;
        }

        if (s.length() < 2) {
            return s;
        }

        // 문자열 사이 하나 공백을 제외한 나머지 공백 제거
        s = removeSpaces(s);

        char[] cArr = s.toCharArray();
        // 전체 문자열 뒤집기
        reverseString(cArr, 0, s.length() - 1);

        // 단어 단위 다시 뒤집기
        reverseWords(cArr, s.length());

        return new String(cArr);
    }

    public static String removeSpaces(String s) {
        int p1 = 0;
        int p2 = 0;

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

        while (p2 < length) {
            // 단어 앞 쪽 공백 skip
            while (p2 < length && cArr[p2] == ' ') {
                p2++;
            }

            // 공백 아닌 경우 해당 문자로 채워넣기
            while (p2 < length && cArr[p2] != ' ') {
                cArr[p1++] = cArr[p2++];
            }

            // 단어 뒤쪽 공백 skip
            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 i, int j) {
        while (i < j) {
            char tmp = cArr[i];
            cArr[i++] = cArr[j];
            cArr[j--] = tmp;
        }
    }

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

        while (p1 < length) {
            // p1, p2 로 공백 제외 단어 부분 시작, 끝 설정
            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    "));

    }
}

blue is sky the
java hello

// Practice
// 주어진 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]]


import java.util.ArrayList;
import java.util.Arrays;

public class Practice4 {
    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])) {
                // i 가 가리키는 값을 부호 반전 시킨 후
                // p1 과 p2 가 가리키는 값의 합이 i 가 가리키는 곳과 같은지 비교하는 방식
                int p1 = i + 1;
                int p2 = nums.length - 1;
                int sum = 0 - nums[i];

                while (p1 < p2) {
                    if (nums[p1] + nums[p2] == sum) {
                        // 0 을 만족하는 경우 추가
                        result.add(new ArrayList<>(Arrays.asList(nums[i], nums[p1], nums[p2])));

                        // 중복 피하기 위한 p1, 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));
    }
}

[[-1, -1, 2], [-1, 0, 1]]
[[-7, 1, 6], [-7, 2, 5]]

출처 : 제로베이스