99클럽 코테 스터디 25일차 TIL + 백준 20551번 Sort 마스터 배지훈의 후계자(Python)

✔️오늘의 학습 키워드

• 이분탐색

• 백준 20551번 Sort 마스터 배지훈의 후계자

  
  

✔️ 공부한 내용

📌 오늘의 문제

📌 작성 코드

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
a=[int(input()) for _ in range(n)]
a.sort()
def bin_search(d):
    start,end=0,n-1
    while start<=end:
        mid=(start+end)//2
        if a[mid]<d:
            start=mid+1
        else:
            end=mid-1
    if start<n and a[start]==d:
        return start
    else:
        return -1
for _ in range(m):
    d=int(input())
    print(bin_search(d))

✔️ 오늘의 회고

📌 문제 및 시도 방법

처음엔 이분탐색 없이 그냥 풀었더니 시간 초과가 나왔다.

import sys
input=sys.stdin.readline
n,m=map(int,input().rstrip().split())
a=[input().rstrip() for _ in range(n)]
b=sorted(a,key=lambda x: x)
for _ in range(m):
    d=input().rstrip()
    print(b.index(d) if d in b else -1)

그래서 이분탐색 사용하여 푸는 방법으로 재시도 하였다.

📌 문제 해결 방법

1. n(배열 원소 수),m(질문 수) 입력
2. 배열 원소 n만큼 입력받은 후 정렬
3. 이분탐색
4. 질문 수 m만큼 d(정수) 입력받고 배열의 인덱스 출력, 없으면 -1 출력

📌 새롭게 안 내용

새롭게 안 개념은 없었다.

📌 내일 학습할 내용

내일의 알고리즘 문제를 풀어보고 이해하기

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL