정글사관학교 17일차 TIL: 사냥꾼(#8993), 철로(#13334), 파이썬 sort 조건 설정 관련 팁

0. 목차

1. 사냥꾼(#8983) 문제

2. 철로(#13334) 문제

P.S. 파이썬 sort 조건 설정 관련 팁

 

1. 사냥꾼 (#8983)

문제 링크: https://www.acmicpc.net/problem/8983

 

사냥꾼은 이제 확실히 이해해서 풀이를 업로드! 예외 조건을 잘 처리해야 100점이 가능하다.

 

1번 풀이: 이중 for문 이용 (시간 복잡도: O(N^2)) => 60점

1번 풀이는 가장 먼저 이 문제에 접근할 때 썼던 방법이다. 당시만 해도 아직 이분 탐색에 익숙치 않던 시절이었다. 바로 떠오르는 방법이라고는 for문 두 번 돌리기 밖에 없었다. 이 문제는 부분 점수가 주어지는 문제여서 의외로 60점이라는 높은(?) 점수를 받긴 했으나 완벽한 풀이는 아님.

 

방식은 이렇다. 놓여진 사대에서 총을 하나 고르고(for문 한 번 돌고) 들판에 있는 동물 중 하나를 골라서(for문 두 번 돈다) 사대와 총 사이 거리가 사정거리보다 작거나 같을 경우 count하는 방식.

 

이때, 동물을 저장해 둔 리스트에서 하나씩 동물을 지우는데 "for j in animal:" 이렇게 쓰면 for문을 도는 순서가 엉켜서 리스트 내 모든 원소를 훑지 못하게 된다. 따라서 animal[:]이라고 쓰면 해당 리스트를 복사해서 새로운 리스트를 만들기 때문에 기존 리스트인 animal에는 지장이 없다.

 

# 풀이 1: 이중 for문 돌리기 => 점수 60점

from sys import stdin

m, n, l = map(int, stdin.readline().split())
gun = list(map(int, stdin.readline().split()))
animal = [list(map(int, stdin.readline().split())) for _ in range(n)]

def distance(gun, animal):
    return (abs(gun-animal[0]) + animal[1])

count = 0
for i in gun:
    for j in animal[:]:
        if distance(i, j) <= l:
            count += 1
            animal.remove(j)


print(count)

 

2번 풀이: 이분탐색 이용 + 예외 케이스 사전 차단 (시간 복잡도: O(NlogN)) => 100점

2번 풀이에서는 이분 탐색과 예외 케이스를 고려했다. 위와 달리 이번에는 사대를 sort()를 이용해 오름차순으로 정렬해준다. 그러면 사대는 왼쪽부터 작은 순으로 차례로 주루룩 나열될 것이다.

 

위에서는 for문을 리스트 컴프리헨션으로 돌려서 애초부터 리스트를 만들고 시작했는데 이번에는 인풋의 양이 워낙 많은지라 바로 for문을 돌리면서 count하는 방식으로 했다.

 

for문을 돌면서 변수 x, y로 어느 한 동물의 x좌표와 y좌표를 받는다.(x, y = map(int, stdin.readline().split())))

 

위에서도 말했듯, 여기서는 예외 케이스를 사전에 차단하는 게 핵심이다. 처음에는 이분 탐색으로 바로 돌렸더니 오히려 점수가 낮게 나오는 불상사가 발생했다. 이분 탐색도 시간이 오래 걸리는 것은 매한가지이기 때문에 사전에 예외 케이스를 필터링하는 장치를 마련한다. 총 두 가지가 있는데

 

1) if not y > l: 동물 위치와 사대에서 핵심적으로 비교해야 하는 값은 오직 x좌표이다. y좌표 값은 사정거리에서 빼주기만 하고 가장 가까운 x좌표와의 거리 비교만 하면 되는데, 여기서 애당초 y좌표 값이 l보다 큰 케이스는 계산하고 자시고 할 것도 없다. 그냥 바로 걸러내기.

 

2) 사대의 왼쪽/오른쪽 끝과 동물 위치 비교 (if x <= gun[0] / elif x >= gun[-1]): 동물 위치의 x좌표가 사대 양끝에 있는 총 범위에 들어오는 케이스면 굳이 이분탐색을 돌려가면서 찾을 필요가 전혀 없다. 이분 탐색의 시간복잡도는 O(NlogN)인데 양끝에 있는 걸 찾아내는 건 O(1)이므로 이런 경우는 이분 탐색 돌리지 않고 양끝 총의 범위 안에 들어오는지 안 오는지만 재빨리 계산해서 count를 센다.

 

이렇게 거르고 나면 나머지 값은 bisect 라이브러리를 이용해 사대가 있는 리스트(gun)에서 동물 위치의 x좌표가 들어갈 수 있는 위치의 인덱스를 받는다. 이후 해당 인덱스를 기준으로 동물과 왼쪽 총 혹은 동물과 오른쪽 총 간의 거리가 사정거리 안에 들어오면 count를 한다.

 

최종 코드는 아래와 같다.

 

# 풀이 2: 이분탐색으로 x, y 기준으로 싹 정렬하고 제거

from sys import stdin
from bisect import bisect_left

m, n, l = map(int, stdin.readline().split())
gun = list(map(int, stdin.readline().split()))

gun.sort()  # 사대 정렬하고

count = 0
for i in range(n):
    x, y = map(int, stdin.readline().split())
    if not y > l:
        if x <=gun[0]:
            if gun[0]-x + y <=l:
                count +=1
        elif x >= gun[-1]:
            if x-gun[-1] + y <=l:
                count +=1
        else:
            idx = bisect_left(gun, x)
            if (abs(x - gun[idx - 1])+y) <= l or (abs(gun[idx] - x)+y) <= l:
                count += 1

print(count)

 

예외 케이스를 미처 고려하지 못했는데, 이에 대해서는 다음 링크를 참고했다:  지훈's 블로그

 

 

 

2. 철로 (#13334)

먼저 문제 링크.

 

철로 문제는 힙을 이용하면 풀 수 있는데, 단순히 힙만 쓴다고 되는 문제는 아니다. 이 문제를 풀려면 양 끝점을 어떤 식으로 정렬하고 어떻게 힙에 넣는지를 이해하는 게 필요하다. 그래서 엄밀히 유형을 구분하자면 정렬 + 힙.

 

문제를 보면 어디가 집이고 어디가 오피스인지에 대한 구분은 사실상 의미가 없다. 그냥 왼쪽/오른쪽 점 둘 다 철로 안에 들어오기만 하면 count가 가능하다. 따라서 첫번째는, [집, 오피스]로 주어지는 숫자 배열을 [min, max]로 재배치한다. 이는 정렬을 편하게 하기 위함이다.

 

이때, 우리는 한 가지 예외 케이스를 함께 정리할 수 있다. 만약 철로 길이 d보다 집-오피스 사이 거리가 큰 애들은 애초부터 고려할 필요가 없으니 min, max로 재배치할 때 예외에 해당되는 애들은 가차없이 빼준다.

 

이를 마치고 나면 정렬을 해줄 건데, 이때 우리는 선분에서 오른쪽 점(x[1])을 기준으로 오름차순으로 정렬할 것이다. 왜 그런지는 아래에서 설명할 것이니 일단 그렇게만 알고 있자. 여기까지를 코드로 정리하면 아래와 같다.

 

from sys import stdin
import heapq

n = int(stdin.readline())
com = [list(map(int, stdin.readline().split())) for _ in range(n)]
d = int(stdin.readline()) # d는 선분 길이

li = []

for i in com:
    i[0], i[1] = min(i[0], i[1]), max(i[0], i[1])
    if i[1] - i[0] > d:
        continue
    else:
        li.append(i)
        
li.sort(key= lambda x: x[1])

 

이를 마치면 아래 이미지와 같이 리스트가 정렬된다. 아래 이미지는 예제에서 주어진 케이스다.

 

이제 맨 아래에 위치한 [10, 20]부터 for문으로 하나씩 선분을 받을 것이다(for i in li). 그전에, 최대값을 저장하기 위한 변수로 max_count=0, 최소 힙을 꺼내기 위한 리스트 heap = [] 을 선언한다. 여기다 뭘 할 것이냐?

 

이제 가장 아래에 있는 선분부터 하나씩 오른쪽 점을 기준으로 왼쪽 방향으로 철로를 깐다고 생각해본다. 그리고 그 안에 들어올 수 있는 다른 선분 수를 셀 것이다. 이때 다른 선분이 해당 철로 안에 들어오는지는, 철로의 왼쪽 끝보다 해당 선분의 왼쪽 점이 더 오른쪽에 위치하는히 확인하면 알 수 있다.

 

예를 들어 가장 밑에 있는 선분 [10, 20]에 철로를 깐다고 해보자. 아래 이미지를 보면, 빨간 선의 길이를 d라고 하면 현재 [10, 20]만 놓고 비교했을 때 비교할 다른 선분이 없기 때문에([10, 20]이 가장 왼쪽에 있기 때문) 이 [10, 20]을 heap 리스트에 heappush로 넣는다. 이때 max_count는 [10, 20] 하나만 해당되므로 max_count +=1이다.

 

이제 그 다음 선분인 [10, 25]에다가 오른쪽 점인 25를 기준으로 왼쪽 방향으로 철로를 깔 것이다. 해당 선분([10, 25])은 어차피 철로 안에 들어오니 괜찮고, 아까 heap에 넣었던 heap[0]인 [10, 20]에서 왼쪽 점 10과 철로의 왼쪽 끝인 i[1]-d = 10-30 = -20을 비교해보자.  -20 < 10이므로 [10, 20]은 철로 안에 들어온다. 따라서 max_count += 1을 해서 max_count = 1+1 = 2이다.

 

 

 

이제 다음 선분인 [25, 30]으로 이동한다. 여전히 heap[0][0] = 10이므로 철로의 왼쪽 끝은 30-30 = 0이니 [25, 30]을 기준으로 철로를 깔았을 때 [10, 20], [10, 25] 둘다 철로 안에 들어온다. 따라서 max_count = 3.

 

다음 선분인 [25, 35]로 넘어가자. 여기서가 중요하다. 왜 heap을 쓰는지가 여기서 나오는데, heap[0][0]을 뽑으면 가장 왼쪽(=가장 최솟값인)10이 나온다. 만약 아까 봤던 [25, 30]에서 왼쪽 점 위치가 25가 아니라 5였다고 해보자. 그러면 heap[0][0]은 5가 될 것이다. 그러면 다음 선분에서 철로를 깔 때 heap[0][0]과 i[1]-d(철로의 왼쪽 끝점 위치)만 비교해주면 그 사이에 있는 다른 선분들은 다 철로 안에 자동 포함될 터이니 계산이 엄청 간단해진다. 즉, 항상 heap[0][0]만 생각하면 된다는 것! 근데 만약 철로 길이보다 바깥에 삐져나간 애가 있다면 걔는 heap에서 제거해주면 된다(heappop). 

이를 반영한 최종 코드는 아래와 같다.

from sys import stdin
import heapq

n = int(stdin.readline())
com = [list(map(int, stdin.readline().split())) for _ in range(n)]
d = int(stdin.readline()) # d는 선분 길이

li = []

for i in com:
    i[0], i[1] = min(i[0], i[1]), max(i[0], i[1])
    if i[1] - i[0] > d:
        continue
    else:
        li.append(i)

li.sort(key= lambda x: x[1])

heap = []
max_count = 0
for i in li:
    if len(heap) == 0:
        heapq.heappush(heap, i)
    else:
        while len(heap) != 0 and heap[0][0] < i[1] - d:
            heapq.heappop(heap)
        heapq.heappush(heap, i)
    max_count = max(max_count, len(heap))

print(max_count)

 

참고 링크 1

https://blog.naver.com/occidere/221085858307

 

참고 링크 2: 지훈이 블로그

https://uneducatedjungler.tistory.com/43

 

 

P.S. 파이썬 sort 쓸 때 다중 조건 설정하는 방법

위의 철로 문제도 그렇고, 정렬 관련 문제를 풀 때 sort를 정말 많이 쓰는데 그것도 그냥 단일 숫자값만 정렬하는 게 아니라 어쩔 때는 값이 2개인 리스트끼리 정렬하기도 하고, 그 2개 리스트에서 왼쪽 값은 내림차순 / 오른쪽 값은 오름차순으로 정렬하기도 하는 등 조건을 복잡하게 설정해야 할 때가 있다. 이를 공부하기 위해 아래 글을 정리.

 

파이썬에서는 내장 라이브러리dp 정렬 기능 함수가 있다. list.sort() 혹은 sorted(list) 를 이용한다. 괄호 안에 아무 인자도 넣지 않으면 아래와 같이 자동 오름차순 정렬한다.

a = [4,1,2,5,7,3,6]
b = sorted(a)
# b = [1,2,3,4,5,6,7]

 

list.sort() 를 찬찬히 살펴보면 다음과 같다.

a = [(1, 2), (0, 1), (5, 1), (5, 2), (3, 0)]

# 인자없이 그냥 .sort()만 쓰면, 리스트 아이템의 가장 첫번째 인덱스를 기준으로 오름차순 정렬 후 그 다음 인덱스를 기준으로 다시 오름차순 정렬
b = a.sort()
# b = [(0, 1), (1, 2), (3, 0), (5, 1), (5, 2)] # 첫번째 인덱스가 먼저 오름차순 / 그 다음 인덱스도 오름차순

# key 인자에 함수를 넘겨주면 해당 함수의 반환값을 비교하여 순서대로 정렬한다.
c = a.sort(key = lambda x : x[0]) => x[0]을 기준으로 오름차순 정렬하라는 말
# c = [(0, 1), (1, 2), (3, 0), (5, 1), (5, 2)]
d = a.sort(key = lambda x : x[1]) 
# x[1]을 기준으로 오름차순 정렬. x[1]이 가장 낮은 값부터 차례로 정렬된다. 
# x[1]이 같으면 그 다음에 x[0]을 오름차순 정렬.
# d = [(3, 0), (0, 1), (5, 1), (1, 2), (5, 2)]

# 아이템 첫 번째 인자를 기준으로 오름차순으로 먼저 정렬하고,
# 그리고 그 안에서 다음 두 번째 인자를 기준으로 내림차순으로 정렬하게 하려면, 다음과 같이 할 수 있다.
e = [(1, 3), (0, 3), (1, 4), (1, 5), (0, 1), (2, 4)]
f = a.sort(key = lambda x : (x[0], -x[1]))
# f = [(0, 3), (0, 1), (1, 5), (1, 4), (1, 3), (2, 4)]

정리하면,

• sort()는 정렬해주는 파이썬 내장 함수.
• sort()에서 괄호 안에 아무 인자도 넣지 않으면 전부 오름차순으로 정렬한다.
• sort()의 key 인자로, 내가 비교하고 싶은 것을 함수 형태로 넣어주면 된다.
• 비교 함수는 비교할 아이템의 요소를 반환하면 된다.
• 비교 함수는 익명 함수(lambda) 도 가능하고, 별도로 정의해도 된다.
• 비교할 아이템의 요소가 복수 개일 경우, 튜플로 그 순서를 내보내주면 된다.
  • ex. sorted(e, key = lambda x : (x[0], -x[1]))
  • -를 붙이면, 현재 정렬차순과 반대로 하게 된다.

https://dailyheumsi.tistory.com/67