[백준/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")
}