백준 알고리즘: 11650번 좌표 정렬하기 (Python)

문제 정보

---

11650번: 좌표 정렬하기

 

 

핵심

---

x좌표가 정렬의 기준이 되고, y좌표를 나중에 정렬하면 된다

하지만 이를 쉽게 풀어갈 수 없었던 것은 각각 다른 배열로 분리해서도 안되었고 그 자체에서 어떻게 정렬할 수 있을까에 대한 생각을 많이 하게 되었다

또한, 이를 제출하면서 많은 런타임 에러들을 마주하였는데 이는 sys.stdin 의 입력 라이브러리를 사용하면서 발생하였었는데 해결 방법을 찾았다

 

풀이

---

import sys


def sol():
    _ = sys.stdin.readline()
    i = sys.stdin.read().split('\n')
    l = [[] for _ in range(200001)]

    for c in i:
        try:
            x, y = c.split()
        except ValueError:
            break
        l[int(x) + 100000].append(int(y))

    for idx in range(200001):
        if l[idx]:
            for pr in sorted(l[idx]):
                print(str(idx - 100000) + ' ' + str(pr))


sol()

먼저 x y 형식으로 제공되는 입력에서 이를 각각의 배열로 쪼개는 것은 비효율적이라고 생각했고 이를 문자열로 받고, x+100000번째 배열에 y의 요소를 int 자료형으로 append 시켜준 후에 각 x 배열 번지를 방문해서 요소가 들어있다면 정렬시키고 출력하는 형식으로 문제를 해결하였다

입력의 범위가 -100,000 <= x, y <= +100,000 으로 정해져 있었기에 입력값은 200,001개 중 하나였기에 배열을 그만큼 만들어서 x좌표를 x좌표 + 100,000 번째 배열로 생각하고 y좌표는 각각 들어가있는 요소의 값이라고 생각하고 풀이하였다

 

고찰

---

뭔가 저번 풀이에서 사용하였던 sorted(key=) 를 사용할 수 있을 것 같았지만 완벽한 활용법을 잘 몰라서 사용하지 못하였는데, 문제를 풀어보고 다양한 사람들의 코드를 읽어보며 이렇게도 풀 수 있구나 하는 지식을 얻어갈 수 있었다

 

import sys

l = sys.stdin.readlines()[1:]
l.sort(key=lambda x: int(x.split()[1]))
l.sort(key=lambda x: int(x.split()[0]))
sys.stdout.write(''.join(l))

먼저 이런 풀이가 내가 풀어보려 했던 풀이인데, 람다식을 이용하여 key에 해당 함수를 넣고 split한 수를 기준으로 정렬할 수 있었다

앞서 말했었던 y 기준 정렬 후 x 기준 정렬을 통하여 모든 좌표를 정렬하고,

정렬한 배열을 join을 통하여 출력하였다

 

import sys

def sort_num(n):
    x, y = n.split()
    return int(x) + int(y)/1000000   

coordinates = sys.stdin.readlines()[1:]
coordinates.sort(key=lambda n: sort_num(n))
print(''.join(coordinates))

두 번째 풀이는 다음과 같이 함수를 만들어서 풀이하였는데 나도 솔직히 이렇게 풀려고 했었다..

y를 1,000,000으로 나눠서 더해도 x의 기준에 영향이 가지 않을 정도로 만들어주고 x 와 y 를 더하고 리턴한 수를 바탕으로 정렬하면

정렬을 한번만 사용해도 완성된 배열을 만들어낼 수 있었던 것이다,,

 

많은 풀이를 보고 배우는 하루였다

 

추가: 백준 파이썬 런타임 에러(ValueError) 해결법

솔직히 별거 없었고,

https://www.acmicpc.net/board/view/86303

이 게시물 혹은 글 참고하면 아... 할 것이다

readline()을 쓰는 경우에는 readline().rstrip()으로 양 옆 공백을 제거해주면 된다

 

참고

---

GitHub - dduneon/CodingTestPy

오늘도 역시 README "좌표 정렬하기" 를 찾으면 해당 풀이의 소스코드를 참고하실 수 있다