Baekjoon 11273번 집합

문제

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

걸린 시간

01 : 23 : 39

풀이

Python3

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    M = int(input())

    # 0 : None, 1 : exist
    s = [0]*21
    result = []
    count = 0

    for _ in range(0, M):
        tmp = input().strip().split()
        command = tmp[0]
        if len(tmp) > 1:
            value = int(tmp[1])
            if command == "add":
                s[value] = 1
            elif command == "remove":
                s[value] = 0
            elif command == "check":
                if len(result) == 0:
                    result.append([s[value], 1])
                else:
                    if result[count][0] != s[value]:
                        count += 1
                        result.append([s[value], 1])
                    else:
                        result[count][1] += 1
            elif command == "toggle":
                if s[value]:
                    s[value] = 0
                else:
                    s[value] = 1
        else:
            if command == "all":
                s = [1]*21
            elif command == "empty":
                s = [0]*21

    for i in result:
        for j in range(0, i[1]):
            print(i[0])

메모리와 시간 모두 초과과 나서 수정하는데 시간이 조금 걸린 문제이다.

수행해야 하는 연산의 개수가 최대 3,000,000개이므로 출력 결과를 모두 리스트에 추가한다면 메모리 초과가 발생한다. 출력이 0과 1로만 이루어져 있다는 점을 이용해 출력 결과가 달라지지 않으면 해당 출력을 개수로 저장하는 방법을 이용하여 해결했다.

시간 초과 문제를 해결하기 위해서는 all 과 empty 연산에서 for 문을 사용하지 않고 집합 리스트를 각각 1, 0 값으로 다시 초기화해주면 된다. 물론 다른 곳에서 불필요한 연산을 최대한 제거해 주면 for 문을 사용하더라도 통과하기는 한다.