[백준] 1253 좋다 - Java

Yunki Kim·2023년 1월 16일
0

백준

목록 보기
101/104
post-thumbnail

문제


링크


코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

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[] numberArray = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < numberArray.length; i++) {
            numberArray[i] = Integer.parseInt(st.nextToken());
        }
        br.close();
        Arrays.sort(numberArray);

        int count = 0;
        for (int k = 0; k < numberArray.length; k++) {
            long findNumber = numberArray[k];
            int pointerI = 0;
            int pointerJ = numberArray.length - 1;
            while (pointerI < pointerJ) {
                if (numberArray[pointerI] + numberArray[pointerJ] == findNumber) {
                    if (pointerI != k && pointerJ != k) {
                        count++;
                        break;
                    } else if (pointerI == k) pointerI++;
                    else pointerJ--;

                } else if (numberArray[pointerI] + numberArray[pointerJ] > findNumber) pointerJ--;
                else pointerI++;
            }
        }
        System.out.println(count);
    }
}

리뷰

주어진 모든 입력에대해 좋은 수인지 판별해야하기 때문에 O(N^2)의 시간복잡도로 문제를 풀게되면 총 O(N^3)이 되어 실패하게된다.

다른 투포인터 문제와 방식은 동일하게 진행된다.
다만 유의해야 할점은 입력되는 수가 정수라는 점을 고려해야 한다.

만약 5가 좋은 수인지 확인하려는데 5와 0을 가리키면 5 + 0 = 5니까 좋은 수라고되면 안되기 때문에 우리가 좋은 수인지 찾을 때 그 숫자 자기자신이 계산에 포함되면 안되는 예외조건이 필요하다.

그래서 두 인덱스의 값의 합이 우리가 찾는 수 일 때 각각의 두 수가 그 수인지 확인하는 작업이 필요하다.
이 부분에서 실수를해서 시간초과가 되었는데 두 수가 찾는 수가 아닌지 판별하는 동시에 만약 가리키는 숫자가 찾는 수였으면 어떻게 해야할지 정해주어야한다.
까먹고 if문을 하나만 두었더니 거기에 갇혀서 나오지못해 시간초과 오류가 발생했다. 😨

0개의 댓글