[Baekjoon] 10814 : 나이순 정렬 (C++)

Baekjoon Online Judge 10814번 : 나이순 정렬

---

문제

온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000)

둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다.

출력

첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다.

예제 입력

3
21 Junkyu
21 Dohyun
20 Sunyoung

예제 출력

20 Sunyoung
21 Junkyu
21 Dohyun

---

코드

저번 문제를 풀 때 생각했던 것처럼 정렬 문제를 모두 입력받고 정렬하는 방식이 아닌 자료를 입력할 때 정해진 위치에 넣어서 정렬된 배열을 만드는 알고리즘을 생각해보았다. 아래 코드에서 주석 처리된 부분(Move_member(), Add_member())이 그 부분인데, 단순하게 뒤에 자료를 한 칸씩 밀어놓고 새로운 자료를 추가하다보니 문제는 해결되지만 시간 초과로 제출에는 실패하였다.

그래서 백준에 제출할 때에는 algorithm에 들어있는 stable_sort()함수를 사용하여 나이 순으로 정렬하되 나이가 같을 시에 가입 순서대로 정렬되도록 하였다.

#include <iostream>
#include <algorithm> // stable_sort()

using namespace std;

typedef struct { // 회원을 저장할 구조체
  int age;  // 회원의 나이
  string name; // 회원의 이름
} Member;

bool cmp(Member m1, Member m2){
  return m1.age < m2.age; // 나이 순 오름차순
}

/* void Move_member(int begin, int end, Member* list) {
  // 회원을 추가할 자리를 만드는 함수
  // 추가할 자리 이후의 자료들을 오른쪽으로 한칸씩 옮김
  for(int i = end; i >= begin; i--){
    list[i+1].age = list[i].age;
    list[i+1].name = list[i].name;
  }
}

void Add_member(int order, Member input, Member* list) {
  // 새로운 회원 추가
  // 나이순으로 정렬하면서 추가 (가입 순서는 자동으로 정렬)
  for(int i = 0; i < order; i++)
  // 새로운 회원이 배열 중간에 들어갈 때
    if(input.age < list[i].age){
      Move_member(i, order-1, list);
      list[i].age = input.age;
      list[i].name = input.name;
      return;
    }
  // 새로운 회원이 가장 연장자일 때
  list[order].age = input.age;
  list[order].name = input.name;
} */

int main(void) {
  int N;
  // Member input;
  Member* mem_list;

  cin >> N;
  mem_list = new Member[N]; // 크기가 N인 배열 동적할당
  for(int i = 0; i < N; i++) {
    cin >> mem_list[i].age >> mem_list[i].name; // 입력

    // cin >> input.age >> input.name;
    // Add_member(i, input, mem_list);
  }

  stable_sort(mem_list, mem_list+N, cmp);
  // stable_sort()함수를 사용해서 가입 순서 변경 X

  for(int i = 0; i < N; i++)
    cout << mem_list[i].age << " " << mem_list[i].name << '\n';
    // 정렬된 회원 목록 출력

  delete[] mem_list; // 동적할당 해제
  return 0;
}