[이분탐색] 백준 10816 - 파이썬

 

의식의 흐름 알고리즘은 문제를 보고 내가 첨에 든 생각들을 끄적인거라 틀린 알고리즘임.

답만 알고 싶다면 최종 알고리즘이나 정답코드만 보면 된다.

 

함께 코테 연습 해봐요!!!

 

백준 10816.

의식의 흐름 알고리즘

10815문제와 다른 점은 몇개 가지고 있는지 구하는 것이다.

사실 그 문제는 한개 찾으면 바로 함수 탈출하면 그만인데 이건 개수를 다 구해야함.

그래도 정렬해놓고 시작할거니까 값이 같을 때 앞뒤로 체크만 하면 되지 않을까 한다.

 

시간 초과가 날 것 같긴하지만? 일단 생각한대로 풀어본다.

 

틀린답 (시간초과 30%대)

def numbercard():
    n = int(input())
    nCards = list(map(int, sys.stdin.readline().split()))
    nCards.sort()

    res = []
    m = int(input())
    mCards = list(map(int, sys.stdin.readline().split()))

    start, end = 0, n-1
    def Binary(start, end, i):
        nonlocal cnt
        cnt = 0
        while start <= end:
            mid = (start+end) // 2
            if nCards[mid] == i:
                fix = mid
                cnt += 1

                for _ in range(fix):
                    mid -= 1
                    if nCards[mid] == i:
                        cnt +=1
                    else:
                        break
                mid = fix
                for _ in range(n-fix-1):
                    mid += 1
                    if nCards[mid] == i:
                        cnt +=1
                    else:
                        break
                return
            elif nCards[mid] > i:
                end = mid-1
            else :
                start = mid+1
        return

    cnt = 0

    for i in mCards:
        Binary(start, end, i)
        res.append(cnt)

    print(*res)

 

생각보다 오래 통과해서 오~~?? 했는데 역시는 역시다.

모든 숫자가 다 똑같다고 가정하면 시간초과가 날 수 밖에 없는 구조..

 

어떻게 해야 시간을 줄일 수 있을까.. 어떻게 조건문을 짜야 할까.....

 

 

 

 

최종 알고리즘

여러가지 방식으로 풀 수 있는데 나도 한번 생각 했던 방법 중 하나는 이건 처음 이 문제 풀 때도 했던 생각인데 딕셔너리를 쓰는 거다.

최초 주어진 카드들을 조회해서 dictionary에 담는데 dic[카드값] : 개수 로 담는거지.

dic[6] = 1, dic[3] = 2, dic[2] 1= , dic[10] =3, dic[-10]=2, dic[7]= 3

그렇게하고 mCards들의 숫자에 맞는 값을 출력하면 된다. 이건 솔직히 너무 쉽긴한데 실제로 말이 되기는 함.

n = int(input())
nCards = list(map(int, sys.stdin.readline().split()))
nCards.sort()

m = int(input())
mCards = list(map(int, sys.stdin.readline().split()))
dic = dict()

for i in nCards:
    if i in dic:
        dic[i] += 1
    else:
        dic[i] = 1

for i in range(m):
    if mCards[i] in dic:
        print(dic[mCards[i]], end=' ')
    else:
        print(0, end=' ')

 

위에서 딕셔너리로 일일이 받는 방법말고 이미 파이썬에서 자체제공하고 있는 파이썬 라이브러리가 있다.

바로 Counter...

n = int(input())
nCards = list(map(int, sys.stdin.readline().split()))
nCards.sort()

res = []
m = int(input())
mCards = list(map(int, sys.stdin.readline().split()))

c = Counter(nCards)

for i in mCards:
    if i in c:
        print(c[i], end = ' ')
    else:
        print(0, end=' ')

 

이렇게 Counter(list)를 하면 딕셔너리 형태로 알아서 반환해준다.