230221 코딩 연습

백준 이분탐색 문제 1920 siver4 단계를 풀어보았다.

N = int(input())
A = list(map(int,input().split(' ')))
M = int(input())
target = list(map(int,input().split(' ')))


# 시간분석 N최대 100,000// M최대 100,000
# 시간 제한 1초 _>100,000,000

# 이분탐색

#  1. 정렬이 필수이다. A 정렬, target 정렬
#  sort()사용시 return 없음, list 바뀜!, sorted()사용시 list가 안바뀜
A.sort()

#  2. 정렬 후 mid값, start, end 찾기
#  target[i]를 A의 mid와 비교, 이후 mid값을 옮겨줌(start, end)


# print(A,target)
for j in target:
    start = 0
    end = len(A) - 1
    while True:
        # 반복문
        mid = (start + end) // 2
        # print(j,'J',A[mid],mid)
        if j == A[mid] :
            print(1)
            break
        elif start >= end  :
            print(0)
            break    
        elif j > A[mid] :
            start = mid + 1
        else :
            end = mid - 1

체크 할점, 1. .sort를  사용시 리턴 없이 바로 이전 리스트가 바뀜, sorted() 사용시 리턴으로 보여줌

2. while Ture: 안에 start>=end 쓰는 것 vs while 옆에 start<=end 주고 True, False로 밖에 꺼내는 방법

3. 2중 for문에서 break는 밖의 for문만 끝냄

 

백준 이분탐색 숫자찾기2

N = int(input())
card = list(map(int,input().split(' ')))
M = int(input())
target = list(map(int,input().split(' ')))

# N 개수 500,000, card 개수 10,000,000*2 
# 1초 100,000,000

# cardM을 sort 시켜서 이분탐색을 사용하자!
# counter쓰면 쉽게 풀 수 있을 것 같지만 알고리즘을 연습해보자
# dict으로 만들어서 count를 세고 target과 비교하자

# card 정렬
card.sort()
# 같은 개수 찾아서 dict에 넣기, dict 'number':'count'
newDict = {}
for i in card:
    if newDict.get(i):
        newDict[i] +=1
    else:
        newDict[i] = 1
# start, end, mid 구하기

# target을 쭉 탐색_> 하나씩 card를 이분탐색시키기

newList=[]

# target[n] 이 cardM에 있는지 체크
for i in target:
#   start,end 초기화
    start = 0
    end = M-1
    while True :
        mid = (start + end) // 2
        if i == card[mid]:
#           newDict[]= 이건 없으면 오류 있어서, .get() 이용
            newList.append(newDict.get(i))
            break
        elif start >= end :
            newList.append(0)
            
            break
        elif i > card[mid]:
            start = mid + 1
        else :
            end = mid - 1
for i in newList:
    print(i,end=' ')

1. dict으로 문제 풀기

2. if newDict.get(i): 이건 none으로 들어가서 오류 X, if newDict[i] 하면 error 발생

if i in newDict: 이렇게 써도 가능

3. append()로 하니까 시간이 아슬아슬 하던데 다른 방법 없을까?