문제 : https://www.acmicpc.net/problem/1181

풀이 방법


  1. 첫 번째 시도
    처음에는 간단하게 배열로 입력받은 문자열을 담은 다음에 Comparable을 구현한 클래스를 통해서 정렬을 하려고 했습니다. 하지만, 문자열의 길이순으로는 정렬이 되는데, 문자열의 길이가 같은 경우에는 사전 순으로 먼저 나오는 단어가 출력되고 그 다음 단어가 출력되는 형식으로 결과를 도출해야 합니다. 하지만, 배열을 사용할 경우에 그렇게 하기란 쉽지 않았습니다.
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
import java.io.*;
import java.util.Arrays;

public class BOJ1181 {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


int N = Integer.parseInt(bf.readLine());
Data[] arr = new Data[N];
for(int i=0;i<N;i++){
String input = bf.readLine();
arr[i] = new Data(input,input.length());

}


Arrays.sort(arr);

for(int i=0;i<N;i++)
bw.write(arr[i].name+"\n");

bw.flush();
bw.close();
bf.close();


}

}

class Data implements Comparable<Data>{
String name;
int length;

public Data(String name, int length){
this.name = name;
this.length = length;
}

@Override
public int compareTo(Data o) {
if(this.length>o.length){
System.out.println("here 0");
return 1;
}else if(this.length<o.length){
System.out.println("here -1");
return -1;
}else {
return 0;
}
}
}
  1. 두 번째 방법
    문제를 자세히 읽어보니 이미 나온 단어가 또 나오면 한번만 출력한다고 합니다. 이 뜻은 중복을 허용하지 않는다는 뜻이므로, Set을 이용할 수 있다는 의미입니다. 또한, Set을 이용해서 데이터를 add 하고 나서 List list = new ArrayList<>(set); 을 통해서 Set을 List의 생성자에 대입할 수 있습니다.

그로 인해서 Set이 List가 되어서 Collections.sort를 통해서 입력 받은 문자열들을 먼저 사전순으로 정렬할 수 있습니다. 그 후에, Comparator를 구현하여 문자열의 길이순으로 오름차순 정렬을 수행할 수 있습니다.

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
import java.io.*;
import java.util.*;

public class BOJ1181 {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


int N = Integer.parseInt(bf.readLine());
Set<String> set = new HashSet<>();
for (int i = 0; i < N; i++) {
String input = bf.readLine();
set.add(input);

}

List<String> list = new ArrayList<>(set);

// 일단 사전순으로 먼저 정렬
Collections.sort(list);

// 길이순으로 정렬
// Comparator을 구현함.
// compare 함수를 오버라이드하여 길이로 비교함
Collections.sort(list, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
if (o1.length() > o2.length())
return 1;
else if (o1.length() < o2.length())
return -1;
else
return 0;
}
});


// 출력
for (int i = 0; i < list.size(); i++)
bw.write(list.get(i) + "\n");

bw.flush();
bw.close();
bf.close();


}

}

배운 점


1일 1 알고리즘을 실천하기 위해서 매일 알고리즘을 풉니다. 그리고 지금은 기초 단계이기 때문에 비교적 쉬운 문제이지만 기초를 잘 다져놔야 추후에 난이도 있는 문제도 풀 수 있다고 생각합니다. 오늘처럼 분명 사용해보았지만 기억이 나지 않았던 부분들은 확실하게 기억하고 넘어가야 할 필요가 있습니다.

오늘 나왔었던 개념은 문제를 자세히 읽어보고 어떠한 자료구조를 선택할 것인가를 잘 생각하고 문제를 이해하고 풀어야 한다는 것입니다. 이 부분은 자료구조에 대한 이해력을 더 높이고 공부를 더 해야 할 것 같습니다. 그리고 두 번째로는 Comparable 혹은 Comparator에 대한 내용입니다. 예전에 공부할 때 포스팅해 둔 내용이 있어서 잠깐 참고해서 보았습니다. 하지만, 이 부분도 시간이 지나면서 점차 기억 속에서 잊혀졌기 때문에 다시 한 번 보면서 개념을 상기시켜야 할 것 같습니다!! :)

Comparable or Comparator 내용 : https://woovictory.github.io/2018/03/08/java-collection-framework/