[algorithm] 백준 단계별 문제 풀이 (집합과 맵 1탄)

[algorithm] 백준 단계별 문제 풀이 (집합과 맵 1탄)

 

안녕하세요. 심심한 코딩쟁이입니다.
 
오늘은 집합과 맵을 주제로 하는 문제들로 구성해 보았습니다.
 
파이썬3 를 사용해 문제 풀이를 진행하겠습니다.
 
문제마다 링크를 걸어두었으니 문제를 살펴보시고 문제를 푼 다음에 저와
 
풀이를 비교해 보시는 걸 추천드립니다.

차근차근 풀어봅시다.

 

알고리즘

---

백준 BAEKJOON 10815

 

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

 

10815번: 숫자 카드

 

문제 해석

 

문제에서 처음에 주어지는 숫자들이 가지고있는 숫자이고

두 번째로 주어지는 숫자들은 가지고있는 숫자들에 포함되어있는 지를 검사할 숫자들이다.

포함되어있다면 1을 출력 그렇지 않다면 0을 출력하는 문제이다.

시간 제한이 있기에 빠르게 처리할 전략이 필요하다.

 

풀이

 

import sys

n = int(sys.stdin.readline())
list1 = sorted(list(map(int, sys.stdin.readline().split())))
m = int(sys.stdin.readline())
list2 = list(map(int, sys.stdin.readline().split()))

for i in list2:
    start, end = 0, n-1
    flag = 0
    
    while start <= end:
        mid = (start+end) // 2
        if list1[mid] > i:
            end = mid -1
        elif list1[mid] < i:
            start = mid + 1
        else:
            flag = 1
            break
    print(flag, end = " ")

 

풀이 해석 및 팁

 

첫 번째로 주어지는 숫자들을 map 함수를 이용해 공백을 기준으로 구분한 뒤에 리스트로 형변환을 합니다.

그리고 형변환을 한 리스트를 sorted 함수로 오름차순으로 정렬시켜주면 가지고있는 숫자의 정렬이 완료됩니다.

다음으로 주어지는 숫자들이 가지고있는 숫자 리스트에 포함되어있나를 확인할 때 전수조사를 해버리면

시간제한에 걸리기 때문에 이진탐색으로 숫자를 가지고있는지 판별하는 검사를 진행합니다.

우리가 첫 번째로 주어지는 숫자들을 정렬시킨 이유는 바로 이진탐색을 하기 위해서였습니다.

---

백준 BAEKJOON 14425

 

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

 

14425번: 문자열 집합

 

문제 해석 

 

주어지는 문자열의 개수는 N + M 개로 차례대로 N개의 줄이 입력되고 나머지 M개의 줄도 입력된다.

모두 입력받은 뒤에 M개의 문자열 중 몇 개가 N개의 문자열에 포함되어있는지 출력하는 문제이다.

 

풀이

 

import sys

n, m = map(int, sys.stdin.readline().split())
list1 = []
count = 0
for _ in range(n):
    list1.append(sys.stdin.readline())

for _ in range(m):
    if sys.stdin.readline() in list1:
        count += 1

print(count)

 

풀이 해석 및 팁

 

처음에 주어지는 N개의 문자열을 리스트에 저장한 다음 M개의 문자열이 입력될 때 마다 문자열 리스트에

포함되어있는지를 판별해 count 변수의 수를 하나씩 늘려주는 방식으로 문제를 해결했습니다.

---

백준 BAEKJOON 1620

 

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

 

1620번: 나는야 포켓몬 마스터 이다솜

 

문제 해석

 

첫 번째 줄에 숫자 2개가 입력되는데 도감에 적혀있는 포켓몬 이름의 수와 시험 문제의 개수가 각각 입력됩니다.

포켓몬 이름의 수만큼의 줄이 입력되고 그 뒤로는 입력되는 문자열이 숫자일 때는 도감에서 숫자번째의

포켓몬 이름을 찾아 출력하고 알파벳일 때는 도감에서 해당 포켓몬의 순번을 출력하면 되는 문제입니다.

 

풀이

 

import sys
n, m = map(int, sys.stdin.readline().split())

names = {}
nums = {}
for i in range(1, n+1):
    tmp = sys.stdin.readline().rstrip()
    nums[i] = tmp
    names[tmp] = i

for _ in range(m):
    tmp = sys.stdin.readline().rstrip()
    if tmp.isdigit():
        print(nums[int(tmp)])
    else:
        print(names[tmp])

 

풀이 해석 및 팁

 

포켓몬의 이름을 Key로 가질 딕셔너리와 도감 번호를 Key로 가질 딕셔너리를 각각 정의하고 입력값을 받으면서

해당 딕셔너리에 알맞게 요소들을 채워나갑니다.

시험 문제인 문자열의 입력이 들어올 때 부터는 해당 문자열이 숫자인지 아닌지를 검사하기위해 isdigit() 함수를

사용하고 숫자일 경우에는 숫자를 키로 가진 딕셔너리에서 값을 찾고 알파벳일ㄹ 경우에는 이름을 키로 가진

딕셔너리에서 값을 찾아 출력하면 문제가 해결됩니다.

확실히 딕셔너리를 사용하는게 리스트를 사용하는것 보다 시간이 제한되어있을 경우 유리한 것 같습니다.

---

여기까지 백준 단계별 문제 풀이 집합과 맵 1탄의 풀이였습니다.

 

궁금하신 점이나 도움이 필요하신 부분이 있다면 댓글로 남겨주세요.

 

감사합니다.