Java 백준 문제풀이 (42) 1253 : 좋다

실패 아니라고..

 

 

이분탐색, 투포인터 등으로 풀 수 있는 문제다.

투포인터 알고리즘에 대한 설명은 지난 글들에서 충분히 다루었기 때문에 생략한다.

투포인터 알고리즘을 모르면 아래의 기초 문제들을 먼저 풀어보자.

 

https://7357.tistory.com/235?category=1066252 

Java 백준 문제풀이 (40) 2018번: 수들의 합5

https://7357.tistory.com/236?category=1066252 

Java 백준 문제풀이 (41) 1940번 : 주몽

 

 

일단 늘 하던 방식대로, 예제를 손으로 그려서 어떻게 풀면 좋을지 생각해보자.

나는 손으로 그렸으나 캡쳐해서 옮기기 귀찮으니 키보드로 작성하겠다.

 

1	2	3	4	5	6	7	8	9	10
Lpointer	Rpointer	K

 

와.. 이렇게만 했을 뿐인데 벌써 완전 괜찮은 풀이법이 탄생한 것 같다.

우선 수를 정렬하고, K를 늘려가며 K보다 작은 수의 범위에서 

Sum이 K보다 크다면 Rpointer--; , Sum이 K보다 작다면 Lpointer++;하면 되겠네요 ㄷ ㄷ

 

늘 그렇듯 풀이법이 너무 쉽게 떠오르면 틀리더라

 

ㅋㅋ

ㅜ

 

 

저 방식으로 풀고 1시간을 맞왜틀하느라 시간 날렸다.

위 방법으로는 다음 조건들을 만족시키지 못한다.

1. 처음 주어지는 3개의 수 중 K와 중복되는 수가 존재하는 경우 ( 예 : 0 3 3 ) 

2. 음수가 존재하는 경우 ( 예 : -2 0 2 )

 

 

따라서 매번 배열의 시작부터 끝까지 모든 경우의 수를 체크해서 경우의 수를 구해야 한다..

결국 N개의 원소를 가진 배열을 N번 반복하므로 이 풀이 방법은 O(N^2)의 시간 복잡도를 가지게 된다.

 

이 부분만 실수하지 않는다면 투 포인터 알고리즘을 알고 있다는 가정 하에 어려운 문제가 아니기에 더 이상의 설명은 생략한다.

 

 

 

 

 

 

 

 

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        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 answer = 0;
        for (int i=0; i<N; i++) {
            int left = 0;
            int right = N - 1;
            int sum;
 
            while (left < right) {
                if ( left == i ) {
                    left++;
                }
                else if ( right == i ) {
                    right--;
                }
                else {
                    sum = arr[left] + arr[right];
 
                    if (sum == arr[i]) {
                        answer++;
                        break;
                    }
 
                    if (sum > arr[i]) {
                        right--;
                    }
 
                    if (sum < arr[i]) {
                        left++;
                    }
                }
            }
        }
 
        System.out.println(answer);
    }
}