백준/ Silver 5 문제 , 백준 파이썬 11723 , 집합

백준/ Silver 5 문제 , 백준 파이썬 11723 , 집합

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
아니 시간초과가 계속 떠가지고 몇번을 수정했는지 모르겠다...계속 수정하고 제출하고 수정하고 제출하고...

 

<문제 출처>

 

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

11723번: 집합

 

------------------------------------------------------------------------------------------------------------------------------

 

다음은 내가 제출했던 코드들이다. 

 

 

1) 메모리 초과

 

import sys
input=sys.stdin.readline

S=[]

for _ in range(int(input())):
    order=input().split()
    if order[0]=='add':
        S.append(order[1])
    elif order[0]=='remove':
        if order[1] in S:
            S.remove(order[1])
    elif order[0]=='check':
        if order[1] in S:
            print(1)
        else:
            print(0)
    elif order[0]=='toggle':
        if order[1] in S:
            S.remove(order[1])
        else:
            S.append(order[1])
    elif order[0]=='all':
        S=[]
        for i in range(1,21):
            S.append(str(i))
    elif order[0]=='empty':
        S=[]

 

 

2) 시간 초과

 

import sys
input=sys.stdin.readline

S=set()
N=int(input())
for _ in range(N):
    order=input().strip().split()
    if len(order)==1:
        if order[0]=='all':
            S=set([str(i) for i in range(1,21)])
        else:
            S=set()
        continue
    else:
        order, value = order[0], order[1]
        value=int(value)

        if order=='add':
            S.add(value)
        elif order=='remove':
            if value in S:
                S.discard(order[1])
        elif order=='check':
            print(1 if value in S else 0)
        elif order=='toggle':
            if value in S:
                S.discard(value)
            else:
                S.add(value)

 

3) 시간 초과

 

import sys
input=sys.stdin.readline

S=set()

for _ in range(int(input())):
    order=input().strip().split()
    if len(order)==1:
        if order[0]=='all':
            S=set([str(i) for i in range(1,21)])
        else:
            S=set()
        continue
    
    order, value = order[0], order[1]
    value=int(value)

    if order=='add':
        S.add(value)
    elif order=='remove':
        if value in S:
            S.discard(order[1])
    elif order=='check':
        print(1 if value in S else 0)
    elif order=='toggle':
        if value in S:
            S.discard(value)
        else:
            S.add(value)

 

 

4) 시간초과

 

import sys
input=sys.stdin.readline

S=set()

for _ in range(int(input())):
    order=input().split()
    if len(order)==1:
        if order[0]=='all':
            S=set([str(i) for i in range(1,21)])
        else:
            S=set()
    else:
        if order[0]=='add':
            S.add(order[1])
        elif order[0]=='remove':
            if order[1] in S:
                S.discard(order[1])
        elif order[0]=='check':
            if order[1] in S:
                print(1)
            else:
                print(0)
        elif order[0]=='toggle':
            if order[1] in S:
                S.discard(order[1])
            else:
                S.add(order[1])
        elif order[0]=='all':
            S=set([str(i) for i in range(1,21)])
        elif order[0]=='empty':
            S=set()

 

 

 

https://mong9data.tistory.com/91

[백준 알고리즘][파이썬/Python] 11723번: 집합

 

처음 시간초과가 나고 이 분 블로그를 참고하면서 계속 코드를 조금씩 고쳤는데 결국 코드가 다 똑같아 질때까지 시간초과가 발생하였다..

 

 

일단 시간초과를 줄일 수 있는 방법은

 

 

1. 리스트 말고 Set() 을 사용, 또한 append, remove 대신 add, discard 사용

 

2. if else 문을 통해 all 이랑 empty 를 빠르게 구분해주고, continue를 통해 다음 for 루프를 돌게 해준다.

 

3. 나는 처음에 str 선언으로 문자형으로 만들어 줬었는데 이거 또한 시간에 지장을 줬다. 

 

 

 

 

 

 

 

------------------------------------------------------------------------------------------------------------------------------

정답

 

 

 

 

 

 

import sys
input=sys.stdin.readline

S=set()

for _ in range(int(input())):
    order=input().strip().split()
    if len(order)==1:
        if order[0]=='all':
            S=set([i for i in range(1,21)])
        else:
            S=set()
        continue
    
    order, value = order[0], order[1]
    value=int(value)

    if order=='add':
        S.add(value)
    elif order=='remove':
        if value in S:
            S.discard(value)
    elif order=='check':
        print(1 if value in S else 0)
    elif order=='toggle':
        if value in S:
            S.discard(value)
        else:
            S.add(value)