문제 url:
단어 정렬
문제:
🤔 문제 알아보기
해당 문제는 이전 문제와 달리 문자열을 입력받아, 조건에 맞게 오름차순으로 정렬하는 문제이다.
문제 조건은 두 개가 있는데
1. 길이가 짧은 것부터 i > it (i가 한 글자로 더 짧다)
2. 길이가 같으면 사전 순 a > b (a가 b보다 먼저 위치한다)
즉, 오름차순으로 푸는데, 길이가 짧은 조건을 정렬시 넣어줘야 한다는 얘기이다.
그럼 해당 문제는 오버로딩 된 sort()메서드 중 아래와 같은 메서드를 사용하고자 한다.
또한 출력 조건이 한 개 존재하는데, 중복된 단어는 하나만 남기고 제거한 상태로 출력을 해야 한다고 한다.
그래서 필자는 중복을 허용하지 않는 Collection인 Set을 이용해서 풀어보겠다.
코드와 함께 같이 설명해보겠다.
🐱👤 실제 코드 1)Set을 활용한
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sbd = new StringBuilder();
int N = Integer.parseInt(br.readLine());
HashSet<String> arr_set = new HashSet<>();
for(int i = 0; i < N; i++) {
arr_set.add(br.readLine());
}
List<String> arr = new ArrayList<>(arr_set);
Collections.sort(arr, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
if(o1.length() == o2.length()) {
return o1.compareTo(o2);
} else {
return o1.length() - o2.length();
}
}
});
for(int i = 0; i < arr.size(); i++) {
sbd.append(arr.get(i)).append("\n");
}
System.out.println(sbd);
}
}
먼저 HashSet을 이용해 데이터를 입력 받는다.
Set의 특징을 간단히 설명하면
- 중복을 허용하지 않는다. (해당 특징 때문에 이번 문제에 사용해봤다)
- 순서를 보장하지 않는다.
- 인덱스를 제공하지 않는다. ( 이는 2번 특징으로 인한 이유이다)
HashSet<String> arr_set = new HashSet<>();
for(int i = 0; i < N; i++) {
arr_set.add(br.readLine());
}
List<String> arr = new ArrayList<>(arr_set);그래서 해당 코드를 보면 HashSet에 중복을 제거하기 위해 받았으며,
순서가 보장되지 않아 ArrayList 배열로 컬랙션 변환을 해주는 것이다.
ArrayList 정리한 자료가 있다. 한번 읽어보면 좋을듯 하다.
ArrayList 객체 생성
자 이제, 정렬을 제외한 나머지 준비는 끝났다. 그럼 정렬을 해보도록 하겠다.
아까 위에서 설명했듯, 해당 sort()메서드를 사용하고자 한다.
Collections.sort(arr, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
if(o1.length() == o2.length()) {
return o1.compareTo(o2);
} else {
return o1.length() - o2.length();
}
}
});객체를 비교하기 위해 Comparator 인터페이스를 익명함수로 생성하였고,
o1과 o2의 길이를 비교해 만약 같으면 사전 순으로 비교하기 위해
o1.compareTo(o2)를 반환한다.
그럼 compareTo는 무엇인가?
compareTo는 String 클래스에 존재하는 메서드로, 자기 자신(여기서는 o1)과 다른 문자열인 o2를 비교하는 로직을 담당한다.
그러고 만약 같지 않다면! o1.length - o2.length를 실시하는데,
왜 이런 형태일까? 할 수 있다.
이것은 sort()메서드를 잘 들어다보면 알 수 있다.
만약 a와 b가 존재하는데, 이를 오름 차순으로 하고싶다면 어떻게 해야 할까?
a < b인 상태라고 가정하자, 만약 a-b를 하게 된다면 음수가 나올 것이다. 그럼 이는 a가 b보다 작기 때문에 현재 오름 차순인 것을 알 수 있다. 이를 이용해서 풀어보자면
a, b를 오름차순 정렬 단, a < b인 상태
- a - b < 0 즉, b가 a보다 크기 때문에 a, b
- a - b == 0 즉, a와 b가 같은 값이기에 a, b
- a - b > 0 즉, a가 b보다 크기 때문에 b, a
이렇게 오름차순 기준을 정할 수 있다.
그렇다면 왜 o1.length - 02.length를 해준 것인지 이해할 것이다.
🤢 코드 리팩토링
역시 Set을 사용하지 않는 방법이 존재할 것이라 생각했는데, 존재한다.
이를 또 타 블로그를 보고 공부해보고자 한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sbd = new StringBuilder();
int N = Integer.parseInt(br.readLine());
String[] arr = new String[N];
for(int i = 0; i < N; i++) {
arr[i] = br.readLine();
}
Arrays.sort(arr, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
if(o1.length() == o2.length()) {
return o1.compareTo(o2);
} else {
return o1.length() - o2.length();
}
}
});
System.out.println(arr[0]);
for(int i = 1; i < arr.length; i++) {
if(!arr[i].equals(arr[i-1])) {
sbd.append(arr[i]).append("\n");
}
}
System.out.println(sbd);
}
}
맨 아래 출력부분을 보면 이해할 수 있는데,
System.out.println(arr[0]);
for(int i = 1; i < arr.length; i++) {
if(!arr[i].equals(arr[i-1])) {
sbd.append(arr[i]).append("\n");
}
}즉, 이전값과 현재값이 같지 않다면(연속적이지 않다면)
StringBuilder에 append하라는 얘기이다.
그러면 연속될 때 맨 처음 나왔던 값만 저장되고 그 이후값들은 저장되지 않기 때문에
이렇게 중복값을 제거할 수 있다.
맨 위에(352ms)가 Set을 사용하지 않은 것
밑에(400ms)가 Set을 사용한 것
속도 차이가 좀 있는 것을 볼 수 있다.
