집합과 맵 - 백준 10815, 1620 파이썬 풀이

이번 챕터는 집합과 정렬을 통해 빠른 성능으로 목적을 이루는 챕터였다.

성능에 관해 여러 난관을 봉착했는데 그 중에 크게 배운 게 이분탐색이다.

그리고 어떻게 하면 코드를 더 간결하게 쓸 수 있을까 고민하며 문제를 풀어나갔다.

몇 문제만 리뷰하고 마무리하겠다!

 

http://acmicpc.net/problem/10815

10815번: 숫자 카드

문제 :

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 

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

 

위와 같은 문제였는데 카드의 갯수 범위가 100,000이였다.

처음엔 그냥 갯수만큼 입력받아서 if in구문으로 풀었는데 당연히 시간초과가 발생했다....ㅎ

그래서 문제를 탐색해봤더니 이분탐색이라는 방법으로 효율적으로 풀 수 있었다.

 

이분 탐색이란 원본 data를 오름차순으로 먼저 정렬해놓는다.

그 다음 내가 찾으려고 하는 숫자와 data의 middle index값을 비교하여

찾으려는 숫자가 더 크다면 중간에서부터 오른쪽으로, 작다면 중간에서부터 왼쪽으로 찾아나가는 방법이다.

이 방법을 사용하면 가장 큰 숫자를 찾기 위해 index 0번부터 탐색하는 수고스러움을 덜 수 있다.

 

사용한 코드는 아래와 같다.

a = int(input())                        #data갯 수
alist = list(map(int,input().split()))	#data list
target = int(input())					#target 갯 수
tlist = list(map(int,input().split()))	#target list
alist.sort()	#이분탐색을 위한 data 오름차순 정렬
result = []		#정답을 담을 배열

for i in range(target) :
    lt = 0								
    rt = a-1
    while lt <= rt :			#left와 right인데 lt가 rt보다 작다는 뜻은 탐색할 것이 남았다는 뜻이다.
        mid = (lt + rt) // 2	#중간 index
        if alist[mid] < tlist[i] :	#중간값(alist[mid])보다 target숫자 i가 더 크면 left시작점을 중간보다 1 큰 값을 대입한다.
            lt = mid + 1
        elif alist[mid] > tlist[i] :##중간값(alist[mid])보다 target숫자 i가 더 작다면 right시작점을 중간보다 1 큰 값을 대입한다.
            rt = mid - 1
        else :			#else는 alist[mid]와 target num이 같음을 의미한다
            result.append('1')	#alist에 targetNum이 있으므로 1을 result에 추가
            break				
    if lt > rt :	#만약 left값이 right를 넘어섰다면 존재 하지 않음을 의미하므로 result에 0추가
        result.append('0')
print(' '.join(result))	#result list를 한 줄에 ' '을 간격으로 출력

코드와 함께 주석으로 해석을 적었으니 참고하시기를...

그리고 나중에 안 내용인데 print하는 쪽에 *list를 하면 한 줄에 한 칸씩 띄어쓰기로 출력된다...

 

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

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

이 문제는 내용이 아주 상당한데... 간단하게 설명하자면 도감이라는 영문으로 이루어진 Data가 있다.

그리고 비교 대상 data가 있는데 data는 index(숫자)이거나 영문일 수 있는데,

index라면 해당하는 영문을 출력하고 영문이라면 index를 출력하면 된다.

 

n,m = map(int,input().split())
book = [input().lower() for _ in range(n)]
target = []
for _ in range(m) :
    a = input()
    try :
        if int(a) + 1 > 0 :
            target.append(int(a))
    except :
        target.append(a)

for i in target :
    if type(a) == int :
        print(book[a-1])
    else :
        idx = book.index(i)
        print(idx)

처음에 작성한 코드이다.

book이라는 리스트에 data를 먼저 저장해놓았다.

그리고 input이 영문이나 숫자일 수 있으므로 try except로 숫자연산이 되면 숫자임을 판단하고 target에 숫자로 넣어주었다

그리고 except라면 문자열 그대로 넣어주었다.

target을 순회하면서 숫자라면 book에 index를 의미하므로 해당 index에 해당하는 값을 출력하고

문자열이라면 index를 출력해야하므로 list.index()를 활용해서 숫자를 출력했지만 당연히 실패했다..

원인은 당연히 시간초과였다.. 난 조금더 효율적이고 빠른 연산을 실행하는 코드를 찾아나섰다.

 

구글링으로 찾은 해답은 dict와 isdigit()함수였다.

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
graph = {}
for i in range(1,n+1) : #입력으로 들어오는 숫자는 1부터 시작하므로 똑같이 1을 더해줬다.
    a = input().strip() #sys.stdin.readline은 '\n'을 포함하므로 strip()으로 공백을 제거했다.
    graph[a] = i		#입력이 숫자이거나 문자열일 수 있으므로 해당하는 키와 value를 둘 다 넣어주었다.
    graph[i] = a		#이 부분이 문제 해결의 핵심이다.
for _ in range(m) :		#출력에 필요한 갯수만큼 순회
    target = input().strip() #공백제거
    if target.isdigit() :	#입력받은 값이 True라면 숫자만 존재함을 의미함
        print(graph[int(target)])	#int로 변환 후 key로 사용해서 문자 value출력
    else :
        print(graph[target])		#문자열을 입력받았으므로 key를 사용해 숫자 value 출력

이렇게 하면 훨씬 간결하고 쉽게 해결할 수 있다.

 

코딩테스트를 풀면서 내장함수나 문제해결 능력을 점차 향상시켜가는 느낌이다.

실버3~5에 해당하는 문제들이지만 안풀리면 1시간넘게 붙잡고 있을 때도 있다...

그래도 혼자 충분히 생각해보고 질문게시판 내용을 참고해서 내 코드로 다시 작성해보면 풀리는 뿌듯함이 있다!