백준-11723번/집합(java)

 

 

문제 접근

 

문제를 보자마자 HashSet의 특징이 떠올라서 HashSet을 이용하여 풀면 간단하게 풀 수 있겠다는 생각을 가지고 구현해보았다.

 

<HashSet을 이용한 풀이>

import java.util.HashSet;
import java.util.Scanner;

public class Problem11723 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        String calculation;
        int num;
        HashSet<Integer> S = new HashSet<Integer>();

        for(int i=0; i<N; i++){
            calculation=scanner.next();
            if(calculation.equals("add")){
                num=scanner.nextInt();
                S.add(num);
            }
            else if(calculation.equals("check")){
                num=scanner.nextInt();
                if(S.contains(num)){
                    System.out.println("1");
                }
                else{
                    System.out.println("0");
                }
            }
            else if(calculation.equals("remove")){
                num=scanner.nextInt();
                S.remove(num);
            }
            else if(calculation.equals("toggle")){
                num=scanner.nextInt();
                if(S.contains(num)){
                    S.remove(num);
                }
                else{
                    S.add(num);
                }
            }
            else if(calculation.equals("all")){
                for(int j=1; j<=20; j++){
                    S.add(j);
                }
            }
            else if(calculation.equals("empty")){
                S.clear();
            }
        }
    }
}

 

 

제출결과 시간초과가 발생하였다.

 위 코드에서 런타임을 최소화 할 수 있는 방법이 무엇이 있나 생각해보면서 차근차근 풀어 나갔다.

 

문제 풀이

 

우선 Scanner 객체를 사용하여 입력을 받는 대신 BufferedReader와 StringTokenizer를 이용하여 입력을 받아서 더 빠른 연산을 가능하도록 하였다.

 

이후 기존의 HashSet을 더 간단한 연산 수행을 위해 크기가 21인 boolean함수로 교체하여 숫자가 집합에 들어있으면 true, 없으면 false를 가지도록 하였다.

 

여기 까지만 해도 연산 시간을 많이 줄였다고 생각하고 제출한 결과 또 시간 초과가 발생하였다..

 

 

 

시간을 더 줄일 수 있는 방법이 하나 더 있었는데  System.out.println()을 통해 그때그때 출력하는 것 보다 StringBuilder를 이용하여 출력을 한번에 바로 하는 방법이다.

 

case "check":
    num = Integer.parseInt(st.nextToken());
    sb.append(S[num] ? "1\n" : "0\n");
    break;

 

이 방법을 적용했더니 시간 제한 안에 수행 되었다.

 

<전체 코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Problem11723_2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        String calculation;
        int num;
        boolean[] S= new boolean[21];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            calculation = st.nextToken();
            switch (calculation) {
                case "add":
                    num = Integer.parseInt(st.nextToken());
                    S[num]=true;
                    break;
                case "check":
                    num = Integer.parseInt(st.nextToken());
                    sb.append(S[num] ? "1\n" : "0\n");
                    break;
                case "remove":
                    num = Integer.parseInt(st.nextToken());
                    S[num]=false;
                    break;
                case "toggle":
                    num = Integer.parseInt(st.nextToken());
                    if (S[num]) {
                        S[num]=false;
                    }else{
                        S[num]=true;
                    }
                    break;
                case "all":
                    Arrays.fill(S,true);
                    break;
                case "empty":
                    Arrays.fill(S,false);
                    break;
            }
        }
        System.out.print(sb.toString());
    }
}