해커를 꿈꾸는 개발자

파이썬 / BOJ 백준 / 10816 숫자 카드 2- Dictionary

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

문제

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

문제 풀이

1. Dictionary를 이용하여 쉽게 풀 수 있는 문제입니다.

2. 해당 주소에 값이 있으면, 그 값에 +1을 해줍니다.

3. 해당 주소에 값이 없으면, 값을 추가합니다.

전체 코드

import sys

n = int(sys.stdin.readline().strip())
n_list = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline().strip())
m_list = list(map(int, sys.stdin.readline().split()))

d = dict()
for i in n_list:
    if i in d.keys():
        d[i] += 1
    else:
        d[i] = 1

for i in m_list:
    if i in d.keys():
        print(d[i], end=' ')
    else:
        print(0, end=' ')

파이썬 / BOJ 백준 / 1920 수 찾기 - 이분 탐색

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

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

문제 풀이

1. 이 문제는 이분 탐색 알고리즘을 이용하여 풀 수 있는 문제입니다.
(하나씩 순차적으로 찾게 되면 시간초과가 됩니다.)

2. 우선 입력된 배열 N을 정렬시킵니다.

3. 시작과 끝 지점을 각각 left와 right로 놓고, 중간 지점을 mid로 놓습니다.

4. mid에 위치한 값과 비교하여,
 4-1. 동일한 값이면, 1을 반환합니다.

 4-2. 값이 크면 left를 mid + 1로 놓고, 다시 검색합니다.

 4-3. 값이 작으면 right를 mid -1로 놓고, 다시 검색합니다.

 4-4. 원하는 값이 없으면, 즉 left 값이 right 값보다 크면 0을 반환합니다.

전체 코드

from sys import stdin

n = stdin.readline()
N = sorted(map(int,stdin.readline().split()))
m = stdin.readline()
M = map(int, stdin.readline().split())

def binary(value, left, right):
    print(value, left, right)
    if left > right:
        return 0
    mid = (left+right)//2
    if value == N[mid]:
        return 1
    elif value < N[mid]:
        return binary(value, left, mid-1)
    else:
        return binary(value, mid+1, right)

for v in M:
    left = 0
    right = len(N)-1
    print("v 입니다.")
    print(binary(v,left,right))