문제:

비어있는 공집합 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 연산이 주어질때마다, 결과를 출력한다.

풀이방법:

python의 set의 내장함수를 적절히 사용하면 쉽게 풀 수 있다.

1. add : set의 add를 사용한다. python의 set은 중복을 지원하지 않기 때문에 x가 이미 있는 경우에는 중복으로 들어가지 않는다.

2. remove : set에서 원소를 제거하는 방법은 remove와 discard가 있다. remove는 원소가 없는 경우 에러를 반환하지만 discard를 그렇지 않다. 따라서 discard를 사용한다.

3. check : python의 in 기능을 사용한다.

4. toggle : 1. add, 2. remove, 3.check의 기능을 적절히 활용하면 된다. 이 명령어에서 원소를 제거하는 경우에는 항상 있다는 보장이 있으므로 remove를 사용했다.

5. all : S를 재정의한다.

6. empty: S를 재정의한다.

연산의 수가 매우 많으므로 sys.stdin.readline()를 사용해서 빠른 입력을 사용한다.

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
import sys
 
= int(sys.stdin.readline())
=set()
for _ in range(M):
    command = sys.stdin.readline().split()
    if command[0]=="add":
        S.add(int(command[1]))
    elif command[0== "remove":
        S.discard(int(command[1]))
    elif command[0== "check":
        if int(command[1]) in S:
            print(1)
        else:
            print(0)
    elif command[0== "toggle":
        if int(command[1]) in S:
            S.remove(int(command[1]))
        else:
            S.add(int(command[1]))
    elif command[0== "all":
        S = set(list(range(1,21)))
    elif command[0== "empty":
        S = set()
    else:
        print("Invalid command")
cs

문제링크:

www.acmicpc.net/problem/11723

 

11723번: 집합

첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.

www.acmicpc.net

 

'Algorithm > Python' 카테고리의 다른 글

[BOJ]1613. 역사  (0) 2020.12.31
[BOJ]13908. 비밀번호  (0) 2020.12.29
[BOJ]1527. 금민수의 개수  (0) 2020.12.22
[BOJ]7453. 합이 0인 네 정수  (0) 2020.12.10
[BOJ]2294. 동전 2  (0) 2020.12.08

+ Recent posts