백준 10814번: 나이순 정렬

우선 회원들의 수가 입력된다. 이후에, 회원들의 나이와 이름이 입력된다.

그랬을 때 회원들을 나이 순으로 정렬해서 출력하는데 만약 나이가 같다면 입력받은 순으로 출력한다.

 

나이와 이름이 동시에 입력되는데 그중에서 나이만 골라서 비교를 해야한다.

그래서 클래스를 새로 만들어서 그곳에 나이, 이름, 입력 순서를 받아주었다.

그리고 나이를 기준으로 정렬을 하면서 그와 동시에 나이가 같다면 입력 순으로 정렬을 다시 하는 코드를 짰다.

그러나 시간 초과가 되어서 코드를 다시 만들어야 했다.

아래는 내가 실패한 코드이다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.Arrays;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int N = Integer.parseInt(br.readLine());
		Member[] mem = new Member[N];
		for (int i = 0; i < N; i++) {
		    StringTokenizer st = new StringTokenizer(br.readLine());
		    mem[i] = new Member(Integer.parseInt(st.nextToken()), st.nextToken(), i);
		}
		br.close();
		
		for (int i = 0; i < N; i++) {
		    for (int j = i + 1; j < N; j++) {
		        if (mem[i].age > mem[j].age) {
		            Member temp = mem[i];
		            mem[i] = mem[j];
		            mem[j] = temp;
		        }
		        if ((mem[i].age == mem[j].age) && (mem[i].index > mem[j].index)) {
		            Member temp = mem[i];
		            mem[i] = mem[j];
		            mem[j] = temp;
		        }
		    }
		}
		
		for (Member i: mem)	bw.write(i.age + " " + i.name + "\n");
		bw.flush();
		bw.close();
	}
}

class Member {
    int age;
    String name;
    int index;
    Member(int a, String n, int i) {
        this.age = a;
        this.name = n;
        this.index = i;
    }
}

코드를 다시 한번 짜면서 나는 정렬해주는 알고리즘이 시간 복잡도를 늘리 것처럼 느꼈다.

그래서 정렬을 줄이기 위해 나이를 클래스 내부말고도 저장하는 배열을 만들어 주었고,

이 배열을 정렬한 뒤에, 기존 클래스는 입력받은 순서로 정렬되어있으므로,

배열에서 뽑은 현재 나이와 일치하는 것들을 출력하도록 하였다.

그 과정속에서 나이가 같은 경우에도 중복없이 한번씩만 실행되어야 하므로 continue를 사용해주었다.

그렇게 하여 문제를 풀 수 있었고, 아래는 해당 문제를 푼 코드이다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.Arrays;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int N = Integer.parseInt(br.readLine());
		Mem[] mem = new Mem[N];
		int[] ag = new int[N];
		for (int i = 0; i < N; i++) {
		    StringTokenizer st = new StringTokenizer(br.readLine());
		    ag[i] = Integer.parseInt(st.nextToken());
		    mem[i] = new Mem(ag[i], st.nextToken());
		}
		Arrays.sort(ag);
		br.close();
		
		Label: for (int i = 0; i < N; i++) {
		    for (int j = 0; j < N; j++) {
		        if (i != 0 && ag[i - 1] == ag[i]) continue Label;
		        if (ag[i] == mem[j].age) bw.write(mem[j].age + " " + mem[j].name + "\n");
		    }
		}
		
		bw.flush();
		bw.close();
	}
}

class Mem{
    int age;
    String name;
    Mem(int age, String name) {
        this.age = age;
        this.name = name;
    }
}