공부 177일차: 백준 11723번 집합 자바 java

11723 집합

https://www.acmicpc.net/problem/11723

11723번: 집합

 

 

 

---

백준 11723번 문제 집합

---

문제

---

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1.5 초	4 MB (하단 참고)	69483	21288	15299	29.221%

문제

비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.

• add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.
• remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.
• check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)
• toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)
• all: S를 {1, 2, ..., 20} 으로 바꾼다.
• empty: S를 공집합으로 바꾼다. 

입력

첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다.

둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.

출력

check 연산이 주어질때마다, 결과를 출력한다.

제한

 

예제 입력 1

26
add 1
add 2
check 1
check 2
check 3
remove 2
check 1
check 2
toggle 3
check 1
check 2
check 3
check 4
all
check 10
check 20
toggle 10
remove 20
check 10
check 20
empty
check 1
toggle 1
check 1
toggle 1
check 1

예제 출력 1

1
1
0
1
0
1
0
1
0
1
1
0
0
0
1
0

힌트

 

 

 

---

과정 생각해보기 & 오답

---

 

https://gimbalja.tistory.com/149

백준 10828번 스택 자바 Java

이것과 같은 형태로 시도해봤지만, 시간 초과가 떴다

import java.io.*;
import java.util.*;
 
public class Main {
 
    // 삭제할 때 인덱스가 아닌 값으로 인식하기 위해 String list
    static ArrayList<String> S = new ArrayList<>();
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        int m = Integer.parseInt(br.readLine());
        
        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            String command = st.nextToken();
            
            switch(command) {
            case "add":
                add(st.nextToken());
                break;
            case "remove":
                remove(st.nextToken());
                break;
            case "check":
                check(st.nextToken());
                break;
            case "toggle":
                toggle(st.nextToken());
                break;
            case "all":
                all();
                break;
            case "empty":
                empty();
                break;
            }
        }
        
        bw.flush();
        bw.close();
    }
    
    static void add(String x) {
        if(S.contains(x)) {    // S에 x가 있으면
            return;
        }
        S.add(x);
    }
        
    static void remove(String x) {
        if(!S.contains(x)) {    // S에 x가 없으면
            return;
        }
        S.remove(x);
    }
    
    static void check(String x) throws IOException{
        if(S.contains(x)) {
            bw.write(1+"\n");
        }else {            
            bw.write(0+"\n");
        }
    }
    
    static void toggle(String x) {
        if(S.contains(x)) {    // 있으면
            S.remove(x);    // 제거
            return;
        }
        S.add(x);    // 없으면 추가
    }
    
    static void all() {
        empty();    // 비우고
        for(int i = 1; i < 21; i++) {
            S.add(i+"");
        }
    }
    
    static void empty() {
        for(int i = 0; i < S.size(); i++) {
            S.remove(i+"");
        }
    }
 
}

그래도 일단 첨부

 

1)

중복을 허용하지 않는 Set을 이용 시 위 코드를 조금만 수정히면 된다

 

2)

문제에서 바라는 풀이 방법이자 메모리와 시간 면에서 효율적인 방법은 바로 비트마스크(비트마스킹, bit mask)

이번에 처음 본 개념인데, 한 마디로 요약하면 컴퓨터처럼 이진수로 자료를 표현하는 방법이다
0 과 1만으로 표현하는 것!

 

이 블로그에 비트 연산자 등이 정리가 매우 잘 되어 있었다

 

 

 

---

정답 인정 코드

---

 

 

1)

 

import java.io.*;
import java.util.*;
 
public class Main {
 
    static Set<Integer> S = new HashSet<>();    // 중복 제거
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        int m = Integer.parseInt(br.readLine());
        
        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            String command = st.nextToken();
            
            switch(command) {
            case "add":
                add(Integer.parseInt(st.nextToken()));
                break;
            case "remove":
                remove(Integer.parseInt(st.nextToken()));
                break;
            case "check":
                check(Integer.parseInt(st.nextToken()));
                break;
            case "toggle":
                toggle(Integer.parseInt(st.nextToken()));
                break;
            case "all":
                all();
                break;
            case "empty":
                empty();
                break;
            }
        }
        
        bw.flush();
        bw.close();
    }
    
    static void add(int x) {
        S.add(x);
    }
        
    static void remove(int x) {
        S.remove(x);
    }
    
    static void check(int x) throws IOException{
        if(S.contains(x)) {
            bw.write(1+"\n");
        }else {            
            bw.write(0+"\n");
        }
    }
    
    static void toggle(int x) {
        if(S.contains(x)) {    // 있으면
            S.remove(x);    // 제거
            return;
        }
        S.add(x);    // 없으면 추가
    }
    
    static void all() {
        for(int i = 1; i < 21; i++) {
            S.add(i);
        }
    }
    
    static void empty() {
        S.clear();
    }
 
}
 

이 블로그 참고

 

 

 

---