문제 : https://www.acmicpc.net/problem/10815

풀이 방법

  1. 첫번째 접근방법

처음에는 배열을 이용해서 접근하려고 했습니다. 상근이가 몇개의 숫자 카드를 가지고 있는지 그리고 어떤 숫자 카드를 가지고 있는지 입력 받고, 그 후에는 카드의 갯수와 카드를 입력 받아서 후에 입력받은 카드를 상근이가 가지고 있는지 없는지 여부를 확인하였습니다.

상근이가 숫자 카드를 가지고 있다면 1, 가지고 있지 않다면 0을 출력하게 됩니다. 그래서 저는 N, M 크기의 배열 2개를 만들고 각 배열에 저장해서 서로 비교할 수 있도록 구현했습니다.

문제에서 주어진 테스트 케이스를 만족시키는 답을 얻을 수 있었습니다. 허나 시간 초과를 피하지 못했습니다. 문제를 풀면서도 이 문제는 시간 초과가 날 것 같다는 느낌이 들었지만, 일단 무작정 풀어보았습니다. 결과는, 역시나… 그래서 다른 방법으로 풀어보았습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
package language;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ10815 {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine()); // 상근이가 가지고 있는 카드의 갯수
        //Set<Integer> set = new HashSet<>();
        ArrayList<Integer> list = new ArrayList<>();
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
        for(int i=0;i<N;i++){
            list.add(Integer.parseInt(st.nextToken()));
        }

        //Set<Integer> check_set = new HashSet<>();
        ArrayList<Integer> checkList = new ArrayList<>();
        int M = Integer.parseInt(bf.readLine());
        StringTokenizer st2 = new StringTokenizer(bf.readLine(), " ");
        for(int i=0;i<M;i++){
            checkList.add(Integer.parseInt(st2.nextToken()));
        }

        for(int i=0;i<M;i++){
            for(int j=0;j<N;j++){
                if(checkList.get(i).equals(list.get(j))){
                    checkList.set(i,1);
                }
                else{
                    continue;
                }
            }
            if(!checkList.get(i).equals(1)){
                checkList.set(i,0);
            }
        }

        Iterator<Integer> iterator = checkList.iterator();
        while (iterator.hasNext()){
            System.out.print(iterator.next()+" ");
        }
    }
}
// 결과
시간 초과....ㅜㅜ
  1. 두 번째 방법

그 다음으로는 Set 자료 구조를 이용하는 것입니다. Set 자료구조는 기본적으로 중복된 값의 저장을 허용하지 않고, 값이 정렬된 것처럼 저장됩니다. 여기서는 Set의 특성을 이용하지는 않지만, 배열보다는 더욱 편리하게 다룰 수 있을 것 같아서 이 자료구조를 사용하기로 결정했습니다.
[List를 사용해도 비슷한 결과를 얻을 수 있다고 생각합니다.]

그리고 문제를 다시 살펴보면서 2개의 Set을 만들어서 값을 가지고 있을 필요가 없다고 생각했습니다. 어차피 우리가 가지고 있어야 할 값들은 상근이가 가지고 있는 숫자 카드이기 때문에 상근이가 가지고 있는 숫자 카드만 Set 자료구조에 저장해서 가지고 있도록 했습니다.

M개의 숫자 카드를 가지고 있는지 확인하기 위해서 숫자 카드를 입력받는데 이 부분은 Set을 통해 값을 저장하지 않아도 됨을 깨달았습니다. 이유는 여기서 입력받는 값을 사용하지 않고 단순하게 상근이가 가지고 있는 카드인지 아닌지를 비교하기 위해서 사용하는 일회성 값이라고 판단되어 입력 받은 즉시 Set에 포함되어 있는지 contains() 메소드를 사용해서 확인해주었습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ10815 {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine()); // 상근이가 가지고 있는 카드의 갯수
        Set<Integer> set = new HashSet<>(); // 상근이가 가지고 있는 카드를 담을 Set 자료구조
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
        for(int i=0;i<N;i++){
            set.add(Integer.parseInt(st.nextToken()));
        }

        int M = Integer.parseInt(bf.readLine());
        StringTokenizer st2 = new StringTokenizer(bf.readLine(), " ");

        /*FIXME
        * 여기서는 어차피 기존에 상근이가 가지고 있는 카드와
        * 입력받은 카드를 비교해서 상근이가 가지고 있는지 가지고 있지 않은지
        * 판단하므로 굳이 Set을 통해서 값을 저장하지 않아도 됨.
        * 입력 받은 그대로 비교하면 된다.
        * */
        for(int i=0;i<M;i++){
            if(set.contains(Integer.parseInt(st2.nextToken()))){
                System.out.print(1+" ");
            }else {
                System.out.print(0+" ");
            }
        }
    }
}
// 입력
5
6 3 2 10 -10
8
10 9 -5 2 3 4 5 -10
// 출력 결과
1 0 0 1 1 0 0 1
  1. 세 번째 방법

이 방법은 두 번째 방법과 똑같은 형태로 구현하지만, 실행 시간을 줄이기 위한 방법입니다. 두 번째 방법으로 문제를 풀면 실행시간은 1.9초 정도 나오게 됩니다. 이 문제의 시간 제한이 2초인 것에 비하면 그 안에 들어서 문제는 없습니다. 하지만 다른 사람들이 푼 코드를 통해서 시간을 줄일 수 있는 방법을 찾았습니다.

그 방법은 System.out.print()를 빈번하게 호출하는 것보다는 StringBuilder 객체를 만들어서 append() 함수를 통해 값을 추가하고 마지막으로 한 번만 최종 결과를 출력해 주는 것입니다. 이 방법은 실행 시간이 0.9초 나오는 것을 확인할 수 있었고, 두 번째 방법과 1초 정도의 실핼 시간 차이가 남을 확인할 수 있었습니다.

실행 시간을 단축할 수 있는 방법을 찾았습니다. :)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
package language;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ10815 {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine()); // 상근이가 가지고 있는 카드의 갯수
        Set<Integer> set = new HashSet<>(); // 상근이가 가지고 있는 카드를 담을 Set 자료구조
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
        for(int i=0;i<N;i++){
            set.add(Integer.parseInt(st.nextToken()));
        }

        int M = Integer.parseInt(bf.readLine());
        StringTokenizer st2 = new StringTokenizer(bf.readLine(), " ");

        /*FIXME
        * 여기서는 어차피 기존에 상근이가 가지고 있는 카드와
        * 입력받은 카드를 비교해서 상근이가 가지고 있는지 가지고 있지 않은지
        * 판단하므로 굳이 Set을 통해서 값을 저장하지 않아도 됨.
        * 입력 받은 그대로 비교하면 된다.
        * */
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<M;i++){
            if(set.contains(Integer.parseInt(st2.nextToken()))){
                sb.append(1+" ");
            }else {
                sb.append(0+" ");
            }
        }
        System.out.println(sb.toString());

    }
}
// 입력
5
6 3 2 10 -10
8
10 9 -5 2 3 4 5 -10
// 출력 결과
1 0 0 1 1 0 0 1

단 3줄의 차이로 실행시간이 1초 줄어든 것을 확인할 수 있습니다. 앞으로 알고리즘 문제를 풀었더라도 실행 시간을 줄이는 방법을 찾아보고 공부해보는 것도 좋은 경험이 되고 실력도 쌓일 것 같습니다.