상남자 되는 길

상남자의 TIL

import sys

input = sys.stdin.readline

N, x = map(int, input().split())
data = list(map(int, input().split()))

def count(data, target):
     leftIndex = leftBinarySearch(data, target, 0, N-1)
     if leftIndex == None:
          return 0
     rightIndex = rightBinarySearch(data, target, 0, N-1)
     return rightIndex - leftIndex + 1

def leftBinarySearch(data, target, start, end):
     if start > end: # 끝까지 했는데 안나온 경우
          return None
     
     mid = (start + end) // 2
     if (mid == 0 or data[mid - 1] < target) and data[mid] == target: # 가장 왼쪽에 해당하는 것만 찾기
          return mid
     elif data[mid] >= target:
          return leftBinarySearch(data, target, start, mid -1)
     else:
          return leftBinarySearch(data, target, mid + 1, end)

def rightBinarySearch(data, target, start, end):
     if start > end: # 끝까지 했는데 안나온 경우
          return None
     
     mid = (start + end) // 2
     if (mid == N - 1 or target < data[mid + 1]) and data[mid] == target: # 가장 오른쪽에 해당하는 것만 찾기
          return mid
     elif data[mid] > target:
          return rightBinarySearch(data, target, start, mid -1)
     else:
          return rightBinarySearch(data, target, mid + 1, end)

answer = count(data, x)
print(answer if answer != 0 else -1)

해당 문제는 이진 탐색을 이용해서 찾고자하는 값이 몇개나 존재하는지 체크하는 코드다.

나는 가장 구현하기 어려웠던 부분은 이 부분이다

if (mid == 0 or data[mid - 1] < target) and data[mid] == target: # 가장 왼쪽에 해당하는 것만 찾기
.
.
.
if (mid == N - 1 or target < data[mid + 1]) and data[mid] == target: # 가장 오른쪽에 해당하는 것만 찾기

왜냐하면 target을 찾고, target보다 작은 값 또는 큰값만 주면 된다고 생각했는데 mid == 0 or mid = N - 1은 생각하지도 못했다.

추가로 다른 이야기이지만, 현재 잡플레닛, 원티드까지 이력서를 작성해 놓은 상태이다. 일단 요번 주말까지 빠르게 잡플레닛, 원티드, 프로그래머스, 인텔리픽, 로켓펀치에 이력서를 작성을 해야겠다.

그리고 그 다음에 포트폴리오를 깔끔하게 작성해야 겠다.

상남자 스케줄 표

상남자 스케줄

https://docs.google.com/spreadsheets/d/1WLdEADCg1MdYhyplaXwOi_udwoeD1AjqvyBLAc0A5D4/edit#gid=0

상남자 노션

https://www.notion.so/42b9367fa8054114b8a7b02f5c104b25