[Problem Solving] 집합과 맵 백준 예제/Python

해당 게시글은 비전공자이자 쌩초보 개발자 지망생이 작성한 글로 정확하지 않을 수 있으니 참고해주시길 바랍니다! 

피드백과 정보 정정 댓글은 환영입니다 :)

 

Python에서 집합은 set() 키워드로 구현할 수 있다! 우리가 알고 있는 집합과 동일하게 중복을 허용하지 않는다. 또한 순서가 없기 때문에 인덱스로 접근할 수 없다. set 키워드는 손쉽게 교집합, 합집합, 차집합, 대칭차집합 등을 구할 수 있기에 유용하며, 중복이 허용되지 않는 입력이 주어졌을 때 리스트보다 시간복잡도가 적기 때문에 효율성 측면에서도 유용하게 쓰일 수 있다. 

# 교집합
s1 & s2
s1.intersection(s2)

# 합집합
s1 | s2
s1.union(s2)

#차집합
s1 - s2
s1.difference(s2)

 

또한 해당 백준의 단계에서 유용하게 쓰이는 키워드로 dict() 가 있다. 해시를 파이썬에서 구현하는 방법으로 효율성과 리스트와 비교하였을 때 추가적인 기능을 수행할 수 있다. 딕셔너리는 key와 value로 이루어져 있고 모양은 다음과 같다.

animals_name = {'Dog' : '바둑이', 'Cat' : '나비'}

 

 

이제 이러한 개념들을 염두에 두고 문제들을 풀어보자!

 

#백준 10815 숫자카드2 Python3

import sys

N = int(sys.stdin.readline())
cards = set(map(int, sys.stdin.readline().split())) # 중요!

M = int(sys.stdin.readline())
given = tuple(map(int, sys.stdin.readline().split())) # 중요!

# in 메서드
for i in given:
    if i in cards:
        print('1', end = ' ')
    else:
        print('0', end = ' ')

#백준 10815 숫자카드2 Python3

해당 문제에서 눈여겨보아야 할 점은 입력을 받는 cards와 given의 자료형을 각각 set과 tuple로 지정한 점이다. list를 사용하게 되면 시간초과가 나기 때문에 각 요소에 접근할 때 시간복잡도가 리스트에 비해 적은 set과 tuple을 사용해야 한다!

 

# 백준 14425 문자열 집합 Python3

import sys

N, M = map(int, sys.stdin.readline().split())
S = [0] * N
cnt = 0

for i in range(N):
    S[i] = sys.stdin.readline().strip()

S = set(S) #집합 자료형을 사용하여 이후 in 메서드를 사용할 때 시간 단축

for j in range(M):
    if sys.stdin.readline().strip() in S:
        cnt = cnt + 1

print(cnt)

# 백준 14425 문자열 집합 Python3

 

# 백준 1620 나는야 포켓몬 마스터 이다솜 Python3

import sys

N, M = map(int, sys.stdin.readline().split())
pokemon = dict() # 딕셔너리 사용

for i in range(1,N+1):
    name = sys.stdin.readline().strip()
    pokemon[i] = name
    pokemon[name] = i

for i in range(M):
    given = sys.stdin.readline().strip()
    
    try: #입력이 숫자로 주어졌을 때
        given = int(given)   
        print(pokemon[given])
        
    except: #입력이 문자로 주어졌을 때
        print(pokemon[given])

# 백준 1620 나는야 포켓몬 마스터 이다솜 Python3

해당 문제 또한 딕셔너리를 사용하여 입력으로 주어진 값에 해당하는 답을 빠르게 찾아낼 수 있다. 대신, 입력이 이름으로 주어질지, 숫자로 주어질지 모르기 때문에 처음 가지고 있는 포켓몬을 입력 받을 때 {이름: 번호}, {번호: 이름} 이 두 가지 형식을 모두 딕셔너리에 추가시켜야 한다. 또한, 이후 try, except 문을 통해 입력이 문자로 주어졌을 때 try 에서 에러가 나면 except 문으로 넘어가 결과값을 출력하게끔 코드를 작성하였다.

 

# 백준 10816 숫자 카드 2

import sys

N = int(sys.stdin.readline())
cards = tuple(map(int, sys.stdin.readline().split()))
cards_dict = dict()

for i in range(N):
    num = cards[i] 
    try:
        cards_dict[num] = cards_dict[num] + 1 # key 가 딕셔너리에 있는 경우
    except:
        cards_dict[num] = 1 # key가 딕셔너리에 없는 경우

M = int(sys.stdin.readline())
given = tuple(map(int, sys.stdin.readline().split()))

for i in range(M):
    try:
        print(cards_dict[given[i]], end = ' ')
    except:
        print(0, end=' ')

# 백준 10816 숫자 카드 2

해당 문제도 try와 except 문을 적절히 사용해주어 코드를 (나름대로) 간결하게 작성해보았다! 카드의 수를 직접 count 메서드를 활용하여 센다면 시간초과가 날 것 같아 딕셔너리를 사용하였다. {카드 넘버: 카드 개수}의 구조를 사용하였고, 이미 있는 key(카드 넘버)라면 value에 1을 더하게끔, 그렇지 않고 에러가 나면 (key가 없는 경우) 초기값을 1로 설정하여 key를 추가해주었다. 마찬가지로 결과를 출력할 때에도 비슷한 논리를 활용하여 코드를 작성하였다!

 

# 백준 1764 듣보잡 Python3

import sys

N, M = map(int, sys.stdin.readline().split())
listen = set()
see = set()

for i in range(N):
    listen.add(sys.stdin.readline().strip())

for i in range(M):
    see.add(sys.stdin.readline().strip())

listen_and_see = sorted(list(listen&see))

print(len(listen_and_see))
for i in listen_and_see:
    print(i)

# 백준 1764 듣보잡 Python3

문제 이름이 제법 재밌는 문제였다! ㅋㅋㅋ 처음에는 틀렸습니다가 떠서 당황했는데, 문제 조건에서 '사전순으로 정렬' 하라는 말을 보지 못해 그런 것이었다. 코드 논리는 굉장히 간단했다. Python에서 제공하는 교집합 연산자를 활용하면 되는 문제!

 

# 백준 1269 대칭 차집합 Python3

import sys

a, b = map(int, sys.stdin.readline().split())
A = set(map(int, sys.stdin.readline().split()))
B = set(map(int, sys.stdin.readline().split()))

print(len(A^B))

# 백준 1269 대칭 차집합 Python3

해당 문제의 논리도 굉장히 간단하다! Python에서 제공하는 대칭 차집합 연산자 (^) 를 사용하면 되는 문제이다.

 

# 백준 11478 서로 다른 부분 문자열의 개수

import sys

S = sys.stdin.readline().strip()
s = set()

for i in range(1, len(S)+1):
    for j in range(len(S)-i+1): #이중 for 문
        s.add(S[j:j+i])

print(len(s))

# 백준 11478 서로 다른 부분 문자열의 개수

개인적으로 해당 문제는 set의 활용보다는 이중 for문에서 range 값을 어떻게 설정하는지에 더 초점이 쏠린 문제라는 생각이 들었다. 'abcdc' 라는 총길이가 5인 문자가 주어졌을 때, 한 글자만으로 만들 수 있는 부분 문자열의 개수는 5-0 = 5개, 두글자로 만들 수 있는 부분 문자열의 개수는 5-1 = 4개 ... (이하 생략) 이다. 이를 고려하여 range 값의 범위를 조정하면 수월하게 풀 수 있는 문제이다.

 

 

느낀 점

해당 단계는 몇개월 전에 풀었던 문제로 복습 차원에서 다시 풀어본 문제들이 대부분이었다. 그래도 많이 성장했다고 느낀 것이 

엄청난 시간 절약 ㅋㅋㅋㅋㅋ

정말 깜짝 놀랐다. 예전 코드를 보니까 왜 저렇게 썼는지 이해가 안됐다...ㅋㅋㅋㅋㅋ 분명 내가 작성한 코드임에도 불구하고... 7개월 전의 나는 바보였던 것일까? ㅎㅎ 아무튼, 지난 일주일 동안 너무 신나게 놀아버려서 위기감을 느끼고 다시 공부 모드로 돌입중이다... 앞으로는 꼬박꼬박 공부를... 해보겠다.. 아자잣!