๋ฌธ์
https://www.acmicpc.net/problem/11650
๋ฐฑ์ค ๋ฌธ์ ์ง - 0x0E๊ฐ - ์ ๋ ฌ I
์๊ณ ๋ฆฌ์ฆ: ์ ๋ ฌ
ํ์ด
2์ฐจ์ ํ๋ฉด ์์ ์ N๊ฐ๊ฐ ์ฃผ์ด์ง๋ค. ์ขํ๋ฅผ x์ขํ๊ฐ ์ฆ๊ฐํ๋ ์์ผ๋ก, x์ขํ๊ฐ ๊ฐ์ผ๋ฉด y์ขํ๊ฐ ์ฆ๊ฐํ๋ ์์๋ก ์ ๋ ฌํ ๋ค์ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ฒซ์งธ ์ค์ ์ ์ ๊ฐ์ N (1 ≤ N ≤ 100,000)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์๋ i๋ฒ์ ์ ์์น xi์ yi๊ฐ ์ฃผ์ด์ง๋ค. (-100,000 ≤ xi, yi ≤ 100,000) ์ขํ๋ ํญ์ ์ ์์ด๊ณ , ์์น๊ฐ ๊ฐ์ ๋ ์ ์ ์๋ค.
(x, y)๋ก ๊ตฌ์ฑ๋ ์ขํ๋ค์ 1) x๊ฐ ์ฆ๊ฐํ๋ ์์ผ๋ก, 2) ๋์ผํ๋ค๋ฉด y๊ฐ ์ฆ๊ฐํ๋ ์์ผ๋ก ์ ๋ ฌํ๋ ๋ฌธ์ ๋ค.
์ฌ์ค ์ด ๋ฌธ์ ๋... ๋จ์ํ sort()๋ง ์ฌ์ฉํ๋ฉด ๋๋ค.
(x, y)์ ํํ์ด ์์๋ ๊ธฐ๋ณธ์ ์ธ ์ ๋ ฌ ์์๋ x ์ ๋ ฌ → y ์ ๋ ฌ ์ด๊ธฐ๋๋ฌธ์ด๋ค.
๋ง์ฝ ๋ฌธ์ ๊ฐ "y๊ธฐ์ค์ผ๋ก ์ ๋ ฌ ํ x๊ธฐ์ค์ผ๋ก ์ ๋ ฌ" ์ด์๋ค๋ฉด ์ถ๊ฐ์ ์ธ ์ฝ๋๊ฐ ํ์ํ๊ฒ ์ง๋ง, ์ ๋ ฌ ๊ธฐ์ค์ด ์ขํ์ ์ธ๋ฑ์ค ์์์ ๋์ผํ๋ฏ๋ก ๋ณ๋ค๋ฅธ ์กฐ๊ฑด์ด ํ์์๋ค.
์ ์ฒด ์ฝ๋
# ๋ฉ๋ชจ๋ฆฌ: 44580KB / ์๊ฐ: 260ms
import sys
input = sys.stdin.readline
N = int(input())
points = [tuple(map(int, input().split())) for _ in range(N)]
points.sort()
for x, y in points:
print(x, y)
๋ง์ฝ ์ธ๋ฑ์ค์ ๋ค๋ฅธ ์์๋ก ์ ๋ ฌํด์ผํ๋ค๋ฉด,
sort()ํจ์์ key= ์ธ์์ lambda๋ฅผ ์ฌ์ฉํ๋ฉด ๋งค์ฐ ๊ฐ๋จํ๋ค!
๋จผ์ (x, y) ํํ์ ํํ๋ค์ ์ธ์๋ก ๋ฐ์์จ ๋ค, ์ฐ์ ์์๋ฅผ ์์ฑํด์ฃผ๋ฉด ๋๋ค.
lambda์์ ์ฌ์ฉํ ๋ณ์๋ฅผ a๋ผ๊ณ ํ์๋, a๋ ๊ฐ (x, y) ํํ๋ค์ ๋ํ๋ธ๋ค.
์ฒซ๋ฒ์งธ๋ x๊ฐ ์ฆ๊ฐํ๋ ์(์ค๋ฆ์ฐจ์)์ด๋ฏ๋ก a[0], ๋๋ฒ์งธ๋ y๊ฐ ์ฆ๊ฐํ๋ ์์ด๋ฏ๋ก a[1]๋ฅผ ์์๋๋ก ์ ํํด์ฃผ๋ฉด ๋๋ค.
๋จ, ์ ๋ ฌ ๊ธฐ์ค์ ์ฌ๋ฌ๊ฐ ์์ฑํ ๊ฒฝ์ฐ ๊ดํธ()๋ก ๊ผญ ๊ฐ์ธ์ค์ผํ๋ค.
# ๋ฉ๋ชจ๋ฆฌ: 51900KB / ์๊ฐ: 284ms
import sys
input = sys.stdin.readline
N = int(input())
points = [tuple(map(int, input().split())) for _ in range(N)]
points.sort(key=lambda x: (x[0], x[1]))
for x, y in points:
print(x, y)
๊ทธ๋ ๋ค๋ฉด lambda๋ฅผ ์ฌ์ฉํ์ง ์๊ณ ํ๋ ค๋ฉด ์ด๋ป๊ฒ ํด์ผํ ๊น?
์ ๋ ฌ ๊ธฐ์ค ๊ฐ์ ๋ฐ๋ก ์ ์ฅํ ๋ค sort ํด์ฃผ๋ฉด ๋๋ค.
(x, y, z) ํํ์ ํํ๋ค๋ก ์ด๋ฃจ์ด์ง ๋ฆฌ์คํธ๊ฐ ์๋ค๊ณ ๊ฐ์ ํด๋ณด์.
1. x๊ฐ ์ฆ๊ฐํ๋ ์
2. ๊ฐ๋ค๋ฉด y๊ฐ ์ฆ๊ฐํ๋ ์
3. ๊ฐ๋ค๋ฉด z๊ฐ ๊ฐ์ํ๋ ์
์ผ๋ก ์ ๋ ฌ์ ํ๋ ค๋ฉด, ๊ธฐ์ค์ (a[0], a[1], -a[2]) ๊ฐ ๋๋ค.
(์ ๊ธฐ์ค๊ฐ๋ค, ์๋์ ๊ฐ)์ผ๋ก ์๋ก์ด ๋ฆฌ์คํธ๋ฅผ ์์ฑํ ๋ค ์ ๋ ฌ ํ ์๋์ ๊ฐ๋ง ์ถ๋ ฅํด์ฃผ๋ฉด lambda๋ฅผ ์ฌ์ฉํ๊ฒ๊ณผ ๋์ผํ๋ค.
data = [(1, 3, 5), (1, 2, 7), (2, 3, 6), (1, 3, 2)]
# ์ ๋ ฌ ๊ธฐ์ค์ด ๋๋ ์ค๊ฐ ๋ฆฌ์คํธ ์์ฑ
tmp = [(x[0], x[1], -x[2], x) for x in data]
# ์ค๊ฐ ๋ฆฌ์คํธ ์ ๋ ฌ
tmp.sort()
# ์๋ณธ ๋ฐ์ดํฐ ์ถ์ถ
sorted_data = [item[3] for item in tmp]
print(sorted_data)
# ์ถ๋ ฅ: [(1, 2, 7), (1, 3, 5), (1, 3, 2), (2, 3, 6)]