[BAEKJOON/Python] no.10815 숫자 카드 | 정렬

문제

---

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

10815번: 숫자 카드

 

 

1차 풀이

---

my_card_count = int(input())
card_list = list(map(int, input().split()))
number_count = int(input())
find_number = list(map(int, input().split()))

for number in find_number:
    if number in card_list:
        print(1, end=' ')
    else:
        print(0, end=' ')

👉🏻일단 되는대로 풀어봤다ㅋㅋㅋ 정렬을 도대체 어디에 써야할 지 모르겠어서..

역시 시간 초과ㅋㅋㅋㅋ

👉🏻근데 아무리 봐도 이진탬색 문제인 것 같아서 이진탐색으로 풀어보았다.

 

2차 풀이 : 이진탐색 활용

---

my_card_count = int(input())
card_list = list(map(int, input().split()))
number_count = int(input())
find_number = list(map(int, input().split()))

card_list.sort()

for number in find_number:
    start = 0
    end = my_card_count - 1
    find = False

    while start <= end:
        mid = (start + end) // 2
        if number < card_list[mid]:
            end = mid - 1
        elif number > card_list[mid]:
            start = mid + 1
        else: 
            print(1, end=' ')
            find = True
            break
    if find is False:
        print(0, end=' ')

👉🏻쨘 전체코드는 다음과 같다.

my_card_count = int(input())
card_list = list(map(int, input().split()))
number_count = int(input())
find_number = list(map(int, input().split()))

card_list.sort()

👉🏻문제에 사용할 값들을 변수에 저장했다. 그중 상근이가 가진 숫자카드 리스트인 card_list를 이진탐색을 활용하기 위해 정렬해주었다.

for number in find_number:
    start = 0
    end = my_card_count - 1
    find = False

    while start <= end:
        mid = (start + end) // 2
        if number < card_list[mid]:
            end = mid - 1
        elif number > card_list[mid]:
            start = mid + 1
        else: 
            print(1, end=' ')
            find = True
            break
    if find is False:
        print(0, end=' ')

👉🏻그리구 이진탐색 돌림!

👉🏻while에 break를 걸어주지 않으니 무한루프에 빠졌었다... 다들 조심!

👉🏻상근이가 숫자 카드를 가지고 있다면 find 변수를 True로 바꿔주고 while문을 빠져나갔다. 그렇게 하지 않으면 0을 모든 카드의 경우에 출력하기 때문이다.

 

🐰이진탐색 코드에 대한 자세한 내용은 아래 글을 확인!ㅎㅎ

2022.03.30 - [그 땐 Algorithm했지/그 땐 Python했지] - [TAVE/이코테] ch07 이진 탐색 | 개념 정리

[TAVE/이코테] ch07 이진 탐색 | 개념 정리