백준 3273 번 - 자바

 

 

아마 이 문제는 이중포인터로 풀라고 만든 것 같은데 나는 먼저 생각난게 TreeSet이라서 트리셋으로 풀었다.

 

집합은 뭘 해도 시간복잡도가 낮으니까.

 

아이디어는 이거다.

 

1. 어차피 중복을 허용하지 않으니까 더한 값이 x가 될 때 짝은 무조건 하나밖에 없으므로 모두 지우면서 result++해준다.

2. a + b > x라면, 가장 작은 수인 a랑 더해도 큰거기 때문에 b를 삭제한다.

3. a + b < x라면, 가장 큰 수인 b랑 더해도 작은거기 때문에 a를 삭제한다.

 

인덱스가 하나거나 없으면 break;

 

TreeSet은 집합이지만 알아서 정렬이 되는 자료구조다. 참고하자.

 

왜인지 모르겠는데 set.size가 1일 때는 어차피 

 

처음에는 계속  NoSuchElementException이 떴는데 이유를 모르다가

사이즈가 겹치면 안된다는 조건을 이후에 봐서

if(set.isEmpty()) =>  if(set.isEmpty() || set.size()==1 로 바꿨는데 에러가 사라졌다.

 

솔직히 어디서 에러뜬건지는 알려주면 좋겠다.

 

이유인 즉슨, 만약에 1밖에 없는 배열에 2가 있다면, 카운트로 들어가고 두 개의 index를 remove한다.

하지만 set의 size는 1이므로 empty한 set을 remove하기 때문에  NoSuchElementException이 뜨는거였다.

 

답안은 아래와 같다.

 

package programers;

import java.util.*;
import java.util.Scanner;

public class Main {
    public int solution(int N,int[] friends, int x) {
        int result = 0;
        TreeSet<Integer> set = new TreeSet<>();
        Arrays.stream(friends).forEach(e -> set.add(e)); // 트리셋에 애드하기


        while (true) {
            if(set.isEmpty() || set.size()==1) { 
                break;
            }
            if(set.first() + set.last() == x) { // 짝은 하나기 때문에 맞으면 둘다 없앤다.
                result++;
                set.remove(set.first());
                set.remove(set.last());

            } else if(set.first() + set.last() > x) { // 제일 작은거 합해도 더 크기 때문에 last는 필요 없다.
                set.remove(set.last());
            }
            else { // 제일 큰거 합해도 더 작기 때문에 제일 작은 first는 필요 없다.
                set.remove(set.first());

            }
        }
        return result;
    }

    public static void main(String[] args) {
        Main num = new Main();
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] arr = new int[N];
        for(int i=0; i<N; i++) {
            arr[i] = sc.nextInt();
        }
        int X = sc.nextInt();

        System.out.println(num.solution(N, arr, X));
    }
}