[백준/python] 집합과 맵 전체 풀이(12단계)

 

목차

 

 

문제풀이를 하기 전에 이번 단계의 제목인 집합과 맵 그리고 이 단계가 시사하는 목적에 대해 요약하자면

 

지금까지는 리스트를 사용해도 시간이 오래 걸리지 않는 적은 수의 데이터를 다루었다면 앞으로는 데이터가 커지기 때문에 문제의 조건을 보고 상황에 맞게 집합 set이나 맵 (해시맵을 뜻함) dict 등을 사용하도록 한다. 따라서 숏코딩 보다는 이에 중점을 두어서 문제 풀이를 하겠다.

 

숫자 카드(#10815)

• Problem

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

 

• Hint

두개의 리스트를 만드는건 불가피하다. 집합과 리스트의 차이는 집합은 중복되는 인자를 가지지 않는다는 것이다. 

 

• Solution

집합을 이용한 풀이

import sys
input=sys.stdin.readline

sl=[]
sn=int(input())
for i in input().split():
    sl.append(i)

sl=set(sl)

l=[]
n=int(input())
for i in input().split():
    if i in sl:
        l.append('1')
    else:
        l.append('0')

print(*l)

리스트를 사용하는 경우 n개의 숫자카드에 써있는 숫자들이 m개의 숫자카드에 있는지를 비교할때 이때의 시간 복잡도는 O(n*m)이지만 만일 n개의 숫자카드에 적힌 숫자가 모두 같은 숫자이고 이를 집합을 이용해 비교하면 O(m)이 된다. 따라서 중복되는 숫자가 많을 수록 시간복잡도가 줄게되므로 집합을 사용하는 편이 좋다.

시간초과는 리스트를 사용하였고 위는 집합을 사용하였다.

---

 

문자열 집합(#14425)

• Problem

총 N개의 문자열로 이루어진 집합 S가 주어진다. 입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성하시오.

 

• Hint

집합의 개념에 대해서 잘 알아두고 문제를 잘 읽어야한다.

 

• Solution

집합의 성질을 이용한 풀이

import sys
input=sys.stdin.readline

n,m=map(int,input().split())
cnt=0
nl=[]
ml=[]

for i in range(n):
    nl.append(input().strip())
    
for i in range(m):
    ml.append(input().strip())

for i in ml:
    if i in nl:
        cnt+=1
print(cnt)

둘다 리스트에 저장을 해놓아도 결과값이 나온다 하지만 n의 경우에는 집합이라고 했으니 중복되는 값이 존재하지 않는다. 하지만 m 에는 중복이 되어도 상관없다 (여담으로 반대로 이해해서 국어의 굴레에 빠졌었다)

---

 

 

나는야 포켓몬 마스터 이다솜(#1620)

• Problem

첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 물어봐도 괜찮아. 나는 언제든지 질문에 답해줄 준비가 되어있어.

둘째 줄부터 N개의 줄에 포켓몬의 번호가 1번인 포켓몬부터 N번에 해당하는 포켓몬까지 한 줄에 하나씩 입력으로 들어와. 포켓몬의 이름은 모두 영어로만 이루어져있고, 또, 음... 첫 글자만 대문자이고, 나머지 문자는 소문자로만 이루어져 있어. 아참! 일부 포켓몬은 마지막 문자만 대문자일 수도 있어. 포켓몬 이름의 최대 길이는 20, 최소 길이는 2야. 그 다음 줄부터 총 M개의 줄에 내가 맞춰야하는 문제가 입력으로 들어와. 문제가 알파벳으로만 들어오면 포켓몬 번호를 말해야 하고, 숫자로만 들어오면, 포켓몬 번호에 해당하는 문자를 출력해야해. 입력으로 들어오는 숫자는 반드시 1보다 크거나 같고, N보다 작거나 같고, 입력으로 들어오는 문자는 반드시 도감에 있는 포켓몬의 이름만 주어져

 

• Hint

사전형을 두개 이용하여 보자

 

• Solution

사전형을 이용한 풀이

n,m = map(int,input().split())
pokedict={}
pokedictr={}
for i in range(n):
    a=input()
    pokedict[i+1]=a
    pokedictr[a]=i+1
result=[]
for i in range(m):
    result.append(input())

for i in result:
    try:
        print(pokedict[int(i)])
    except:
        print(pokedictr[i])

일단 try와 except으로 int 타입으로 변경하려고할때 에러가 나게되면 (str의 경우) 와 아닌경우로 나누었고 이후에 리스트형을 사용하여 .index를 이용해서 번호를 찾으려 했는데 시간초과가 뜨게 되었다. 따라서 pokedict와 저 사전이 반대로 저장되어있는 pokedictr를 만들어서 시간 복잡도를 줄여서 코딩을 하게 되었다.

 

딕셔너리의 경우에는 키와 결과값이 한개씩 짝지어져 있기 때문에 시간 복잡도가 O(1)이 된다.

---

 

숫자 카드 2(#10816)

• Problem

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

 

• Hint

마찬가지로 맵 dict을 이용하여 풀이하면 된다.

 

• Solution

dict() 사전형을 이용한 풀이

input()
ndict={}

for i in map(int,input().split()):
    if i in ndict:
        ndict[i]=int(ndict[i])+1
    else:
        ndict[i]=1

input()
res=[]

for j in map(int,input().split()):
    if j in ndict:
        res.append(ndict[j])
    else:
        res.append(int(0))

print(*res)

n개의 숫자 모임에 사전형을 적용하여 키가 기존에 저장되어있을때 if (key) in (dict) 는 value 값을 1을 추가해주고 아닌 경우에는 1로 초기 저장을 해주었다.

 

출력의 경우에는 키가 존재하지 않은 경우에는 0을 출력하고 존재할 경우에는 각 key에 맞는 value 값을 출력하도록 하였다.

---

 

 

듣보잡(#1764)

• Problem

김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.

 

• Hint

딕셔너리는 key로 찾는 것이기 때문에 빠르다 사전형으로 오름차순 정렬하는 것을 잊지말자

 

• Solution

dict을 이용한 풀이

import sys
input=sys.stdin.readline

n,m = map(int,input().split())
nl={}
res=[]
cnt=0

for i in range(n):
    nl[input().strip()]=1

for i in range(m):
    a = input().strip()
    if a in nl:
        cnt+=1
        res.append(a)

print(cnt)
print(*sorted(res),sep='\n')

dict가 속도는 가장 빠른것 같다.

---

 

대칭 차집합(#1269)

• Problem

자연수를 원소로 갖는 공집합이 아닌 두 집합 A와 B가 있다. 이때, 두 집합의 대칭 차집합의 원소의 개수를 출력하는 프로그램을 작성하시오. 두 집합 A와 B가 있을 때, (A-B)와 (B-A)의 합집합을 A와 B의 대칭 차집합이라고 한다. 예를 들어, A = { 1, 2, 4 } 이고, B = { 2, 3, 4, 5, 6 } 라고 할 때, A-B = { 1 } 이고, B-A = { 3, 5, 6 } 이므로, 대칭 차집합의 원소의 개수는 1 + 3 = 4개이다.

 

• Hint

수학적으로 접근을 먼저 하자

 

• Solution

dict 을 이용한 풀이

import sys
input=sys.stdin.readline

n,m = map(int,input().split())
nl={}
res=[]
cnt=0

for i in map(int,input().split()):
    nl[i]=1

for i in map(int,input().split()):
    if i in nl:
        cnt+=1

print(n+m-cnt*2)

수학적으로 생각해보면 대칭 차집합의 개수는 결국 A와 B의 원소의 합에서 둘의 합집합 원소의 2배를 뺀 개수와 같다는 사실을 알 수있다.

---

 

서로 다른 부분 문자열의 개수(#11478)

• Problem

문자열 S가 주어졌을 때, S의 서로 다른 부분 문자열의 개수를 구하는 프로그램을 작성하시오. 부분 문자열은 S에서 연속된 일부분을 말하며, 길이가 1보다 크거나 같아야 한다. 예를 들어, ababc의 부분 문자열은 a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc가 있고, 서로 다른것의 개수는 12개이다.

 

• Hint

부분 문자열을 만들 방법을 잘 생각해보자. 반복문을 2번 사용하면 쉽게 만들어낼수 있다.

 

• Solution

을 이용한 풀이

n = str(input().strip())
res=[]
a=[]

for i in n:
    res.append(i)
for j in range(len(n)):
    for i in range(len(n)-j):
        a.append("".join(res[i:i+j+1]))
print(len(set(a)))

반복문 두번으로

임의로 print를 통하여 출력하게 한 결과물

저 리스트를 뽑게되면 set을 통해 중복값을 없애주고 그 집합의 길이를 구하면 쉽게 해결 가능하다.