[백준] 10814 - 나이순정렬 JAVA

Solved.ac Class 완전정복 프로젝트

Class : 2 ~ 2 ++

 

---

 

링크

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

10814번: 나이순 정렬

문제

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

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

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

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

 

접근방법

 문제는 나이 순으로 정렬을 하되, 나이가 같으면 가입자 순으로 의 정렬을 요구하고 있다. 나이 정렬과 2차적으로 가입 순 정렬을 요구하는 문제이다. 특수한 비교 조건이므로 비교 조건을 만들어 쓸 수 있겠다는 생각을 가지고 풀이로 들어가자.

 

풀이

 Arraylist로 string과 integer 타입을 모두 때려박자니, 너무 두꺼워지는 것 같아. 다음과 같이 분리하였다.

 

1. String [] names -> 인덱스가 가입자 인덱스와 동일하며, 값은 이름값을 가진다.
2. ArrayList <int []> ->리스트 원소의 0번 인덱스에는 나이를, 1번 인덱스에는 가입자 인덱스를  가진다. 

원래 가입한 인덱스 순서를 기준으로 객체를 두 가지로 분리하였다. ArrayList 객체와 names는 인덱스 번호로 매핑이 가능하니, ArrayList 원소가 가진 나이 속성을 통해 정렬을 하면 된다.

 

앞서 말했듯, 나이가 같을 때의 한하여, 가입 순으로 2차적 정렬이 필요하기 때문에, 람다식을 이용하여 다음과 같이 정렬방법을 정의하였다.

//람다식을 이용한 비교 정의 
Collections.sort(datas,(o1, o2) -> {
            if(o1[0] == o2[0]){
                //나이가 같을때에 한하여, 비교
                return  Integer.compare(o1[1],o2[1]);
            }else{
            	//나이가 다를때는 나이로 비교
                return Integer.compare(o1[0],o2[0]);
            }
        });

코드

1. 하나씩 System out으로 출력하는 코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        Main test = new Main();
    }


    public Main() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int tc = Integer.parseInt(br.readLine());

        ArrayList<int[]> datas = new ArrayList<>();
        String[] names = new String[tc];
        for (int i = 0; i < tc; i++) {
            int[] info =new int[2];
            info[1] = i;
            StringTokenizer stringTokenizer = new StringTokenizer(br.readLine()," ");
            info[0] = Integer.parseInt(stringTokenizer.nextToken());
            names[i] = stringTokenizer.nextToken();
            datas.add(info);
        }
        solution(datas,names);
    }


    public void solution(ArrayList<int[]> datas, String[] names) {

        Collections.sort(datas,(o1, o2) -> {
            if(o1[0] == o2[0]){
                return  Integer.compare(o1[1],o2[1]);
            }else{
                return Integer.compare(o1[0],o2[0]);
            }
        });

        for (int i = 0 ; i < datas.size() ; i++){
            System.out.println(datas.get(i)[0] +" "+ names[datas.get(i)[1]]);
            
        }
    }
}

 

2. Stringbuilder를 통해 한번에 출력하는 코드 (시간 개선 코드)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        Main test = new Main();
    }


    public Main() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int tc = Integer.parseInt(br.readLine());
		
        //나이와 인덱스를 저장
        ArrayList<int[]> datas = new ArrayList<>();
        //인덱스(=원본인덱스와 순서 맞춤), 이름 저장
        String[] names = new String[tc];
        
        for (int i = 0; i < tc; i++) {
            //0 - 나이 : 1 - 인덱스
            int[] info =new int[2];
            info[1] = i;
            StringTokenizer stringTokenizer = new StringTokenizer(br.readLine()," ");
            info[0] = Integer.parseInt(stringTokenizer.nextToken());
            names[i] = stringTokenizer.nextToken();
            datas.add(info);
        }
        
        solution(datas,names);
		
        //출력
        for (int i = 0 ; i < datas.size() ; i++){
            sb.append(datas.get(i)[0] +" "+ names[datas.get(i)[1]]);
            sb.append("\n");
        }

        System.out.println(sb);
    }

	//sorting 만함
    public void solution(ArrayList<int[]> datas, String[] names) {
        Collections.sort(datas,(o1, o2) -> {
            if(o1[0] == o2[0]){
                return  Integer.compare(o1[1],o2[1]);
            }else{
                return Integer.compare(o1[0],o2[0]);
            }
        });
    }
}

 

 

결과

 

32822083 - Stringbuilder를 이용한 한 번의 출력

32821642 - sout으로 하나씩 출력

 

속도 차이가 엄청나다 ㄷㄷ;

 

---

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다.