[Algorithm] Two Pointers

시간 복잡도를 O(n^2)에서 O(n)으로 바꿀 수 있는 Two Pointers 알고리즘을 활용하여 문제를 해결해본다.
모든 코드는 깃허브 (링크)의 테스트 코드로 정리해두었다.

---

두 배열 합치기

오름차순으로 정렬이 된 두 배열이 주어지면 두 배열을 오름차순으로 합쳐 출력하는 프로그램을 작성하세요.

• 입력설명
  첫 번째 줄에 첫 번째 배열의 크기 N(1<=N<=100)이 주어집니다. 두 번째 줄에 N개의 배열 원소가 오름차순으로 주어집니다.
  세 번째 줄에 두 번째 배열의 크기 M(1<=M<=100)이 주어집니다. 네 번째 줄에 M개의 배열 원소가 오름차순으로 주어집니다.
  각 리스트의 원소는 int형 변수의 크기를 넘지 않습니다.
• 출력설명
  오름차순으로 정렬된 배열을 출력합니다.
• 입력예제 1
  3
  1 3 5
  5
  2 3 6 7 9
• 출력예제 1
  1 2 3 3 5 6 7 9

public class CombiningTwoArray {

    public Integer[] solution1(int[] arr1, int[] arr2) {
        List<Integer> answer = new ArrayList<>();
        int arr1Position = 0;
        int arr2Position = 0;
        while (arr1Position < arr1.length && arr2Position < arr2.length) {
            if (arr1[arr1Position] <= arr2[arr2Position]) {
                answer.add(arr1[arr1Position++]);
            } else {
                answer.add(arr2[arr2Position++]);
            }
        }
        while (arr1Position < arr1.length) {
            answer.add(arr1[arr1Position++]);
        }
        while (arr2Position < arr2.length) {
            answer.add(arr2[arr2Position++]);
        }

        return answer.toArray(new Integer[0]);
    }

    @Test
    @DisplayName("두 배열 합치기")
    public void main() {
        int[] arr1 = {1, 3, 5};
        int[] arr2 = {2, 3, 6, 7, 9};
        Integer[] expectedAnswer = {1, 2, 3, 3, 5, 6, 7, 9};
        Integer[] answer1 = solution1(arr1, arr2);
        assertArrayEquals(expectedAnswer, answer1);
    }

}

---

공통 원소 구하기

A, B 두 개의 집합이 주어지면 두 집합의 공통 원소를 추출하여 오름차순으로 출력하는 프로그램을 작성하세요.

• 입력설명
  첫 번째 줄에 집합 A의 크기 N(1<=N<=30,000)이 주어집니다.
  두 번째 줄에 N개의 원소가 주어집니다. 원소가 중복되어 주어지지 않습니다. 세 번째 줄에 집합 B의 크기 M(1<=M<=30,000)이 주어집니다.
  네 번째 줄에 M개의 원소가 주어집니다. 원소가 중복되어 주어지지 않습니다. 각 집합의 원소는 1,000,000,000이하의 자연수입니다.
• 출력설명
  두 집합의 공통원소를 오름차순 정렬하여 출력합니다.
• 입력예제 1
  5
  1 3 9 5 2
  5
  3 2 5 7 8
• 출력예제 1
  2 3 5

public class FindingCommonElements {

    public Integer[] solution1(int[] arr1, int[] arr2) {
        List<Integer> answer = new ArrayList<>();
        Arrays.sort(arr1);
        Arrays.sort(arr2);
        int position1 = 0;
        int position2 = 0;

        while (position1 < arr1.length - 1 && position2 < arr2.length - 2) {
            if (arr1[position1] == arr2[position2]) {
                answer.add(arr1[position1++]);
                position2++;
            } else if (arr1[position1] <= arr2[position2]) {
                position1++;
            } else {
                position2++;
            }
        }
        return answer.toArray(new Integer[0]);
    }

    @Test
    @DisplayName("공통 원소 구하기")
    public void main() {
        int[] arr1 = {1, 3, 9, 5, 2};
        int[] arr2 = {3, 2, 5, 7, 8};
        Integer[] expectedAnswer = {2, 3, 5};
        Integer[] answer1 = solution1(arr1, arr2);
        assertArrayEquals(expectedAnswer, answer1);
    }

}

---

연속된 자연수의 합

N입력으로 양의 정수 N이 입력되면 2개 이상의 연속된 자연수의 합으로 정수 N을 표현하는 방법의 가짓수를 출력하는 프로그램을 작성하세요.
만약 N=15이면
7+8=15
4+5+6=15
1+2+3+4+5=15
와 같이 총 3가지의 경우가 존재한다.

• 입력설명
  첫 번째 줄에 양의 정수 N(7<=N<1000)이 주어집니다.
• 출력설명
  첫 줄에 총 경우의 수를 출력합니다.
• 입력예제 1
  15
• 출력예제 1
  3

public class SumOfNaturalNumber {

    // TwoPointers 와 SlidingWindow 를 활용한 방법
    public int solution1(int input) {
        int answer = 0;
        int[] numbers = new int[input];
        for (int i = 0; i < input; i++) {
            numbers[i] = (i + 1);
        }
        int p1 = 0;
        int p2 = 0;
        int tmpSum = 0;
        while (p2 < input) {
            if (tmpSum < input) {
                tmpSum += numbers[p2++];
            } else if (tmpSum > input) {
                tmpSum -= numbers[p1++];
            } else {
                answer++;
                tmpSum -= numbers[p1++];
            }
        }
        return answer;
    }

    // 수학을 활용한 방법 (input = 15인 경우를 예로 들어)
    // 두 개의 수로 만들 수 있는지 확인
    // (15 - 1 - 2) / 2 의 소수점이 없으므로 가능
    // 세 개의 수로 만들 수 있는지 확인
    // (15 - 1 - 2 - 3) / 3 의 소수점이 없으므로 가능
    // (15 - ***) / 3 이 0인 경우가 나올 때까지 반복
    public int solution2(int input) {
        int answer = 0;
        // 몇 개의 수로 만들 것인지 카운트
        int count = 1;
        input--;
        while (input > 0) {
            count++;
            input -= count;
            if (input % count == 0) {
                answer++;
            }
        }
        return answer;
    }

    @Test
    @DisplayName("연속된 자연수의 합")
    public void main() {
        int expectedAnswer = 3;
        int answer1 = solution1(15);
        assertEquals(expectedAnswer, answer1);
        int answer2 = solution2(15);
        assertEquals(expectedAnswer, answer2);
    }

}

---

참고한 강의: https://www.inflearn.com/course/%EC%9E%90%EB%B0%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%ED%85%8C%EB%8C%80%EB%B9%84