https://www.acmicpc.net/problem/1181
문제
알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.
- 길이가 짧은 것부터
- 길이가 같으면 사전 순으로
단, 중복된 단어는 하나만 남기고 제거해야 한다.
접근 방법 / 풀이 과정
주어진 입력 예제는 이렇다.
13
but
i
wont
hesitate
no
more
no
more
it
cannot
wait
im
yours단어의 길이가 짧은 것부터 정렬하되 길이가 같다면 사전순으로 정렬하라고 하였다.
1번 조건은 각 단어의 length()로 대조하면 될 것 같다.
2번 조건은 아스키코드로 대조해야겠다고 생각했다. 알파벳 소문자로 이루어졌다고 했으므로
a ~ z까지는 아스키코드로 97 ~ 122이다.
코드로 옮겨보자.
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
int N = Integer.parseInt(bf.readLine());
String[] array = new String[N];
for(int i = 0; i < N; i++)
array[i] = bf.readLine();
Arrays.sort( array , new Comparator<String>(){
@Override
public int compare( String o1 , String o2){
if(o1.length() != o2.length()) {
return o1.length() - o2.length();
}else {
for(int i = 0; i < o1.length(); i++) {
if( o1.charAt(i) > o2.charAt(i)) {
return 1;
}else if(o1.charAt(i) < o2.charAt(i)) {
return -1;
}
}
}
return 0;
}
});
for(int i = 0; i < N-1; i++) {
if(!array[i].equals(array[i+1]))
bw.write( array[i] + "\n");
}
bw.write(array[array.length-1]);
bw.flush();
}
이번에도 Arrays.sort와 comparetor 인터페이스를 사용해서 구현했다.
배열의 i번째 요소와 i+1번째 요소의 문자열 길이 차이를 기준으로 오름차순으로 정렬한다.
만약 길이가 같다면 문자열의 0번째 문자부터 문자열 길이만큼 대조한다.
배열의 i번째 요소의 첫번째 글자와 i+1번째 요소의 첫번째 글자의 아스키코드 크기를 비교하는 것이다.
예를 들어 배열의 0번째 요소는 it이고 배열의 i+1번째 요소가 im가 있다.
두 개의 요소의 첫번째 글자를 보면 i i로 둘 다 같으므로, 두번 째 글자로 넘어간다.
t 와 m이다. 이를 아스키 코드로 나타내면 116과 109로 나타낼 수 있다.
조건은 사전순이므로 im이 it의 앞에 와야한다.
배운점
java 문법 중 인터페이스를 배웠지만, 막상 어디에 사용하는지 잘 감이 오지 않았었다.
compareable과 comparetor 인터페이스를 구현하고 메소드를 오버라이딩 해보면서 유용함을 느꼈다.
알고리즘 문제를 풀다보면 라이브러리에 대한 지식도 쌓여 여러 방면으로 도움이 되는 것 같다.
