Study / Algorithm4 minutes read (About 629 words)

백준 10815번 숫자 카드


백준 10815번 숫자 카드

내가 푼 코드 시간 초과!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def exsitCard(card, my_card):
    checked_card = my_card
    while(True):
        if len(checked_card) == 1:
            return 1 if card == checked_card[0] else 0
        elif len(checked_card) < 1:
            return 0
        else:
            center_num = len(checked_card)//2 
            if card == checked_card[center_num]:
                return 1
            elif card < checked_card[center_num]:
                checked_card = checked_card[:center_num]
            elif card > checked_card[center_num]:
                checked_card = checked_card[center_num+1:]


num1 = int(input())
my_card = list(map(int, input().split()))
my_card.sort()

num2 = int(input())
card_list = list(map(int, input().split()))

for card in card_list:
    print(exsitCard(card,my_card))

정답

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import sys
def existCard(card, checked_card):
    start_idx = 0
    end_idx = len(checked_card) - 1
    while(start_idx <= end_idx):
        idx = (start_idx + end_idx) //2
        if card == checked_card[idx]:
            return "1"
        elif card < checked_card[idx]:
            end_idx = idx -1
        else:
            start_idx = idx + 1
    return 0


num1 = int(input())
my_card = list(map(int, sys.stdin.readline().split()))
my_card.sort()

num2 = int(input())
card_list = list(map(int, sys.stdin.readline().split()))

result = []
for card in card_list:
    result.append(existCard(card,my_card))

print(" ".join(result))

시간 초과 발생한 이유는, idx가 아닌 배열 자체를 잘랐기 때문에! 배열 자체를 반 씩 자르고 저장하고 이래서 시간 초과가 발생했다.
이진 탐색을 할 때에는 배열은 그대로 두고 인덱스를 바꿔가면서 찾도록 하자!
while은 true말고 조건을 달아주자! 이번의 경우는 start_idx는 계속 늘어나고 end_idx는 계속 줄어드니까 + end_idx가 무조건 같거나 커야하므로 start_idx ≤ end_idx로 설정

idx에 +1, -1을 하는 이유는, idx가 반복되는 일을 방지하기 위해서다.
idx가 될 수 있는 수는 start_idx보다 크거나 같은 경우인데
idx가 start_idx보다 큰 경우, idx가 start_idx보다 제일 작은 1만큼 더 크다고 했을 때, idx+1을 하게 되면 2차이가 나므로 나누기 2를 하면, 이전 idx와 항상 다르게 된다.

idx가 start_idx와 같은 경우, (start,end,idx)라고 할 때 (2, 2, 2)나 (2, 3, 2)를 예로 들어보자.
(2, 2, 2)의 경우, idx+1을 만나면 (3,2,2)가 되어 start > end가 되므로 while이 끝나 버린다. idx-1을 만나도 마찬가지이다. 그리고 (2, 3, 2)의 경우, idx+1을 만나면 (3,3,2)가 되어 idx가 바뀐다. idx-1을 만나면 (2, 1, 2)가 되어 while이 끝나 버린다!
계속 이어서 end_idx = idx-1도 살펴보면, idx가 될 수 있는 수는 idx와 같거나 작은 수인데,
idx가 end_idx보다 작은 경우, idx - 1을 하면 최소 2이상의 차이가 나므로 이전 idx와 항상 다르게 된다.
idx가 end_idx와 같은 경우, (2, 2, 2)가 있는데 idx-1을 하면 while이 끝나 버린다.

Comments

×