인프런 영문 브랜드 로고
인프런 영문 브랜드 로고

인프런 커뮤니티 질문&답변

신성찬님의 프로필 이미지
신성찬

작성한 질문수

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)

1. 이분 검색

이분검색 질문있습니다.

작성

·

258

2

만약 리스트가 [1, 2, 2, 2, 3] 으로 주어진다면 즉 중복 값이 있는 리스트가 존재하면 이 방법으로 2의 위치는 3이 됩니다.

만약  중복일 경우 가장 빠른 값의 위치를 반환하라고 하면

 어떤식으로 우회하여 실제 답을 찾을수 있을까요?

답변 2

0

안녕하세요. 파이썬 리스트에서 값이랑 자리수 같이 반환하는 함수가 있었던 것 같은데 그걸로 이용하면 안되나요??

0

김태원님의 프로필 이미지
김태원
지식공유자

문제 설명이 디테일 하지 못했습니다. 중복값은 존재하지 않는다라고 문제에 설명해 놓겠습니다.

물어보신 것 처럼 중복값이 있을 때 가장 빠른 값의 위치를 반환하려면 이분 검색을 하면서 답을 찾았을 때 멈추지 말고 답을 계속 갱신하면서 범위를 앞쪽으로 좁혀가면 됩니다.  

아래는 질문하신 답을 찾는 코드입니다. 

n, m=map(int, input().split())
a=list(map(int, input().split()))
a.sort()
lt=0
rt=n-1
while lt<=rt:
    mid=(lt+rt)//2
    if a[mid]==m:
        res=mid+1
        rt=mid-1
    elif a[mid]>m:
        rt=mid-1
    else:
        lt=mid+1
print(res)

신성찬님의 프로필 이미지
신성찬

작성한 질문수

질문하기