[백준/JAVA] 18114번: 블랙 프라이데이

🔺 문제

18114번: 블랙 프라이데이

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, C;
    static List<Integer> w = new ArrayList<>(); // 물건 무게 리스트
    static boolean exists = false;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
        N = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
 
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            w.add(Integer.parseInt(st.nextToken()));
 
            if(w.get(i) == C) {
                System.out.println(1);
                return;
            }
        }
        Collections.sort(w);   // 이진 탐색 위해 오름차순 정렬
 
        int start = 0;
        int end = N - 1;
        int weight;
 
        while(start < end) {
            weight = w.get(start) + w.get(end); // 물건 2개 골라놓은 상태
 
            if(weight > C) {
                end--;
            }
            else if(weight == C) {
                System.out.println(1);
                return;
            }
            else {
                if(start < w.indexOf(C - weight) && w.indexOf(C - weight) < end) { // 물건들의 합이 C가 될 수 있는지만 확인
                    System.out.println(1);
                    return;
                }
                start++;
            }
        }
 
        System.out.println(0);
    }
}

 

 

 

🧩  해결 아이디어

• 이진 탐색 

1. 리스트에 물건들의 무게 값을 저장한다.

2. 리스트를 오름차순 정렬한다. (이진탐색 목적)

3. 이진 탐색을 통해 물건을 2개 골라둔다.

 

 이 때 물건 2개의 값이 목표 무게보다 크다면 끝 범위를 줄이고,

작다면  목표 무게에서 현재 2개의 무게 값을 빼서 C를 만들 수 있는지 확인하고 시작 범위를 높인다.

 

물건 2개의 값이 목표 무게 값이라면 1을 출력한다.

 

 

 

---

🔺 다른 풀이들

- 정렬 후 1개 선택 시에는 이분탐색,

2개 선택 시에는 for문으로 1개 선택하고 left를 i + 1로 잡고 찾고,

3개 선택 시에는 2중 for문으로 2개 선택하고 나머지 elft를 j + 1로 잡고 찾으셨다. (시간 복잡도 : O(N^2 log N))

 

백준 18114번 - 블랙 프라이데이

 

 

- HashSet을 활용하셨다. 간단스!! (시간 복잡도 : O(N^2))

[자바] 백준 18114 - 블랙 프라이데이 (boj java)

---

💬 느낀 점

문제가 짧아서 만만하게 보았는데

아이디어 생각까지 은근히 오래 걸리는 문제다..

담엔 혼자 생각해내서 풀어보고 싶다.

 

1회독	2회독	3회독	4회독	5회독
V	240220

---

(참고)

[백준] 18114번 - 블랙 프라이데이 by Java(자바)