본문 바로가기
알고리즘/백준

10814번 문제 : 나이순 정렬

by son_i 2023. 3. 12.
728x90

10814번: 나이순 정렬 (acmicpc.net)

 

10814번: 나이순 정렬

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

www.acmicpc.net

너무 졸려서 이름만 보고 간단해 보이길래 고름 !

 

되게 쉬워보엿는데 역시 만만한 건 하나도 없다.

Map<Integer,String> hm = new HashMap<>();
		
		StringTokenizer st;
		for(int i = 0;i<num;i++) {
			st = new StringTokenizer(br.readLine());
			hm.put(Integer.parseInt(st.nextToken()),st.nextToken());

		}
		
		for(Map.Entry<Integer,String> entry : hm.entrySet()) {
			System.out.printf("key: %s, value:%s \n",entry.getKey(),entry.getValue());
		}

나이랑 이름을 해시맵으로 key value로 해서 받았는데

3개를 넣어도 자꾸 두 개밖에 안 나오는 거 !! 알고보니 hashmap은 key값이 중복이 안 되었다 ......

 이 문제의 핵심은 어떤 자료구조를 쓰는지 hashmap이 안 된다는 것을 알아야할 것 같고!

 

StringBuilder는 또 자동정렬인가 ? ㄴㄴ 그건 아님 뭐였더라 아 맞다 내가 배열로 서로 값 바꾸는 식으로 해서 바뀐 거였음

 

package algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args) throws  IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int num = Integer.parseInt(br.readLine());
		List <Integer>age = new ArrayList<>();
		List <String>name = new ArrayList<>();

		StringTokenizer st;
		for(int i = 0;i<num;i++) {
			st = new StringTokenizer(br.readLine());
			age.add(i,Integer.parseInt(st.nextToken()));
			name.add(i,st.nextToken());
		}
		for(int i=0;i<num;i++) {
			for(int j=i;j<num;j++) {//작은 값을 찾아서 위로 올리는 방식. 근데 서로 자리를 바꾸면 안 됨
				if(age.get(i) > age.get(j)) {
					age.add(0, age.get(j));
					name.add(0,name.get(j));
				}
			}
		}
		StringBuilder sb = new StringBuilder();
		for(int i=0;i<num;i++) {
			sb.append(age.get(i));
			sb.append(" ");
			sb.append(name.get(i));
			sb.append("\n");
		}
		System.out.println(age.get(num));
	}
}

코드 짜서 결과 맞게 나왔는데 시간초과라고 뜸 ㅠㅠㅠ,,, 시간을 어떻게 줄일까나

 

 

3/12 재도전 !!

문제에서 요구하는 것

1) 나이순 정렬 2) 나이 같으면 입력 순 정렬

 

1) Arrays.sort에 Comparator의 compar메소드 구현하여 사용자 정의로 풀기

2) 배열을 이용하지 않고 클래스 객체를 만들어 배열처럼 사용하는 방법

3) StringBuilder를 배열처럼 사용하여 Counting sort형태로 사용

package algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args) throws  IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int num = Integer.parseInt(br.readLine());
		String arr[][] = new String[num][2];
		
		StringTokenizer st;
		for(int i=0;i<num;i++) {
			st = new StringTokenizer(br.readLine());
			arr[i][0] = st.nextToken();
			arr[i][1] = st.nextToken();
		}
		Arrays.sort(arr,(o1,o2)->{
				return Integer.parseInt(o1[0])-Integer.parseInt(o2[0]);
		});
		StringBuilder sb = new StringBuilder();
		for(int i=0;i<num;i++) {
			sb.append(arr[i][0]+" "+arr[i][1]).append("\n");
		}
		System.out.println(sb);
	}
}

이렇게 해결 !

BufferedReader , StringBuilder를 사용해 시간 단축

나이순으로 정렬을 하면 compare메소드에서 나이가 같을 경우(반환값이 0인 경우)는 두 객체의 위치를 바꾸지 않기 때문에 자연스럽게 입력순 정렬이 됨. 아직 Arrays.sort에 대한 개념이 확실하게 잡히지 않은ㄱ ㅓㅅ 같다.

 

깨달았다. 

Arrays.sort(arr, new Comparator<String[]>() {

// 나이순으로 정렬
@Override
public int compare(String[] s1, String[] s2) {
    return Integer.parseInt(s1[0]) - Integer.parseInt(s2[0]);
}

});

여기서 Comparator <> 안에 쓰인 것이 compare메소드에서 다뤄줄 매개변수의 자료형 !!!

 

그래서 람다식에서는 원래함수의 매개변수, 리턴값만 쓰잖아 그래서

Arrays.sort(arr, (o1,o2) → { return o1-o2 }; 이렇게 써주었나보다 ….!!!!

 

2) Person 객체를 만들어서 배열처럼 쓰기

package algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args) throws  IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int num = Integer.parseInt(br.readLine());
	
		Person person[] = new Person[num];
		StringTokenizer st;
		for(int i = 0;i<num;i++) {
			st = new StringTokenizer(br.readLine());
			person[i] = new Person(Integer.parseInt(st.nextToken()),st.nextToken());
		}
		
		Arrays.sort(person,(o1,o2)->{
				return o1.age - o2.age;
		});
		StringBuilder sb = new StringBuilder();
		for(int i=0;i<num;i++) {// 객체배열의 객체를 출력하면 해당 인덱스의 객체의 toString() 이 출력 됨
			sb.append(person[i]);
		}
		System.out.println(sb);
	}
}
class Person{
	int age;
	String name;
	
	public Person(int age, String name) {
		super();
		this.age = age;
		this.name = name;
	}

	@Override
	public String toString() {
		StringBuilder builder = new StringBuilder();
		builder.append(age);
		builder.append(" ");
		builder.append(name);
		builder.append("\n");
		return builder.toString();
	}
}

알아둬야할 것은 내가 Person 객체에 toString 메소드를 원하는 출력방식대로 오버라이딩 해줘서 얘를 출력하면 toString()이 출력됨. 그래서 sb.append에 person[i]로 객체를 차곡차곡 쌓다가 출력하면 toString에 정의된 대로 나오는 거

 

3) StringBuilder 를 배열처럼 사용해서 Counting sort처럼 사용

package algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args) throws  IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int num = Integer.parseInt(br.readLine());
		
		StringBuilder []p = new StringBuilder[201]; //입력되는 나이의 범위 1~200
		
		for(int i=0;i<p.length;i++) {
			p[i] = new StringBuilder(); //배열 하나하나마다 StringBuilder를 만들어줌.
		}
	
		for(int i=0;i<num;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int age = Integer.parseInt(st.nextToken());
			String name = st.nextToken();
			p[age].append(age).append(" ").append(name).append("\n");
            // 카운팅 정렬 : 나이를 index 로 하여 해당 배열에 나이와 이름을 append() 한다
		}
		StringBuilder sb1 = new StringBuilder();
		for(StringBuilder val : p) {
			sb1.append(val);
		}
		System.out.println(sb1);
	}
}

 

카운팅 정렬 ?  데이터 값을 인덱스로 하여 정렬하는 방식.

 

시간이 정말 빨라졌다. !

728x90

'알고리즘 > 백준' 카테고리의 다른 글

1018번 문제 : 체스판 다시 칠하기  (0) 2023.03.16
10250번 문제 : ACM호텔  (0) 2023.03.13
7568번 문제 : 덩치  (0) 2023.03.11
4153번 문제 : 직각삼각형  (0) 2023.03.10
2292번 문제 : 벌집  (0) 2023.03.08