728x90
문제풀이
이번 문제는 정렬 알고리즘 문제입니다.
입력으로 들어오는 문자열을 주어진 조건에 맞게 정렬하는 방법에 대해 알아보고자 합니다.
코딩테스트에서 정렬만을 단독으로 물어보는 문제는 거의 출제되지 않고 주로 정렬을 사용해서 어떤 다른것을 해라~
이런식으로 주어지기 때문에 단순 정렬이 아닌 길이순, 사전순, 이나 사용자 클래스를 만들어서 정렬 과같은 방법을 모두 알 익혀두어야 합니다.
문제를 풀때 정렬을 직접 구현해서 사용해도 되지만 Collection.sort(), Arrays.sort()를 사용하는것이 시간상 더 효율적이라고 생각합니다.
1. sort 함수 호출할때 정렬 방법 선택하기
2. 사용자 정의 클래스를 만들어서 toCompare 함수 override 하기
다음의 두 가지를 이용해서 문제를 풀어보겠습니다.
소스코드를 참고해 주세요.
소스코드
방법1
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
import java.io.*;
import java.util.*;
public class Main {
static int n;
static Map<String, Integer> map = new HashMap<>();
public static void main(String[] args) throws Exception, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
n = Integer.parseInt(br.readLine());
for(int i=0;i<n;i++)
{
map.put(br.readLine(), 1);
}
String[] arr = new String[map.size()];
int idx = 0;
for(String key : map.keySet())
{
arr[idx++] = key;
}
Arrays.sort(arr, new Comparator<String>(){
public int compare(String a, String b)
{
if(a.length() < b.length()) return -1;
else if(a.length() > b.length()) return 1;
else {
return a.compareTo(b);
}
}
});
for(int i=0;i<arr.length;i++)
{
sb.append(arr[i]).append('\n');
}
System.out.println(sb);
}
}
|
cs |
방법2
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
import java.io.*;
import java.util.*;
public class Main {
static int n;
static Map<String, Integer> map = new HashMap<>();
public static void main(String[] args) throws Exception, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
n = Integer.parseInt(br.readLine());
for(int i=0;i<n;i++)
{
map.put(br.readLine(), 1);
}
String[] arr = new String[map.size()];
int idx = 0;
for(String key : map.keySet())
{
arr[idx++] = key;
}
List<MyString> list = new ArrayList<>();
for(int i=0;i<arr.length;i++)
{
list.add(new MyString(arr[i]));
}
Collections.sort(list);
for(int i=0;i<list.size();i++)
{
sb.append(list.get(i).str).append('\n');
}
System.out.println(sb);
}
}
class MyString implements Comparable<MyString>{
String str;
public MyString(String s)
{
str = s;
}
@Override
public int compareTo(MyString mString)
{
if(str.length() < mString.str.length()) return -1;
else if(str.length() > mString.str.length()) return 1;
else{
return str.compareTo(mString.str);
}
}
}
|
cs |
https://www.acmicpc.net/problem/1181
1181번: 단어 정렬
첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.
www.acmicpc.net
LIST
'Programming > Algorithm' 카테고리의 다른 글
| [Tree] BOJ 10610번, 트리의 지름(JAVA) (0) | 2021.11.04 |
|---|---|
| [Sort] BOJ 10610번, 30(JAVA) (0) | 2021.11.01 |
| [Topology Sort] BOJ 2252번, 줄 세우기(JAVA) (0) | 2021.10.29 |
| [Kruskal MST] BOJ 1197번, 최소 스패닝 트리(JAVA) (0) | 2021.10.29 |
| [BFS] BOJ 2583번, 영역 구하기(JAVA) (0) | 2021.10.28 |