[백준] 10816번 숫자 카드2

www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

 

 

🔥첫 시도 (시간초과)

이분탐색을 하긴 하는데.. start와 end를 찾아서 end-start+1 해서 갯수를 세기로 함

근데 while 2개를 돌아서 시간 초과인것같다...ㅠㅠ 

# 10816번 : 숫자카드
def binary_search_10816():
  _ = int(input())
  N = list(map(int, input().split()))
    
  _ = int(input())
  M = list(map(int, input().split()))

  # N = [6, 3, 2, 10, 10, 10, -10, -10, 7, 3]
  # M = [10, 9, -5, 2, 3, 4, 5, -10]

            #   0   1   2  3  4  5  6  7   8   9
  N.sort() # [-10, -10, 2, 3, 3, 6, 7, 10, 10, 10]
  # print(N)

  setN = set(N)

  result_arr = []

  def find_start(s,e,m):
    start = 0
    while 1:
      c = (e+s) // 2

      if m == N[c] :
        if N[c-1] == N[c]:
          e = c - 1
        elif N[c-1] != N[c]:
          start = c
          break 
      elif m < N[c]:
        e = c - 1
      elif m > N[c]:
        s = c + 1

      if s > e:
        start = e
        break
    return start

  def find_end(s,e,m):
    end = 0
    while 1:
      c = (e+s) // 2

      if m == N[c] :
        if N[c+1] == N[c]:
          s = c + 1
        elif N[c+1] != N[c]:
          end = c
          break 
      elif m < N[c]:
        e = c - 1
      elif m > N[c]:
        s = c + 1

      if s >= e:
        end = e
        break
    return end

  for m in M:
    s = 0
    e = len(N)-1 
    # print(m)

    if m not in setN:
      result_arr.append(0)
      continue

    st = find_start(s,e,m)
    ed = find_end(s,e,m)

    result_arr.append(ed-st+1)
  print(' '.join(str(r) for r in result_arr))   

 

시간초과

 

 

🔥두번째 시도 (시간초과)

위에서 조금만 고쳐서(거의 같음) 또 시간초과ㅠㅠ 이분탐색 꼭 써야하나요 안쓸래ㅠㅠㅠㅠㅠㅠㅠㅠ

암튼 그래서 코드 안올림.. 비슷해서....

 

 

🔥세번째 시도 (통과ㅠㅠ)

근데 이분탐색을 버렸습니다 dict로 풀었어요... 

# 10816번 : 숫자카드 2트
def binary_search_10816_2():
  _ = int(input())
  N = list(map(int, input().split()))
    
  _ = int(input())
  M = list(map(int, input().split()))

  # N = [6, 2, 2, 2, 3, 2, 10, 10, 10, 10, 10, -10, -10, 7, 3]
  # M = [10, 9, -5, 2, 3, 4, 5, -10]

            #   0   1   2  3  4  5  6  7   8   9
  N.sort() # [-10, -10, 2, 3, 3, 6, 7, 10, 10, 10]
  # print(N)

  dictN = {}

  for n in N:
    if n in dictN:
      dictN[n] += 1
    else:
      dictN[n] = 1
  
  # print(dictN)
  
  for m in M:
    if m not in dictN:
      print(0, end=' ')
    else:
      print(dictN.get(m), end=' ')


binary_search_10816_2()