lower bound와 upper bound에 대해 알아보세요.

lower bound와 upper bound에 대한 풀이는 알고있습니다. 그런데 그 배경지식을 모르는 상태에서 문제를 만났을때 풀 수 있는 방법이 있을 것 같은데 풀리지 않아서 여쭤봅니다.

지금과 같은 이분 탐색을 쓰는 방식이라면 그게 유일한 방법입니다. Lower/upper bound 풀이와 이 코드와의 유일한 차이점이 수가 같은 범위의 시작점/끝점을 루프로 한 칸씩 찾는 대신 이분 탐색으로 빠르게 찾는다는 것뿐이고, 다른 방법으로 푸는 건 이보다 덜 비슷할 수밖에 없습니다.

Upper/lower bound 풀이라는 게 꼭 라이브러리를 쓰라는 뜻이 아니고, 그 기능을 직접 구현하는 것이 "배경지식을 모르는 상태에서 문제를 만났을때 풀 수 있는 방법"에 해당합니다.

또한 check_card가 정렬되어있지 않기 때문에 33~47번째 줄과 같은 이분 탐색은 사용할 수 없습니다.

33-47 이 문제가 있는 것이 아닐까요?

이진탐색을 하려면 정렬이 되어 있어야 하는데 check_card 는 정렬이 안되어 있기 때문에 이전 질의한 결과를 다시 찾는 것이 정상 동작하지 않을 것이고, 

그러면 동일한 질문을 여러번 하면 오래 걸리지 않을까 합니다.

check_card도 정렬한 다음에 결과를 뽑고 (중복을 제거하고 해도 되고...)

출력시에 해당하는 결과를 찾아서 출력하는 것도 방법일 수 있을 것 같네요.

======================================

사실 이 문제는 수의 범위가 20,000,001 이라서 count 배열을 int 로 만들어도 80M 수준이기 때문에 각 숫자를 count 하고 

그 결과를 출력하는 것이 가장 빠른 해가 아닐까 합니다.