꾸준히 문제 풀기 - 9월 1, 2주차

9/1. 이항 계수 1 (백준 11050번)

 

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

 

#python

import sys

def fact(num) :
    ans = 1
    for i in range(1, num+1) :
        ans *= i

    return ans

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

ans = fact(n) / (fact(k) * fact(n-k))

print(int(ans))

 

저번에 풀었던 문제이지만 저번에 풀 때는 함수를 만들어서 하지 않았기 때문에, 이번에는 함수를 만들어서 활용하는 방법으로 풀어봤다. (정답)

 

---

 

9/3. 카드2 (백준 2164번)

 

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

 

#python

import sys
from collections import deque

n = int(sys.stdin.readline())
deq = deque()

for i in range(1, n+1) :
    deq.append(i)

while len(deq) != 1 :
    deq.popleft()
    deq.append(deq.popleft())

print(deq.popleft())

 

예전에 EC.crew에서 봤던 문제이다. 그 때는 어려워서 못 풀었던 것 같은데, 최근에 배운 덱 클래스를 쓰니까 쉽게 해결할 수 있었다. 이것이 자료구조의 중요성!! (정답)

 

---

 

9/6. 숫자 카드 2 (백준 10816번)

 

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

 

#python

import sys

n = int(sys.stdin.readline())
sang = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
card = list(map(int, sys.stdin.readline().split()))

for i in range(0, m) :
    count = 0
    
    for j in range(0, n) :
        if card[i] == sang[j] :
            count += 1
    
    print(count, end = " ")

 

첫번째 풀이. 당연히 시간 초과... (오답)

 

알고리즘에 이진탐색이라고 적혀있었어서 검색해봤다. linear search(순차검색)는 가장 쉽게 생각할 수 있는 순서대로 찾는 방법이다. 이는 정렬 방식이 상관 없다. binary search(이진 탐색)는 반드시 정렬된 상태에서 시작해야 하지만, 로그실행시간을 보장한다. (시간복잡도 O(logN)) 암튼.. 이 문제 풀겠다고 이진 탐색 공부하고 구현하는 것까지 해본 상태에서 풀어보려고 하니까... 주어진 카드를 정렬하는 것도 이상하고... (왜냐면 정렬하고 나면 출력할 때 원래 카드의 순서대로 출력해야 해서 복잡해진다.) 상근이의 카드를 정렬해도 이진 탐색은 인덱스값만 반환하므로 수정을 많이 해야하는데... 뭔가 이상해서 찾아보니 다들 이진 탐색은 사실상 필요가 없고 딕셔너리를 활용하면 쉽게 풀 수 있다고 한다. (찾아본 결과, 이 문제의 풀이법은 정말 다양했다. 해쉬맵 사용, counter 사용 등등... 이진 탐색을 활용한 풀이도 있고...) 아무튼 다시 딕셔너리를 공부하고 풀어봤다. 

 

#python

import sys

n = int(sys.stdin.readline())
sang = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
card = list(map(int, sys.stdin.readline().split()))

count = {}

for i in sang:
    if i in count:
        count[i] += 1
    else:
        count[i] = 1
    
for i in card:
    if i in count:
        print(count[i], end = " ")
    else:
        print(0, end = " ")

 

두번째 풀이. 딕셔너리로 풀었더니 풀이도 간단하고 시간 초과 없이 문제를 풀 수 있었다. (정답)

 

#python

import sys

def binary_search(target, data, start, end):
    if start > end:
        return None

    mid = (start + end) // 2

    if data[mid] == target:
        return mid
    elif data[mid] > target:
        end = mid - 1
    else:
        start = mid + 1
    
    return binary_search(target, data, start, end)

n = int(sys.stdin.readline())
sang = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
card = list(map(int, sys.stdin.readline().split()))

sang.sort()

for i in range(0, m):
    index = binary_search(card[i], sang, 0, n-1)
    count = 0

    if index != None:
        count = 1

        temp = index - 1
        while temp >= 0:
            if card[i] == sang[temp]:
                count += 1
                temp -= 1
            else:
                break

        temp = index + 1
        while temp < n:
            if card[i] == sang[temp]:
                count += 1
                temp += 1
            else:
                break
    
    print(count, end = " ")

 

세번째 풀이. 이진 탐색에 대한 미련을 버리지 못하고... 열심히 공부했으니까 활용해서 풀고 싶었다 ㅠㅅㅠ. 알고리즘 분류에 적혀 있기도 했고... 값을 찾았으면 앞뒤로 돌아다니며 같은 값이 몇개인지 세어서 출력하도록 짰다. 하지만 이 또한 시간 초과... ㅂㄷㅂㄷ (오답)

 

#python

import sys
from bisect import bisect_right, bisect_left

n = int(sys.stdin.readline())
sang = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
card = list(map(int, sys.stdin.readline().split()))

sang.sort()

for i in range(0, m):
    count = bisect_right(sang, card[i]) - bisect_left(sang, card[i])
    print(count, end = " ")

 

네번째 풀이이자 마지막 풀이..!! 바로 파이썬에 내장된 이진 탐색 모듈 bisect를 활용한 방법. bisect_left(list, value)는 list에서 value가 들어갈 가장 왼쪽 인덱스를, bisect_right(list, value)는 list에서 value가 들어갈 가장 오른쪽 인덱스를 반환한다. 그래서 bisect_right에서 bisect_left를 빼면 value의 개수가 나온다. (정답) 근데 이것보다 딕셔너리를 활용한 풀이가 더 빠르긴 하다. (거의 2배 차이..??)