[백준, 파이썬, 4158번] CD

 

풀이

 

• 해당 문제는 집합, 이진 탐색 
• 두 방법으로 풀이가 가능하기에 각각 접근을 따로 해봤다.
• 그런데 해당 문제에서는 내가 시도한 이진 탐색 방식은 pypy 제출만 가능했어서 조금 아쉽...
• 집합은 둘 다 잘 나오는데....
• 무튼 집합 풀이
  • 단순히 입력 값들을 set() 메서드에 넣은 다음
  • intersection인 교집합을 조회한 뒤 개수를 출력하는 형식으로 간단하게 풀이
• 이진 탐색 풀이
  • 우선 n의 길이만큼 받아지는 입력 값을 li에 넣은 다음
  • m 길이 만큼 반복해서 해당 값을 find로 담은 뒤
  • 이진 탐색을 위한 시작과 끝 값을 0과 n-1값으로 하여
  • find 값을 li에서 찾도록 하기
  • 이후 이진 탐색 코드는 다른 이진 탐색 코드랑 유사할 것이기에 생략

 

집합 풀이

import sys

input = sys.stdin.readline

while True:

    n,m = map(int,input().split())

    if (n,m) != (0,0):

        _n,_m = set(),set()

        for _ in range(n): _n.add(int(input()))

        for _ in range(m): _m.add(int(input()))

        print(len(_n.intersection(_m)))

    else: break

 

이진 탐색 풀이

import sys

input = sys.stdin.readline

while True:

    n,m = map(int,input().split())

    if (n,m) != (0,0):

        cnt = 0

        li = [int(input()) for _ in range(n)] # 1 2 3

        for _ in range(m):

            find = int(input()) # 1 2 4

            s,e = 0,n-1

            while e>=s:

                mid = (s+e)//2

                if li[mid] == find:

                    cnt += 1

                    break

                elif li[mid] > find: e = mid-1

                else: s = mid+1

        print(cnt)

    else: break