https://www.acmicpc.net/problem/10989
10989번: 수 정렬하기 3
첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
www.acmicpc.net
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
출력
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
예제 입력 1 복사
10 5 2 3 1 4 2 3 5 1 7
예제 출력 1 복사
1 1 2 2 3 3 4 5 5 7
[문제 풀이]
HashMap에 key: 수, value: 등장 횟수로 저장한 후, keySet()을 Object 배열로 받아 Arrays.sort()를 이용해 키 값을 정렬한 후 출력해주었는데 이렇게 해결하였더니 시간초과가 났다.
Scanner를 사용하면 시간 초과가 나게 된다. 따라서 BufferedReader를 이용하여 입력을 받고, Arrays.sort()를 이용해 값을 정렬해주었다.
[코드 - 시간 초과, HashMap 이용]
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N =sc.nextInt();
Map<Integer, Integer> map = new HashMap<>();
for(int i=0;i<N;i++) {
int n = sc.nextInt();
if(map.containsKey(n))
map.put(n,map.get(n)+1);
else
map.put(n,1);
}
Object[] obj = map.keySet().toArray();
Arrays.sort(obj);
StringBuilder sb = new StringBuilder();
for(Integer i:map.keySet()) {
for(int j=0;j<map.get(i);j++)
sb.append(i).append("\n");
}
System.out.println(sb.toString());
}
}
[코드 - BufferedReader, Arrays.sort() 이용]
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
int[] num = new int[N];
for(int i=0;i<N;i++) {
num[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(num);
for(int i=0;i<N;i++)
sb.append(num[i]).append("\n");
System.out.println(sb.toString());
}
}
'Algorithm > 백준' 카테고리의 다른 글
[BOJ] 11049: 행렬 곱셈 순서(JAVA) (0) | 2021.10.29 |
---|---|
[BOJ] 1931: 회의실 배정(JAVA) (0) | 2021.10.28 |
[BOJ] 11053: 가장 긴 증가하는 부분 수열(JAVA) (0) | 2021.10.26 |
[BOJ] 14425: 문자열 집합(JAVA) (0) | 2021.10.25 |
[BOJ] 1967: 트리의 지름(JAVA) (0) | 2021.10.22 |