[백준/Java, Kotlin] 18114번 블랙 프라이데이

 

 

 

문제 풀이 (Java만 설명)

 

총 4가지의 방법으로 풀이했다. 다른 부분은 거의 비슷하고 3개의 물건을 고르는 부분만 다르다.

시간이 오래 걸린 풀이 방법부터 간단하게 설명해보겠다.

 

1. 반복문

BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());

int N = Integer.parseInt(st.nextToken());
int C = Integer.parseInt(st.nextToken());

int[] things = new int[N];

Boolean isFriday = false;

st = new StringTokenizer(bf.readLine());
for(int i=0; i<N; i++) {
    int input = Integer.parseInt(st.nextToken());
    if(input == C) {
        things[i] = 0;
    }else {
        things[i] = input;
    }
}

Arrays.sort(things);

1. 주어진 입력을 받고, 정수 배열을 생성해 물건의 무게를 담는다.

이 때, 물건의 무게가 C라면 즉, 한 개의 물건으로도 무게 C를 만족한다면 이 때 배열에 C를 넣지 않고, 0을 넣는다.

 

그리고 배열을 오름차순 정렬한다.

 

if(things[0] == 0) {
    System.out.println(1);
    return;
}

2. 오름차순 했을 때, 배열의 0번 인덱스가 0이라면 1을 출력하고 리턴한다.

(근데 이건 그냥 입력 받을 때 C를 만족하면 1을 출력하고 리턴하는게 더 간단한 방법 같음.)

 

int start = 0;
int end = N-1;

while(start < end) {
    int sum = things[start] + things[end];

    if(sum == C) {
        isFriday = true;
        break;

    }else if(sum > C) {
        end--;
    }else {
        for(int i=start+1; i<end; i++) {
            if(sum + things[i] == C) {
                isFriday = true;
                break;
            }
        }
        start++;
    }
}

3. 이제 투포인터로 무게를 찾을 시간이다.

두 포인터는 양쪽 끝에서 시작한다.

start < end 을 만족할 때까지 while 문을 반복한다.

start, end에는 각각 인덱스 값이 담겨있기 때문에 두 포인터가 가르키는 인덱스의 무게를 더해 sum 변수에 담는다.

 

sum == C라면

2개의 물건으로 무게 C 만큼 담을 수 있기 때문에 isFriday = true 바꿔준다.

(isFriday는 C를 만족할 때 true로 바꾸도록 함.)

(이 역시 변수를 따로 생성하지 않고 출력 후 리턴하는게 좋음)

 

sum이 C보다 크다면

end에 -1을 더한다.

 

sum이 C보다 크다면

이 때는 2개를 더했을 때 아직 무게가 다 차지 않았기 때문에 C - sum을 만족하는 무게를 가진 물건이 있는지 확인해봐야한다.

이 때 나는 반복문을 사용했다. start와 end 사이에 만족하는 무게가 있다면 마찬가지로 isFriday를 true로 바꾸고 멈췄다.

 

모두 만족하지 않다면 start를 1 증가시킨다. 

 

if(isFriday) {
    System.out.println(1);
}else {
    System.out.println(0);
}

4. 마지막으로 isFriday가 true라면 1을, false라면 0을 출력한다.

isFriday가 true 라는 것은 things 배열에 최소 1개의 물건 ~ 최대 3개의 물건을 더했을 때 C가 된다는 것을 의미한다.

 

이렇게 했더니 시간이 152ms가 나왔고, 채점 현황을 보니까 더 짧은 풀이가 있어서 다른 풀이로 풀어봤다.

 

 

 

2. 어레이 리스트에 값이 있는가? - indexOf()

첫번째 풀이와 다른 점은 정수 배열이 아닌 ArrayList를 생성했다.

왜냐하면 indexOf를 사용하기 위해서다.

 

앞부분은 모두 같은 코드이니 생략하겠다.

 

while(start < end) {
    int sum = things.get(start) + things.get(end);

    if(sum == C) {
        isFriday = true;
        break;

    }else if(sum > C) {
        end--;
    }else {
        if(things.indexOf(C - sum) > start && things.indexOf(C - sum) < end) {
            isFriday = true;
            break;
        }
        start++;
    }
}

1. 두 포인터를 움직이는 부분 중 [ sum < C ] 를 만족하는 부분만 보겠다.

 

if(things.indexOf(C - sum) > start && things.indexOf(C - sum) < end) {
    isFriday = true;
    break;
}

2. things.indexOf( num ) 은 things 라는 리스트에 num이라는 숫자가 몇 번째 인덱스에 있는지를 의미한다.

만약 없다면 -1을 출력한다.

 

C(담을 수 있는 무게)에서 sum(현재 물건 2개의 무게)을 뺀 값의 인덱스가 start보다 크거나 end보다 작아야한다.

그 이유는 물건은 중복해서 담을 수 없기 때문이다.

처음에 나는 왜 굳이 인덱스를 사용해야하는거지 ?

 

things.contains(C - sum)을 사용하면 안 되는 건가 했는데 이 때는 반례가 존재한다.

예제
5 16
1 2 4 7 19

이 예제를 보면 (2,7) 일 때 위의 코드를 실행할 것이다.

이 때 C - sum = 16 - (7 + 2) = 7 인데 things.contains(C - sum) 를 사용하면 true를 반환한다.

하지만 물건을 중복해서 사용할 수 없고, 문제에서 같은 무게는 주어지지 않기 때문에 해당 값이 포함되어 있는지 아닌지로 비교하면 안 되고 인덱스로 확인해야한다.

 

 

 

 

3. 중복 두 포인터

}else {
    int s = start+1; int e = end-1; int c = C - (things[start] + things[end]);

    while(s <= e) {
        if(things[s] == c || things[e] == c) {
            System.out.println(1);
            return;
        }else{
            s++;
            e--;
        }
    }
    start++;
}

나머지 코드는 1번과 동일하고  sum < C 인 부분만 다르다.

이 때는 현재 start, end 사이의 값들 중 C - sum을 만족하는 값이 있는지 확인한다.

 

두 포인터를 동시에 움직이며 C  - sum 의 유무를 확인한다.

 

 

 

4. 두 포인터, 이분탐색

else {
    int s = start+1; int e = end-1; int c = C - sum;

    while(s <= e) {
        int mid = (s+e)/2;

        if(things[mid] == c) {
            System.out.println(1);
            return;
        }else if(things[mid] > c) {
            e = mid-1;
        }else {
            s = mid+1;
        }
    }
    start++;
}

이 코드도 마찬가지로 나머지 코드는 1번 코드와 동일하고 아래 전체 코드를 남겨뒀다.

 

이분 탐색으로 풀어 시간을 최소한으로 만들었다.

설명은 생략하겠다.

 

코드

• Java 코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());
		
		int[] things = new int[N];
		
		Boolean isFriday = false;
		
		st = new StringTokenizer(bf.readLine());
		for(int i=0; i<N; i++) {
			int input = Integer.parseInt(st.nextToken());
			if(input == C) {
				things[i] = 0;
			}else {
				things[i] = input;
			}
		}
		
		Arrays.sort(things);
		
		if(things[0] == 0) {
			System.out.println(1);
			return;
		}
		
		int start = 0;
		int end = N-1;
		
		while(start < end) {
			int sum = things[start] + things[end];
			
			if(sum == C) {
				isFriday = true;
				break;
				
			}else if(sum > C) {
				end--;
			}else {
				int s = start+1; int e = end-1; int c = C - sum;
				
				while(s <= e) {
					int mid = (s+e)/2;
					
					if(things[mid] == c) {
						System.out.println(1);
						return;
					}else if(things[mid] > c) {
						e = mid-1;
					}else {
						s = mid+1;
					}
				}
				start++;
			}
		}
		
		if(isFriday) {
			System.out.println(1);
		}else {
			System.out.println(0);
		}
	}
}

 

• Kotlin 코드

fun main(){
    var (N, C) = readln().split(" ").map{ it.toInt() }
    var things = readln().split(" ").map{ it.toInt() }.toIntArray()

    things.sort()

    //물건 한 개
    if(things.contains(C)){
        println("1")
        return
    }

    var start = 0
    var end = N - 1

    while(start < end){
        var sum = things[start] + things[end]
		//물건 2가지로 된다면
        if(sum == C){
            println("1")
            return
        }else if(sum > C){
            end--
        }else{
            //물건 3가지로 되는지 확인
            var s = start+1
            var e = end-1
            var sumValue = C - sum

            while(s <= e){
                var mid = (s + e) / 2

                if(things[mid] == sumValue){
                    println("1")
                    return
                }else if(things[mid] > sumValue){
                    e = mid-1
                }else{
                    s = mid+1
                }
            }
            start++
        }
    }

    println("0")
}