99클럽(3기) - 코테스터디 5일차 TIL # 이분탐색

프로그래머스 - 10815. 숫자 카드

1. 문제 설명

 정수 M개의 수에 대해서 각각 상근이가 가지고 있는 숫자 카드 N개에 포함되어 있으면 1, 아니면 0을 공백으로 구분해 출력한다. 

첫째 줄에 상근이 가지고 있는 숫자 카드 개수 N개가 주어지고, 둘째 줄에 상근이가 가지고 있는 숫자 카드에 적힌 정수들이 공백을 두고 주어지고, 셋째 줄에 정수 M이 주어지고, 넷째 줄에는 공백을 두고 M개의 정수가 주어진다. 

 

2.  제한 사항

• 1 <= N <= 500,000
• 1 <= M <= 500,000
• 10,000,000 <= 숫자 카드에 적혀있는 수 <= 10,000,000

 

3. 입출력 예

 

---

 

4. 첫 번째 풀이 - Python

1) 4줄의 입력을 처리한다. 

4줄에 걸쳐 정수 N, N개의 숫자들, 정수 M, M개의 숫자들을 입력받는다. ns 생성에 O(N), ms 생성에 O(M)의 시간복잡도가 소요된다. 

 

2) N개의 숫자들(ns)은 set 자료형으로 만든다.

ms의 요소들이 ns에 있는지 판별해야하기 때문에 탐색의 대상은 ns이다. list는 탐색 시간이 O(N)이고, set은 해시테이블을 기반으로 하기 때문에 탐색 시간이 O(1)이다. 따라서 ns를 set 자료형으로 만든다. 

 

3) M개의 숫자들에 대해서 각각 N개의 숫자들에 포함되어있는지 판단한 결과를 출력

answer에 리스트 컴프리헨션으로 ms의 요소가 ns에 있으면 1을, 아니면 0을 담는다. ns를 탐색하는 시간은 O(1)이고 ms는 모든 요소를 다 탐색해야해서 O(M)의 시간복잡도가 소요되므로 answer 생성에 소요되는 시간복잡도는 총 O(M)이다. 그 후 answer의 각 요소를 문자열로 변환 후 공백 기준으로 join하여 출력한다. 여기서 주의할 점은 join 메소드는 문자열에만 사용할 수 있기 때문에 answer의 요소들을 꼭 문자열로 변환해줘야 한다는 것이다. 

 

🕰️ 최종 시간복잡도

• 상근이의 숫자 카드를 집합으로 변환: O(N)
• 확인할 숫자 카드를 리스트로 변환: O(M)
• 각 확인할 숫자가 집합에 있는지 검사: O(M)
• 결과 출력: O(M)

 

  ➡️ 모두 더하면 O(N + M)

N = int(input())
ns = set(map(int, input().split(" "))) # N개의 숫자들
M = int(input())
ms = list(map(int, input().split(" "))) # M개의 숫자들

answer = [1 if val in ns else 0 for val in ms]
print(" ".join(map(str, answer)))

 

 

5. 다른 사람의 풀이 - Python

파이썬 모듈 bisect를 이용한다. 위 풀이에서는 ns를 set 자료형으로 변환했다면, 해당 풀이에서는 이분탐색(bisect)을 사용하기 위해 sorted 메소드를 적용했다. bisect.bisect_left(정렬된 리스트, 값)은 리스트 내부에서 값을 찾으면 해당 값의 '가장 왼쪽 인덱스'를 반환한다. 만약 리스트 내부에 값이 없다면 해당 값을 삽입해도 여전히 정렬 상태를 유지할 수 있는 인덱스를 반환한다. 

 

🕰️ 최종 시간복잡도

• 상근이의 숫자 카드를 입력받아(O(N)) 정렬(O(log N)): O(N log N)
• 확인할 숫자 카드를 리스트로 변환: O(M)
• 이분탐색(O(log N))을 M번 반복: O(M log N)
• 결과 출력: O(M)

 

  ➡️ 모두 더하면 O((N + M) log N)

import bisect

# 입력 받기
N = int(input())
ns = sorted(map(int, input().split()))
M = int(input())
ms = list(map(int, input().split()))

# 이분 탐색을 통해 각 ms의 값을 ns에서 찾기
for val in ms:
    # bisect_left로 val의 삽입 위치를 찾음
    index = bisect.bisect_left(ns, val)
    # index가 ns 길이 내에 있고, ns[index]가 val과 같은지 확인
    if index < N and ns[index] == val:
        print(1, end = " ")
    else:
        print(0, end = " ")

 

 

6. Java로 풀이

Java에는 bisect 대신 Arrays.binarySearch가 있다! 파라미터로 이분탐색을 할 리스트와 찾을 값을 전달하면 된다.  Arrays.binarySearch(정렬된 리스트, 값) 이렇게!

풀이 방식은 아래와 같다. 

import java.util.Arrays;
import java.util.Scanner;

pupblic class Main {
	public static void main(String[] args) {
    	Scanner scanner = new Scanner(System.in);
        
        // 입력 받기
        int N = scanner.nextInt();
        int[] ns = new int[N];
        for (int i = 0; i < N; i++) {
        	ns[i] = scanner.nextInt();
        }
        
        int M = scanner.nextInt();
        int[] ms = new int[M];
        for (int i = 0; i < M; i++) {
        	ms[i] = scanner.nextInt();
        }
        
        // 정렬
        Arrays.sort(ns);
        
        
       	// 결과 리스트 초기화
        int[] answer = new int[M];
        
        // 이분 탐색을 통해 각 ms의 값을 ns에서 찾기
        for (int i = 0; i < M; i++) {
        	int val = ms[i];
            if (Arrays.binarySearch(ns, val) >= 0) {
            	answer[i] = 1;
            } else {
            	answer[i] = 0;
            }
        }
        
        // 결과 출력
        for (int i = 0; i < M; i++) {
        	System.out.print(answer[i] + " ");
        }
    }
}

 

 

7. 문법 정리

• list 시간복잡도
  • 탐색: O(n)
  • 특정 위치에 삽입/삭제: O(n) → 삽입/삭제 후 나머지 요소들을 이동시켜야 하기 때문
  • 맨 마지막 위치에 삽입/삭제: O(1)
  • 인덱스 접근: O(1)

 

• set 시간복잡도
  • 탐색: O(1)
  • 삽입/삭제: O(1)

 

• 숫자 리스트의 요소들을 join 해서 출력하려면 먼저 문자열로 변환해야 함
  • join 메소드는 문자열에만 사용할 수 있기 때문! 
  • EX) print(" ".join(map(str, list)))

 

• Python - bisect 사용법
  • bisect.bisect_left(정렬된 리스트, 값)
    • 값을 찾으면 '가장 왼쪽 값의 인덱스' 반환
    • 못 찾으면 해당 값을 삽입했을 때 정렬을 유지할 수 있는 위치 반환
     
  • bisect.bisect_right(정렬된 리스트, 값)
    • 값을 찾으면 '가장 오른쪽 값의 인덱스  +1' 반환
    • 못 찾으면 해당 값을 삽입했을 때 정렬을 유지할 수 있는 위치 반환
     
  • bisect.bisect(정렬된 리스트, 값)
    • bisect.bisect_right()와 동일

 

• Java - Arrays.binarySearch 사용법
  • Arrays.binarySearch(정렬된 리스트, 값)
    • 값을 찾으면 해당 값의 인덱스 반환
    • 못 찾으면 해당 값을 삽입했을 때 정렬을 유지할 수 있는 위치의 음수값 반환