[파이썬] 4158 - CD

먼저, 문제부터 보자

이분 탐색이라는 원리를 조금이라도 더 몸에 익히고자

 

백준에서 이분 탐색으로 열심히 검색해서 풀다 나온 문제이다 

 

여느 문제와 같이 시작, 마지막 값을 만들고

 

mid값을 만든뒤 

 

중간부터 시작해서

 

차츰차츰 범위를 줄여가며

 

값을 찾는 이분 탐색

 

 

처음 짠 코드는 이렇다

 

import sys a, b = map(int, sys.stdin.readline().split()) ary1 = [int(sys.stdin.readline()) for _ in range(a)] ary2 = [int(sys.stdin.readline()) for _ in range(b)] ans = 0 for cd in ary2:     start, end = 0,  a-1     while start <= end:         mid = (start+end)//2         if ary1[mid] == cd:             ans +=1             break         elif ary1[mid]>cd:             end = mid -1         elif ary1[mid]<cd:             start = mid +1 print (ans)

예시를 넣고 돌리니 맞아서 백준에 바로 제출했다.. 근데 아니나 다를까 

 

아니 맞잖아 ;;

 

그 후로 여러 시도를 해보았다 

 

열심히 돌리다가

 

문제점을 알아냈고 틀린 직전 코드에 적용시켜보았다

 

그래도 장족의 발전이다 시간 초과가 떴다! 

import sys while (1):     a, b = map(int, sys.stdin.readline().split())     if a ==0 and b==0:         break     ary1 = [int(sys.stdin.readline()) for _ in range(a)]     ary2 = [int(sys.stdin.readline()) for _ in range(b)]     ans = 0     for i in ary1:         for p in ary2:             if str(p) in str(i) and str(i) in str(p):                 ans+=1                 break     print (ans)

이 문제를 풀다가 도저히 안 풀려서 왜 ???

 

이러면서 포기하고 그냥 배열끼리 비교하는 식을 짜서 시도하던 도중..

 

시간 초과라는 희망적인 문구를 본 것이다 

 

그리고 이유를 알아내었다

 

틀린 이유는 ..

 

문제에서 찾을 수 있었다

 

"입력은 여러 개의 테스트 케이스로 이루어져 있다"

 

처음 문제를 읽을 때는

 

'뭐.. 그렇지 예시에 숫자가 많으니..'

 

근데 그 뜻이 아니다 

 

진짜로 그 예시 자체가 여러 개가 있는 것이다

 

그리고 마지막에 0 0을 왜 주는지 몰랐다

 

여하튼 솔루션을 깨달았고

 

맨 처음 코드를 계속 돌리면

 

무조건 통과한다는 생각이 들어서

 

맨 위에 코드를 다시 들고 왔다 

 

 

 

import sys while (1):     a, b = map(int, sys.stdin.readline().split())     if a ==0 and b==0:         break     ary1 = [int(sys.stdin.readline()) for _ in range(a)]     ary2 = [int(sys.stdin.readline()) for _ in range(b)]     ans = 0     for cd in ary2:         start, end = 0,  a-1         while start <= end:             mid = (start+end)//2             if ary1[mid] == cd:                 ans +=1                 break             elif ary1[mid]>cd:                 end = mid -1             elif ary1[mid]<cd:                 start = mid +1     print (ans)

여느 때와 같은 이분 탐색 문제처럼

 

두 ary값을 for로 냅다 받아버리고

 

둘 다 있는지 없는지를 찾아야 한다

 

==

 

둘 중 그 누구가 대상이 되든 상관없다

 

고로 ary1을 대상으로, 시작 값과 마지막 값 설정해주고 

 

문제는 다 오름차순으로 들어온다 하였으니 sort는 없어도 무관

 

 

while문으로 이분 탐색 시작하고

 

ary[mid]값이 cd면 +1 하고

 

냅다 while문을 나와서 다음 cd값으로

 

만약 같지 않고  ary1[mid]가 크면

내가 찾고자 하는 값이 mid값 범위 안에 있으니 

마지막 값(end)을 mid로 바꿔서,

이미 mid값은 비교했으니 -1을 해서 while문을 다시 시작

 

또한 같지 않고 ary1[mid]가 작으면

mid값 범위 밖(오른쪽)에 있으니

이번에는 시작 값을 mid값으로 바꿔서,

또한 mid값은 비교했으니 +1을 해서 while문을 다시 시작

 

 

이렇게 for문에서 주는 cd값을 ary1에서

 

이분 탐색한 뒤 있다면 +1

 

없다면 넘기는 형식으로 쭉 넘겨준다

 

 

cd문제 기점으로 이분 탐색 문제를 좀 풀었다 생각했는데

 

아직도 이분 탐색 문제를 보면 뇌가 굳는다 

 

이제 mid값의 역할과 start와 end가 왜 mid로 변하는지는 알겠으나 

 

이걸 적용할 일머리가 없어서 그런 건가

 

아니면 내가 완벽하게 아직 이해를 못 한 건가 하면서.. 

 

그리고 위안으로는 아직 파이썬 시작한 지..

아니 프로그래밍 시작한지 한 달도 지나지 않았으니

아직 모르는 게 많아서 그런가 보다 생각하면서..

 

날잡고 또 이분 탐색 문제를 가져와서 풀어봐야겠다