[백준 알고리즘] 11650번 : 좌표 정렬하기, c++

https://www.acmicpc.net/problem/11650

11650번: 좌표 정렬하기

c++로 백준 11650번 문제를 풀어보겠다.

 

 

 

 

 

 

문제

2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

출력

첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.

예제 입력 1 복사

5
3 4
1 1
1 -1
2 2
3 3

예제 출력 1 복사

1 -1
1 1
2 2
3 3
3 4

 

 

 

 

<문제 풀이>

 

처음에 작성한 코드는 다음과 같다.

 

하지만 결과는 '시간 초과' 였다. 또 visual studio에서도 내가 원하는 대로 값이 출력되지 않았다.

이를 해결하기 위해서는 새로운 함수를 사용해 새롭게 접근해 알고리즘 복잡도를 줄여야 했다.

 

 

 

최종적으로 작성한 코드는 다음과 같다.

 

1. N을 선언한 후 입력받는다.

2. <int, int>형의 pair로 된 배열을 선언한 후 입력받는다.

3. sort 함수를 사용해 오름차순으로 정렬한다.

4. 배열에 저장된 숫자들을 순서대로 출력한다.

 

 

 

 

이 문제를 통해 알게된 점 : 

<algorithm>안에 있는 여러 함수들에 대해 알게 되었다. (pair, make_pair(,), first, second)

- pair <데이터 타입, 데이터 타입> 배열이름[데이터 개수];   -> pair로 된 배열 선언

- (x, y를 입력받은 후) 배열이름[i] = make_pair(x, y);           -> pair로 배열 입력받아 저장

- 배열이름[i].first, 배열이름[i].second                              -> first, second를 통해 불러오면 각각 쌍 중 앞에 저장된                                                                                     수, 뒤에 저장된 수가 호출됨