백준 2751 Java

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

2751번: 수 정렬하기 2

 

---

 

 

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
 
 
public class Main {
	public static void main(String[] args) throws IOException {
    
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(br.readLine());
		
		// list 계열 중 하나를 쓰면 된다.
		ArrayList<Integer> list = new ArrayList<>();
		
		for(int i = 0; i < N; i++) {
			list.add(Integer.parseInt(br.readLine()));
		}
		
		Collections.sort(list);
		
		for(int value : list) {
			sb.append(value).append('\n');
		}
		System.out.println(sb);
	}
}

---

이 문제 풀면서 시간초과가 세번이나 나왔다.

 

첫번째는 정렬을 for문으로 작성해서,

두번째는 Scanner를 사용해서,

세번째는 String의 출력을 for문에서 System.out.println()을 사용해서 였다.

 

이 순서로 성능을 올릴 수 있는 방법을 차근차근 변경해 나갔다. 

단순히 정렬을 for문을 사용해서 버블정렬을 했는데, Collection을 사용하는 방식으로 변경을 했다. 

그리고 Scanner보다 빠른 BufferedReader를 사용했다. 

마지막으로는 for문으로 list를 하나하나 출력하는 방식이 아닌 StringBuilder로 모든 결과를 이어 붙여서 한번에 출력하는 방식으로 변경했다. 

 

 

Collection은 목록성 데이터를 처리하는 자료구조를 통칭한다고 한다. 

 

자바에서의 자료유형은 아래와 같다. 

 

- KEY-VALUE의 형태로 저장되는 Map형

- 순서가 있는 목록인 List형

- 순서가 중요하지 않은 목록인 Set형

- 먼저 들어온 것이 먼저 나가는 Queue형

 

출처: https://tenlie10.tistory.com/10 [게임 엔진/클라이언트 개발자:티스토리]

 

***

Set _ HashSet, TreeSet

List _  LinkedList, Vector,ArrayList

Queue _ LinkedList, PriorityQueue

Map _ Hashtable, HashMap, TreeMap

 

1. Set

순서를 유지하지 않는 데이터의 집합. (데이터의 중복을 허용하지 않음)

• HashSet
  - 가장빠른 임의 접근 속도
  - 순서를 예측할 수 없음
• TreeSet
  - 정렬방법을 지정할 수 있음

2. List 

순서가 있는 데이터의 집합. (데이터의 중복을 허용)

• LinkedList
  - 양방향 포인터 구조로 데이터의 삽입, 삭제가 빈번할 경우 데이터의 위치정보만 수정하면 되기에 유용
  - 스택, 큐, 양방향 큐 등을 만들기 위한 용도로 쓰임
• Vector
  - 과거에 대용량 처리를 위해 사용했으며, 내부에서 자동으로 동기화처리가 일어나 비교적 성능이 좋지 않고 무거워 잘 쓰이지 않음
• ArrayList
  - 단방향 포인터 구조로 각 데이터에 대한 인덱스를 가지고 있어 조회 기능에 성능이 뛰어남

3. Map

키(Key), 값(Value)의 쌍으로 이루어진 데이터으 집합.

(순서는 유지되지 않으며 키(Key)의 중복을 허용하지 않으나 값(Value)의 중복은 허용)

• Hashtable
  - HashMap보다는 느리지만 동기화 지원
  - null불가
• HashMap
  - 중복과 순서가 허용되지 않으며 null값이 올 수 있다.
• TreeMap
  - 정렬된 순서대로 키(Key)와 값(Value)을 저장하여 검색이 빠름

4. Queue

List와 유사하다.

 

 

StringBuilder는 string객체를 더하는(+) 것 보다 상대적을 부하가 적고 빠르다.

문자열을 더할 때 새로운 객체를 만들어 더하는 것이 아닌 기존의 데이터에 이어 붙이는 방식이기 때문이다.