[JAVA / 자바] 백준 1181번 - 단어 정렬
문제
알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.
- 길이가 짧은 것부터
- 길이가 같으면 사전 순으로
입력
첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.
출력
조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다.
문제 접근 방법
해당 문제는 입력을 위 조건에 따라 정렬된 채로 출력하면 되는 문제이다.
이때, 중요한 것은 첫 번째로 입력에 중복이 있을 수 있고 출력에는 중복이 없어야 한다는 것이고, 두 번째로 위 조건에 맞게 정렬해야 한다는 것이다.
첫 번째 고민, 나는 여기서 중복을 언제 걸러낼 것인지를 생각했다.
i) 입력받을 때 중복을 걸러서 배열에 저장한다.
ii) 출력할 때 중복을 걸러서 출력한다.
두 가지 방법이 떠올랐다. 두 방법 다 구현해서 비교해 보도록 하자.
두 번째 고민, 정렬은 어떻게 할까?
배열 정렬 시 자바 내장 함수를 오버로드 해서 사용하는데, 조건에 맞게 함수를 다시 작성해야 한다.
첫 번째로 해당 문자의 길이가 같은지 다른지 판단하여 문자의 길이가 같은 경우만 사전 순으로 비교를 해주고, 만약 문자의 길이가 다르면 길이가 짧은 것이 먼저 오도록 정렬되게 함수를 다시 짜준다.
JAVA 코드 풀이
i) 입력받을 때 중복을 걸러서 배열에 저장
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));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int tC = Integer.parseInt(br.readLine());
ArrayList<String> list = new ArrayList<>();
String temp;
list.add(br.readLine());
while(tC-- > 1){
temp = br.readLine();
if(!list.contains(temp)) // 현재 입력받은 줄에 적힌 문자가 배열에 저장되어있는지 아닌지 확인(중복 방지)
list.add(temp);
}
Collections.sort(list, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
if(o1.length() == o2.length()) // 2. 문자열의 길이가 같으면 사전순으로 정렬
return o1.compareTo(o2);
return o1.length()- o2.length(); // 1. 문자열의 길이가 짧은 것부터
}
});
for(int i=0; i<list.size(); i++)
bw.write(list.get(i)+"\n");
bw.close();
}
}ii) 출력할 때 중복을 걸러서 출력
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));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int tC = Integer.parseInt(br.readLine());
String list[] = new String[tC];
for(int i=0; i<tC; i++)
list[i] = br.readLine();
Arrays.sort(list, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
if(o1.length() == o2.length()) // 2. 문자열의 길이가 같으면 사전 순으로
return o1.compareTo(o2);
return o1.length()- o2.length(); // 1. 문자열의 길이가 짧은 것부터
}
});
bw.write(list[0]+"\n");
for(int i=1; i<list.length; i++)
if(!list[i-1].equals(list[i])) // 중복 체크(정렬된 배열이므로 중복이 있으면 같이 인접해서 나열되어있기 때문에 앞칸과 뒷칸이 같은지 다른지 비교하여 최초 1회만 출력)
bw.write(list[i]+"\n");
bw.close();
}
}코드 실행 결과
후기
처음에 입력으로 중복이 들어올 수 있지만, 출력 때는 중복을 허용하지 않는대서 HashSet을 사용하려고 했었다. 그러나 HashSet은 중복을 허용하지 않는다는 성질도 있지만 정렬을 지원하지 않는다는 성질도 있기 때문에 적절하지 않다고 판단을 했다. 그래서 그다음으로 들었던 생각은 입력에서부터 중복을 판단해서 중복되지 않은 값만 배열에 저장하고 정렬해서 출력하자라는 생각에 코드를 작성했다. 그러나 실행시간이 너무 오래 걸렸고, 다른 사람들이 쓴 코드를 봤다. 보다 보니 유독 실행 시간이 빠른 게 있었는데 바로 나의 두 번째 방법과 같은 중복을 구분하지 않고 입력을 다 배열에 저장하고 그대로 정렬해서 출력 때 중복을 솎아내는 것이다. 왜냐면 정렬 시에 같은 문자면 붙어있게 정렬이 되어있으므로 같은 문자가 반복하는 처음만 출력을 하고 그다음 같은 문자들은 출력하지 않고 그냥 해당 인덱스를 넘겨버리는 방법이다. 중복을 언제 체크하는지 그 차이로 거의 6배의 실행시간 차이가 났다. 첫 번째 방법은 해당 문자가 어디에 저장되어있는지 모르는 채로 입력 때마다 배열 전체를 찾아 판단해야 하는 연산의 복잡함이 있지만 두 번째 방법은 바로 앞의 문자만 비교하여 앞과 같은지 다른지만 판단하면 되기 때문에 훨씬 연산이 간단해진다. 이 차이로 엄청난 실행시간 차이를 보이는 것을 보고 같은 논리여도 코드 순서가 어떻게 되는지에 따라 실행시간 차이에, 코드의 효율에 막대한 영향을 끼친다는 것을 느꼈다.