99클럽 코테 스터디 10일차 TIL [Two Pointer]

- 오늘의 학습 키워드 : Two Pointer 알고리즘

[문제 이름 : 좋다 (백준 1253, G4)]
문제 url : https://www.acmicpc.net/problem/1253

내가 작성한 코드는 아래와 같다.

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);
        int count = 0;

        for (int i = 0; i < n; i++) {
            if (goodNumber(i, arr)) {
                count++;
            }
        }

        System.out.println(count);
    }

    static boolean goodNumber(int i, int[] arr) {
        int left = 0;
        int num = arr[i];
        int right = arr.length -1;

        while(left < right) {
            if (left == i) {
                left++;
                continue;
            }
            if (right == i) {
                right--;
                continue;
            }
            int sum = arr[left] + arr[right];

            if(sum == num) {
                return true;
            } else if (sum < num) {
                left++;
            } else {
                right--;
            }
        }

        return false;
    }
}

 

풀이 과정 (풀이 시간 : 30분)

배열이 [-10, -5, 0, 5, 10] 으로 들어오는 경우, index가 0일 때 arr[2] + arr[4]로 값을 더할 수 있는데, 입력1만 보고 이를 고려하지 못해서 추가로 시간이 쓰였다. 음수인 경우를 고려하지 못한 게 큰 실책이었다.

 

1. n을 입력받고, arr에 n개에 해당하는 숫자들을 저장한다.

2. for문을 활용하여, 서로 다른 두 수로 합할 수 있는지 계산한다.
3. 인덱스 번호를 계산하여 left는 arr[0]의 부터, right는 arr[arr.length-1]인 arr.length-1로 값을 초기에 선언한다.

4. 만약 left나 right에서 찾고자 하는 인덱스 값이 같다면, 동일한 수를 더하면 안되므로 이에 대한 처리를 해준다.

5. 나머지는 Two Pointer 알고리즘을 활용해서 서로 다른 두 수로 해당 값을 찾을 수 있는지 while 문에서 반복적으로 탐색한다.

내일은 면접이 있어, 이에 대한 준비를 마무리해보고자 한다.