[실버 V] 11723번. 집합

 문제 

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

11723번: 집합

 사용 언어 

Python3

 풀이 과정 

set() 함수를 이용해 나름 쉽게 풀었다고 생각했는데 두둥...! 처음 보는 메모리 초과;

import sys

S = set() # 비어있는 공집합
result = [] # check만 출력

def program(input):
  global S
  operator = input[0]
  if len(input) == 2:
    number = int(input[1])
  if(operator == 'add'):
    S.add(number)
  elif(operator == 'remove'):
    S.discard(number) # remove는 없으면 에러, discard는 없으면 pass
  elif(operator == 'check'):
    if(number in S):
      result.append(1)
    else:
      result.append(0)
  elif(operator == 'toggle'):
    if(number in S):
      S.remove(number)
    else:
      S.add(number)
  elif(operator == 'all'):
    S = set(range(1, 21))
  elif(operator == 'empty'):
    S = set()

M = int(sys.stdin.readline())
for _ in range(M):
  input = sys.stdin.readline().strip().split(' ')
  program(input)

print(*result, sep='\n')

알고리즘 문제에서 모든 출력을 배열에 담으면 메모리 초과가 날 확률이 높아진다고 한다...

출력은 가능한 한 바로바로 하는걸로!

그래서 함수도 없애고 결과 리스트도 지우고 if문 도는 횟수도 줄이고 all과 empty 연산에 각각 update와 clear 명령어를 사용하도록 수정했다. 그런데 다른 사람들 코드랑 비교해보니 if문 도는 횟수를 줄인 것이 가장 큰 효과를 준다고 한다.

 

그리고 파이썬은 내부적으로 연산과 메모리를 관리하기 때문에 파이썬에 내장되어있는 함수들을 적용할수록 메모리를 효율적으로 관리할 수 있다고 한다. 내장함수 쓰면 원리 이해하는데 방해된다고 생각했는데(물론 열심히 편한 함수 찾아보지만) 좋은 점도 있구나!

어찌저찌 구글링까지 해가며 힘들게 본 맞았습니다!!

실버치고 쉬운 문제인줄 알았는데 역시.. 공간 복잡도를 처음으로 생각해보게 한 문제였다.

 제출 답안 

import sys

S = set() # 비어있는 공집합
set = list(range(1, 21)) # update할 set

M = int(sys.stdin.readline())
for _ in range(M):
  input = sys.stdin.readline().strip().split(' ') # strip 꼭 해야 함!
  op = input[0]
  if len(input) == 1:
    if(op == 'all'):
      S.update(set)
    elif(op == 'empty'):
      S.clear()
      
  else:
    num = int(input[1])
    if(op == 'add'):
      S.add(num)
    elif(op == 'remove'):
      S.discard(num) # remove는 없으면 에러, discard는 없으면 패스
    elif(op == 'check'):
      if(num in S):
        print(1)
      else:
        print(0)
    elif(op == 'toggle'):
      if(num in S):
        S.remove(num)
      else:
        S.add(num)

 공부한 내용 

집합 연산자 set()

기본적으로 set은 집합 연산자이기 때문에 중복값은 제거된다. 각 메서드의 예제는 출처를 참고하도록.

- set.add : 요소 추가

- set. update : 요소 여러개 추가

- set.remove : 특정 요소 제거, 내부에 값이 없으면 오류

- set.discard : 특정 요소 제거, 내부에 값이 없으면 아무일도 일어나지 않음

- set.pop : 임의의 요소를 반환하고 제거

- set.clear : 모든 요소 제거, 비어있는 집합이 됨

- value in set : 내부에 요소가 있는지 확인

- len(set) : 집합의 길이(요소 개수) 확인

출처: https://blockdmask.tistory.com/451

파이썬 메모리 관리와 효율적인 코드

자세한 원리와 예제는 아래 출처의 velog를 확인하면 좋을 것 같고 나는 메모리 효율적인 파이썬 코드의 모범사례를 대충 정리해보겠다.

 

1. 리스트 원소를 출력할 때 join하기

2. 문자열에 + 연산자 피하기

3. 제너레이터(Generator) 사용하기

생성기를 사용하면 한 번에 모든 항목이 아닌 한 번에 하나의 항목을 반환하는 함수를 만들 수 있다. 즉, 데이터 집합이 큰 경우 전체 데이터 집합에 액세스 할 때까지 기다릴 필요가 없다.

4. (전역 변수보다) 지역 변수에 함수 할당하기

파이썬은 전역 변수보다 훨씬 효율적으로 지역 변수에 액세스한다. 지역 변수에 함수를 할당 한 다음 사용하는 것이 좋다.

5. 내장 함수와 라이브러리 사용하기

파이썬은 내부적으로 연산과 메모리를 관리하기 때문에 파이썬에 내장되어있는 함수들을 적용할수록 메모리를 효율적으로 관리할 수 있다.

6. itertools를 사용하여 원치 않는 루프 제거

7. 안전 및 메모리 관리를 위해 new 덮어 쓰기 및 메타 클래스 활용

 

+) 대부분의 프로그래밍 언어가 느려지는 경우는 메모리가 재할당이 이뤄지기 때문이다. 그리고 주로 for 문에서 이런 일이 생긴다. map() 함수를 사용하면 파이썬 내부적으로 연산과 메모리를 관리하기 때문에 효율적으로 모든 요소에 함수를 적용할 수 있다. (lambda 예약어를 함께 사용하면 좋다)

 

출처: https://wikidocs.net/21057 | https://velog.io/@swhan9404/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EB%A9%94%EB%AA%A8%EB%A6%AC-%EA%B4%80%EB%A6%AC%EA%B3%BC-%ED%9A%A8%EC%9C%A8%EC%A0%81%EC%9D%B8-%EC%BD%94%EB%93%9C

python 프로그램 메모리 사용량 확인

메모리 사용량이 궁금해서 찾아보니 아래 코드를 사용하면 사용량을 출력할 수 있었다.사용하기 위해서는 psutil을 import 해야 하고 python과 별도로 미리 설치를 해줘야 한다.

''' 모듈 설치 명령어 아래 둘 중 하나
python -m pip install --upgrade pip
python -m pip install psutil
'''

import psutil
def memory_usage(message: str = 'debug'):
    # current process RAM usage
    p = psutil.Process()
    rss = p.memory_info().rss / 2 ** 20 # Bytes to MB
    print(f"[{message}] memory usage: {rss: 10.5f} MB")

 

출처: https://jybaek.tistory.com/895

 다른 사람 답안 

메모리 사용을 더 줄인 답안이 있을 것 같아 찾아보았다.

import sys

N = int(sys.stdin.readline())
S = [False] * 21
for i in range(N):
    order = sys.stdin.readline().strip().split()
    if len(order) == 1:
        if order[0] == 'all':
            S = [False] + [True]*20
        else:
            S = [False] * 21
    else:
        order, x = order[0], int(order[1])
        if order == 'add':
            S[x] = True
        elif order == 'remove':
            S[x] = False
        elif order == 'check':
            if S[x]:
                print(1)
            else:
                print(0)
        elif order == 'toggle':
            if S[x]:
                S[x] = False
            else:
                S[x] = True

출처: https://maeng2world.tistory.com/170

 

숫자가 1~21로 작기 때문에 boolean 값을 사용하셨다고 했는데 제출해보니 실행 결과는 나의 코드랑 비슷했다.

다만 boolean을 사용한 게 신기해서 이런 방법도 있다는 걸 알아둬야겠다. 어떤 값이 들어있냐보다 문제에서 요구한 게 check로 있는지 여부만 확인하기 때문에 가능한 듯 하다.