10814번 문제 : 나이순 정렬

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

10814번: 나이순 정렬

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

 

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

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);
	}
}

 

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

 

시간이 정말 빨라졌다. !