크래프톤 정글 TIL : 0706

팀 코드 리뷰

import sys
from collections import defaultdict

N = int(sys.stdin.readline().strip())
S = {sys.stdin.readline().strip() for _ in range(N)}
D = defaultdict(list)shootBox - (L-y) <= sorted_A[found + i][0] <= shootBox + L-y
이 조건문 통째로 변수 처리 할 수 있나?

L = sorted(S)
L.sort()
N = len(L)

for i, string in enumerate(L):
  D[len(string)].append(string)

for key in sorted(D.keys()):
    for string in D[key]:
        print(string)

• # input = sys.stdin.readline 으로 메서드 이름 줄일 수 있다
• L.sort() 필요 없었음
• enumerate 쓸 필요 없었는듯

배운 것들

리스트 컴프리헨션 안 쓰고 그냥 list() 해버린 오류

A = list(map(int, sys.stdin.readline().strip().split()) for _ in range(M))
아니 이거 왜 출력했더니
<map object at 0x78b44b5198a0>
이딴 식으로 뜨는거임

A = list(map(int, sys.stdin.readline().strip().split()) for _ in range(M))

이 코드는 map 객체의 리스트를 반환하지 않고, map 객체 자체를 요소로 갖는 리스트를 생성합니다.

A = [list(map(int, sys.stdin.readline().strip().split())) for _ in range(M)]

올바른 방법은 위와 같습니다.

리스트 컴프리헨션을 사용하여 각 입력 줄을 정수 리스트로 변환해야 합니다.

list(map(int, sys.stdin.readline().strip()))
이건 리스트 컴프리헨션 안 써도 출력하면 잘 나오던데

• list(map(int, sys.stdin.readline().strip()))는 문자열의 각 문자를 개별적으로 정수로 변환합니다.
• list(map(int, sys.stdin.readline().strip().split()))는 문자열을 공백으로 분할하여 각 부분을 정수로 변환합니다.
• 여러 줄의 입력을 2차원 리스트로 처리하려면 리스트 컴프리헨션을 사용하여 각 줄을 개별적으로 처리해야 합니다.

그냥 return만 띡 쓰면 return None이랑 똑같음?

네, return 문만 단독으로 쓰면 None을 반환하는 것과 같습니다. 이는 함수가 명시적으로 값을 반환하지 않을 때 파이썬이 기본적으로 None을 반환하는 것과 동일한 동작입니다.

변수 a에 None 넣어놨다가 1 넣어도 됨? 성능 문제 없음?

네, 변수에 None 값을 넣어놨다가 나중에 다른 값(예: 1)을 넣어도 성능 문제는 없습니다. 파이썬은 동적 타이핑 언어(dynamic typing language)이기 때문에, 변수의 타입을 변경하는 것이 자연스럽고 일반적인 프로그래밍 방식입니다.

리스트도 global 붙여줘야 함수 안에서 수정 가능함?

네, 파이썬에서 리스트를 함수 내에서 수정하려면 리스트가 전역 변수임을 명시적으로 선언해야 합니다. 이를 위해 global 키워드를 사용할 수 있습니다.

백준

2805 나무 자르기

import sys

S = list(map(int, sys.stdin.readline().strip().split()))
N = int(S[0]) # 나무의 수
M = int(S[1]) # 필요한 나무의 길이
T = list(map(int, sys.stdin.readline().strip().split())) # 나무들의 높이

# h만큼 벌목기 올렸을 때 얻는 나무의 양
def getTree(h):
  sum = 0
  for tree in T:
    if tree - h > 0:
      sum += tree - h
  return sum

start = 0
end = max(T)
mid = (start + end)//2

while start <= end:
  mid = (start+end)//2
  Get = getTree(mid)

  # print(start, end, mid, Get, M)

  if Get == M:
    break
  elif Get <= M:
    end = mid - 1
    mid = (start+end)//2
  else:
    start = mid + 1
    mid = (start+end)//2

print(mid)

이분 탐색 그대로 다시 구현하면 되는거라 어려울 것 없었다.
이분 탐색이라는 주제가 안 주어지고 그냥 하라고 했으면 좀 헤맸을수도.

  if Get == M:
    break
  elif Get <= M:
    end = mid - 1
  else:
    start = mid + 1

처음 제출할 때 mid를 업데이트 안 해서 '틀렸습니다!' 떴었음.

8983 사냥꾼

def findRange(range_s, range_e, somewhere, y):
  upLimit = -1
  downLimit = -1
  A_end = len(sorted_A)

  # 유효하지 않은 x좌표를 가진 동물에게 불시착했다면
  if not range_s <= sorted_A[somewhere][0] <= range_e:
    # 유효한 x좌표를 가진 무리를 전부 탐색할 때까지 위로 탐색
    for i in range(A_end - somewhere):
      # 무리를 만났었다면
      if downLimit != -1:
        # 다른 y 좌표를 가진 동물을 만났을 때 탐색 종료
        if sorted_A[somewhere+i][1] != y:
          upLimit = somewhere+i-1
          break
        # 유효하지 않은 x좌표를 가진 동물을 만났을 때 탐색 종료
        elif range_s <= sorted_A[somewhere+i][0] <= range_e:
          upLimit = somewhere+i-1
          break

      # 무리를 만난 적이 없다면
      else:
        # 유효한 x좌표를 가진 동물을 발견했을 때 하계 할당
        if range_s <= sorted_A[somewhere+i][0] <= range_e:
          downLimit = somewhere+i

      i += 1

  # 유효한 x좌표를 가진 동물에게 착륙했다면
  if sorted_A[somewhere+i][0] != y:
    # 무리를 만났었다면
    if downLimit != -1:
      # 다른 y 좌표를 가진 동물을 만났을 때 탐색 종료
      if sorted_A[somewhere+i][1] != y:
        upLimit = somewhere+i-1
        break
      # 유효하지 않은 x좌표를 가진 동물을 만났을 때 탐색 종료
      elif range_s <= sorted_A[somewhere+i][0] <= range_e:
        upLimit = somewhere+i-1
        break
    
    # 무리를 만난 적이 없다면
    else:
      

      # 
      if 

      # 무리를 처음 만났다면 시작
      if
        # 무리를 만나 시작점이 -1이 아니었다면 현재 인덱스-1 을 끝점으로 할당

    # 유효한 x좌표를 가진 무리를 전부 탐색할 때까지 아래로 탐색

하루종일 개같이 코드 짜다가
이쯤 와서는 뭔가 이상한 것 같다는 사실을 눈치채버림
다시 정신 차리고 풀어보려는데

import sys
input = sys.stdin.readline

S = list(map(int, input().strip().split()))
M = int(S[0]) # 사대의 수
N = int(S[1]) # 동물의 수
L = int(S[2]) # 사정거리
H = list(map(int, input().strip().split())) # 사대의 위치
A = [list(map(int, input().strip().split())) for _ in range(N)] # 동물의 위치
valid_A = [] # 사냥 가능할 수도 있는 동물 좌표들
sorted_A = [] # y좌표에 대해 정렬된 동물 좌표들
Shot = [] # 사냥할 수 있는 좌표

##### 동물 리스트 준비 #####

# 사정거리 이상의 Y좌표를 가지면 동물 자격 박탈
for animal in A:
  if animal[1] <= L:
    valid_A.append(animal)

# 동물의 위치를 y좌표에 대해, 그 후 x좌표에 대해 정렬
# [[5, 1], [7, 2], [2, 2], [3, 3], [1, 4], [8, 4], [9, 4], [4, 5]]
# l[0][0] = x좌표, l[0][1] = y좌표
sorted_A.append(valid_A[0])
for i in range(1,len(valid_A)): # 쏠 동물 좌표 순회
  for j in range(len(sorted_A)): # 정렬 리스트에 하나씩 넣으며 좌표 정렬
    s_x = sorted_A[j][0]
    s_y = sorted_A[j][1]
    v_x = valid_A[i][0]
    v_y = valid_A[i][1]

    if s_y == v_y and s_x > v_x:
      sorted_A.insert(j+1,valid_A[i])
      break
    elif s_y > v_y:
      sorted_A.insert(j,valid_A[i])
      break
    elif j == len(sorted_A)-1:
      sorted_A.append(valid_A[i])


##### 점의 개수 세기 ##### 

# y축 내려가면서
# 이분탐색으로 점 하나 찾은 후에
# 인덱스 위아래로 훑는다

# 같은 y좌표를 가진 동물이 어느 인덱스에 있는지 이진 탐색
def binarySearch(find):
  start = 0
  end = len(sorted_A)-1
  half = (start + end) // 2

  while start <= end:
    # 정중앙 인덱스를 확인하고
    # 중앙의 값과 같으면 그대로 반환
    if sorted_A[half][1] == find:
      return True, half

    # 중앙의 값보다 크면 end => half
    elif sorted_A[half][1] > find:
      end = half - 1
      half = (start + end) // 2

    # 작으면 start => half
    else:
      start = half + 1
      half = (start + end) // 2 

  return False, half



def scapeGoat(shootBox, found, y):
  global totalSum
  limit = len(sorted_A) - 1

  # 위로 탐색
  i=0
  inRange = shootBox - (L-y) <= sorted_A[found + i][0] <= shootBox + L-y
  notLimit = found + i < limit
  cond_1, cond_2, searchEnd = False, False, False

  while not searchEnd and notLimit:
    if inRange:
      cond_1 = True
      totalSum += 1
      del sorted_A[found+i]

    elif cond_1:
      cond_2 = True 

    if cond_1 and cond_2:
      serachEnd = True

    i+=1
  
  # 아래로 탐색
  i=0
  inRange = shootBox - (L-y) <= sorted_A[found - i][0] <= shootBox + L-y
  notLimit = 0 <= found + i
  cond_1, cond_2, searchEnd = False, False, False

  while not searchEnd and notLimit:
    if inRange:
      cond_1 = True
      totalSum += 1
      del sorted_A[found-i]
    
    elif cond_1:
      cond_2 = True
    
    if cond_1 and cond_2:
      searchEnd = True

    i+=1
  
def huntAnimal(shootBox):
  for h in range(2, L):
    isIn, found = binarySearch(h)
    if isIn:
      y = sorted_A[found][1] 
      scapeGoat(shootBox, found, y)

totalSum = 0

for shootBox in H:
  huntAnimal(shootBox)

print(totalSum)

정신차려보니 또 똑같은 느낌의 디지털 쓰레기를 만들어내고 있었음.
문제 붙잡은지 8시간 정도 된 것 같아서 그냥 보내주기로 함.
답지를 봤는데

https://western-sky.tistory.com/140

import sys

m, n, l = map(int, input().split())
gun = list(map(int, sys.stdin.readline().split()))
animal = list(map(int, sys.stdin.readline().split()) for _ in range(n))
gun.sort()
cnt = 0

for x, y in animal:
    if (y>l):
        continue
    s = x+y-l
    e = x-y+l
    left, right = 0, m-1
    while left <= right:
        mid = (left+right)//2
        if gun[mid] >= s and gun[mid] <= e:
            cnt += 1
            break
        elif gun[mid] < e:
            left = mid + 1
        else:
            right = mid - 1
print(cnt)

말도 안되게 간단했음.

⭐ 사대 거리를 고정하고 가능한 동물 수를 구하려고 하면 시간 복잡도가 높아진다. (n^2)
⭐ 따라서 동물을 고정하고, 잡을 수 있는 사대가 존재하는 지 확인하는 하는 것이 쉽다. (nlogn)
⭐ 동물을 잡을 수 있는 사대 좌표는 s = x+y-l (최소값) ~ e = x-y+l 이다. (l 최대 범위가 크기 때문)

이게 도대체 뭔 소린지 내일 와서 다시 공부해봐야할듯
동물을 고정하고 사대를 고정하는 것보다
사대의 범위 내에 있는 동물들을 찾는게 훨씬 빠를 것 같아서
발상이 떠오를때마다 가능성을 배제해버렸는데, 반대라니 충격적이다.
시간 복잡도는 어떻게 구하는 건지 궁금하다.