정렬 - 좌표 정렬하기

백준 11650

정렬 - 좌표 정렬하기

 

오답1. 시간초과 .

접근.

배열 2개 준비.

1. 배열1 을 정렬할 때 배열2도 배열1의 기준에 맞춰 같이 정렬

2. 배열1 을 for문으로 쭉 탐색하면서 정렬이 필요한 시작 번호, 끝 번호를 추려내어 배열2를 정렬.

 

 

>> 정답은 도출하는 데에는 문제가 없지만 시간 초과가 떴다..

     이 문제는 노가다식의 방법으로 푸는 것이 아니다.. 어떤 방법으로 풀어야 할까??

import sys
N=int(input())
arr=[]
arr2=[]
for _ in range(N):
	a,b=sys.stdin.readline().split()
	arr.append(a)
	arr2.append(b)

s=100001

for i in range(0,N-1):
	for j in range(1,N-i):
		if arr[j-1]>arr[j]:
			tmp=arr[j-1]
			tmp2=arr2[j-1]
			arr[j-1]=arr[j]
			arr2[j-1]=arr2[j]
			arr[j]=tmp
			arr2[j]=tmp2
def cc_(s,e):
	print(s,e)
	for i in range(s,e):
		for j in range(s+1,s+e+1-i):
			if arr2[j-1]>arr2[j]:
				tmp=arr2[j-1]
				arr2[j-1]=arr2[j]
				arr2[j]=tmp

t1=0
t2=0
tt=False
for i in range(1,N):
	if arr[i-1]==arr[i]:
		t2=i
		tt=True
		if i==N-1 and tt:
			cc_(t1,t2)
	else:
		if tt:
			cc_(t1,t2)
		t1=i
		t2=i
		tt=False
for _ in range(N):
	print(arr[_]+" "+arr2[_])

 

 

정답1

JAVA에서 CompareTo 할 때 comparable을 상속받아 객체 자체에서 무엇이 더 큰지를 명시해준다면 객체 비교 자체로 원 큐에 비교 가능해지는 것이 떠올랐다. 파이썬에서는 [].sort() 만으로 배열의 첫 째값 비교 후 두 번째 값 까지 함께 정렬해주고 있었다.

 

import sys
N=int(input())
arr=[]
for _ in range(N):
	a,b=sys.stdin.readline().split()
	arr.append([int(a),int(b)])
arr.sort()
for _ in arr:
	print(f"{_[0]} {_[1]}")

 

느낀점

>> 파이썬은 역시 편하다. 허나 문제에서 배열의 첫 값은 오름차순, 두 번째 값은 내림차순으로 정렬하라고 할 때,

     어떻게 코드를 짜야할까?? 결코 위의 코드처럼 간결하지만은 않을 것이다.. 옵션이 있다면..? 파이썬 갓..

 

추가 - Priority Queue(우선순위 큐) 복습하기.