[파이썬] 11723. 집합

문제

비어있는 공집합 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

 

 

 

🐹 나의 풀이

import sys
input=sys.stdin.readline
M=int(input())         # 연산 수
S=set()

for i in range(M) :
    cmd=input().split()
    if len(cmd) == 1 :
        if cmd[0] == "all":
            S = set(range(1, 21))
        elif cmd[0] == "empty":
            S.clear()
    else :
        a, b=cmd[0], int(cmd[1])
        if a == "add" :
            S.add(b)
        elif a == "remove" :
            S.discard(b)
        elif a == "check" :   # 출력
            if b in S :
                print(1)
            else :
                print(0)
        elif a == "toggle" :
            if b in S :
                S.discard(b)
            else :
                S.add(b)

여러 번 시도 끝에 통과😊

구현 문제라 문제에 나온 내용 그대로 코드를 작성하면 되지만, 시간초과를 조심해야한다.

아래 시간초과한 코드와 다른점은 두가지다.

1. x의 유무에 따라서 if문, else문으로 나눴다. -> 그렇게 중요하지 않다. if문은 시간복잡도에 영향을 주지 않는다.
2. 집합 S에 문자열이 아닌 정수형으로 값을 저장했다.(map을 사용해서 문자열로 변환하는 과정이 사라짐)

https://yongbbbba.github.io/til/if/

[알고리즘] if문과 시간 복잡도

 

 

# 실패
import sys
input=sys.stdin.readline
M=int(input())              # 연산 수
S=set()

for i in range(M) :
    cmd=input().split()
    if cmd[0] == "add" :
        S.add(cmd[1])
    elif cmd[0] == "remove" :
        S.discard(cmd[1])
    elif cmd[0] == "check" :   # 출력
        if cmd[1] in S :
            print(1)
        else :
            print(0)
    elif cmd[0] == "toggle" :
        if cmd[1] in S :
            S.discard(cmd[1])
        else :
            S.add(cmd[1])
    elif cmd[0] == "all" :
        S=set(map(str, range(1, 21)))
    elif cmd[0] == "empty" :
        S.clear()

71%에서 시간초과 뜸 ㅠ.ㅠ

input()을 sys.stdin.readline()으로 바꾸면 될줄 알았는데..

in을 썼지만, S 집합에 들어갈 원소가 1부터 20까지라 별로 안 되는데🤔

문제점을 찾았다!!

s=set(map(str, range(1, 21))) 때문에 시간초과가 뜬 것이다.

집합 S에 int로 저장하도록 바꾸면 통과한다.

 

 

🎀 다른 사람 풀이

# https://yoonsang-it.tistory.com/38
import sys

m=int(sys.stdin.readline())
S=set()

for _ in range(m) :
    temp=sys.stdin.readline().strip().split()

    if len(temp) == 1 :
        if temp[0] == "all" :
            S=set([i for i in range(1, 21)])
        else :
            S=set()
    else :
        func, x=temp[0], temp[1]
        x=int(x)

        if func == "add" :
            S.add(x)
        elif func == "remove" :
            S.discard(x)
        elif func == "check" :
            print(1 if x in S else 0)
        elif func == "toggle" :
            if x in S :
                S.discard(x)
            else :
                S.add(x)

나랑 차이점이 x가 없는 all, empty와 x가 있는 add, remove, check, toggle을 구분해서 실행한다.

 

 

// https://dragon-h.tistory.com/28
import java.io.*;
import java.util.*;


public class Main{
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
    static StringBuilder sb=new StringBuilder();

    public static void main(String[] args) throws Exception{
        int n=Integer.parseInt(br.readLine());
        int bitset=0;

        while(n-- > 0){
            StringTokenizer st=new StringTokenizer(br.readLine());
            String op=st.nextToken();
            int num;

            switch(op){
                case "add" :
                    num=Integer.parseInt(st.nextToken());
                    bitset|=(1<<(num-1));
                    break;
                case "remove" :
                    num=Integer.parseInt(st.nextToken());
                    bitset=bitset & ~(1 << (num-1));
                    break;
                case "check" :
                    num=Integer.parseInt(st.nextToken());
                    sb.append((bitset & (1<<(num-1))) != 0 ? "1\n" : "0\n");
                    break;
                case "toggle" :
                    num=Integer.parseInt(st.nextToken());
                    bitset^=(1<<(num-1));
                    break;
                case "all" :
                    bitset |= (~0);
                    break;
                case "empty" :
                    bitset &= 0;
                    break;
            }
        }
        bw.write(sb.toString());
        bw.close();
        bw.close();
    }
}

비트마스크 풀이

N비트 정수 변수는 0~N-1까지 정수 원소를 가질 수 있는 집합이 되기 때문에 num-1을 했다.

 

 

 

 

문제 출처 👉 백준