99클럽 코테 스터디 14일차 TIL + 이분탐색

오늘의 문제 - 이분탐색

백준 10815번 - 숫자 카드2

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오

https://www.acmicpc.net/problem/10816

---

내 풀이 및 접근 방식

1. dic 이용 풀이

이분탐색이 주제이지만, 앞 선 숫자카드 문제에서 set을 이용했던 것이 생각나 같은 해시인 dic 풀이 방식이 가장 먼저 생각났다. dic을 이용해 상근이의 숫자 카드 개수를 저장하는 방식으로 풀이했다.

import sys

n = int(sys.stdin.readline())
n_cards = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
m_cards = list(map(int, sys.stdin.readline().split()))

n_cnts = {}	# 상근이 카드 숫자 개수 {카드 숫자: 카드 개수}
		
for nc in n_cards:	# 상근이 카드 순회하며 카드 숫자 개수 구하기
    if nc in n_cnts:
        n_cnts[nc] += 1
    else:
        n_cnts[nc] = 1

for mc in m_cards:	# 판별해야할 숫자 카드를 순회
    if mc in n_cnts:	# dic에 있는 경우, value 출력
        print(n_cnts[mc], end=' ')
    else:				# dic에 없는 경우, 0 출력
        print(0, end=' ')

 

시간 복잡도: O(n+m)

1. 상근이 카드 개수 세기: O(n)
2. 판별해야할 숫자 카드 개수 세기: O(m)

2. 이분 탐색 풀이

이전에 풀이했던 코드를 확인해보니 이분 탐색을 이용한 풀이였다. 아마도 내가 푼 것이 아니라 다른 사람 코드를 반영했을 확률 99%..확신. 아무튼 이것이 정석 풀이같다.

import sys

# 검색 값의 최소 인덱스 찾기
def firstIndex(list, n):
    start = 0
    end = len(list) - 1
    fi = -1                 # 못 찾았을 경우 -1

    while start <= end:
        mid = (start + end) // 2

        if n == list[mid]:
            fi = mid
            end = mid - 1   # 최소 인덱스 찾기 위함
        elif n > list[mid]:
            start = mid + 1
        else:
            end = mid - 1

    return fi

# 검색 값의 마지막 인덱스 찾기
def lastIndex(list, n):
    start = 0
    end = len(list) - 1
    li = -1                   # 못 찾았을 경우 -1

    while start <= end:
        mid = (start + end) // 2

        if n == list[mid]:
            li = mid
            start = mid + 1   # 최대 인덱스 찾기 위함
        elif n > list[mid]:
            start = mid + 1
        else:
            end = mid - 1

    return li

# 상근이가 가지고 있는 숫자 카드 개수
N = int(sys.stdin.readline())
# 상근이의 숫자 카드에 적혀있는 정수
NCard = list(map(int, sys.stdin.readline().split()))

# 상근이가 몇 개 가지고 있는지 구해야 할 정수 개수
M = int(input())
# 상근이가 몇 개 가지고 있는지 구해야 할 정수
MCard = list(map(int, sys.stdin.readline().split()))

NCard.sort()

result = []
for i in MCard:
    if firstIndex(NCard, i) != -1:
        result.append(lastIndex(NCard, i)-firstIndex(NCard, i)+1)
    else:
        result.append(0)

for i in result:
    print(i, end=" ")

 

풀이 방식

1. 상근이가 가진 카드를 정렬한다.
2. firstIndex 함수와 lastIndex 함수를 이용해 특정 숫자의 최소 인덱스와 최대 인덱스를 구한다.
3. 최대인덱스에서 최소인덱스를 제거하고 1을 더하며 특정 카드 숫자의 개수를 구한다.

여기서 핵심은 분기 firstIndex와 lastIndex에서 최소 최대 인덱스를 찾기 위한 분기처리같다.

최소 인덱스를 구하는 이분탐색에서는 숫자를 찾은 후 최소 인덱스를 구하기 위해 end=mid-1로 더 작은 범위를 탐색한다.

반면 최대 인덱스를 구하는 이분탐색에서는 최대 인덱스를 구하기 위해 start=mid+1을 통해 더 큰 범위를 탐색한다.

 

시간 복잡도: O((n+m)logn)

1. NCard.sort() 정렬: O(nlogn) (n: n_list 길이)
2. 최소, 최대 인덱스 찾는 이진 탐색 함수: O(logn)
3. m개의 카드 판별: O(mlogn)
   m개의 카드를 순회하며 이진 탐색 함수를 호출하므로 m*logn이다.
4. 결과 출력: O(m)

 

2개의 시간 복잡도를 비교했을 때,

n과 m이 크지 않거나 n이 매우 클 때는 첫 번째 코드가 효율적이다.

상근이의 카드 개수 n이 매우 큰 경우에는 이진 탐색 코드가 더 효율적이다. 라고 chatGPT가 말했다.

---

회고

정렬된 리스트에서 최소 인덱스와 최대 인덱스를 통해 숫자 개수 구하는 방법 기억하자~ 

 

이분 탐색 적용한 관련 문제 꼭 풀기

 

• 백준 1920. 수 찾기:
  • 문제 설명: N개의 정수가 주어지고, 이 안에 M개의 수가 있는지 확인하는 문제입니다.
  • 링크: 수 찾기
• 백준 2110. 공유기 설치:
  • 문제 설명: 주어진 집에 공유기를 설치할 때, 가장 인접한 두 공유기 사이의 거리를 최대화하는 문제입니다.
  • 링크: 공유기 설치