[백준/파이썬] 10815. 숫자 카드 풀이

🔗 문제 링크

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

10815번: 숫자 카드

 

  상근이가 가진 숫자 카드와 새로 주어진 숫자 카드를 비교해서 새로 주어진 숫자 카드들을 상근이가 가지고 있는지 구하는 문제이다. 문제를 풀고 구글링 해보니까 대부분 이분 탐색으로 풀었는데, 나는 단순 탐색으로 풀었다.

 

 

---

🔎 문제 풀이 & 작성 코드

  숫자 카드가 중복되지 않는다는 특징을 이용해서, 단순하게 카드의 범위 전체에 대한 리스트를 생성했다. 원래 카드는 -10,000,000부터 10,000,000까지의 범위를 갖는데, 리스트의 인덱스를 활용하기 위해서 0~20,000,000의 범위를 갖는 리스트를 생성한 후 모두 0으로 선언해 두었다. 가지고 있는 숫자 카드에 대해서는 해당 인덱스의 0을 1로 다시 바꾸어 주었다. 그다음 새로 주어진 숫자 카드들에 대해서는, 각 인덱스마다 0인지 1인지를 확인해서 소지하고 있는지 아닌지 구분해 주었다. 

 

  아무래도 전체 범위로 리스트를 선언해 두었기에, 정말 큰 범위가 주어지면 메모리를 낭비하는 꼴이 될 것이다. 그래서 이런 접근이랑 가장 흡사하면서도 메모리를 효율적으로 쓸 수 있는 방법은 딕셔너리인 것 같다! 가지고 있는 숫자 카드를 딕셔너리로 저장해 두고 탐색하게 된다면 될 것이다. 

import sys

answer=[]
cards=[0]*20000000

N = int(sys.stdin.readline())
for i in list(map(int, sys.stdin.readline().split())):
    cards[i+10000000]=1
    
M = int(sys.stdin.readline())
for j in list(map(int, sys.stdin.readline().split())):
    if cards[j+10000000]==1:
        print(1, end=" ")
    else:
        print(0, end=" ")

 

 

 

---

🌍 깃허브 링크

실제 작성한 해당 정답 코드는 깃허브에도 업로드해두었습니다.

dohyun-99 - Overview