정렬 관련해서 어제인가? 백준 문제 1302번을 다른 분 티스토리 참고하면서 풀다가 Comparable과 Comparator에 대해 접하게 되었다. 그래서 ㅈㅓ번에 해시맵 잊어버리고 꾸역꾸역 클래스 만들던 것처럼 잊어버리기 전에 정리하기!
Algorithm : Comparable
Comparable
: 기본 정렬 기준(String 사전순, int/long 오름차순)을 구현하는데 사용한다.
- compareTo 함수의 return 값이 양수라면 두 요소의 자리를 바꾼다.
- return 값이 0이거나 음수라면 두 요소의 자리를 바꾸지 않는다.
- 내림차순 정렬을 구현하고 싶다면 if-else문을 사용한다.
ex) if(this.getElement() < cls.getElement()) return -1;
class ClassName implements Comparable<ClassName> {
private int element;
// 생성자, getter, setter 함수 생략
@Override
public int compareTo(ClassName cls) {
return this.getElement() - cls.getElement();
}
}
Comparable 알고리즘 코드
출처 : https://www.acmicpc.net/problem/1431
import java.util.Collections;
import java.util.ArrayList;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
class SerialNumber implements Comparable<SerialNumber> {
private String serialnumber;
private int length;
public SerialNumber() {}
public SerialNumber(String serialnumber, int length) {
this.serialnumber = serialnumber;
this.length = length;
}
public String getSerialnumber() {
return this.serialnumber;
}
public int getLength() {
return this.length;
}
public void setSerialnumber(String serialnumber) {
this.serialnumber = serialnumber;
}
public void setLength(int length) {
this.length = length;
}
@Override
public int compareTo(SerialNumber serialNumber) {
int lenResult = this.getLength() - serialNumber.getLength();
if (lenResult == 0) {
String A = this.getSerialnumber();
String B = serialNumber.getSerialnumber();
A = A.replaceAll("[^0-9]", "");
B = B.replaceAll("[^0-9]", "");
int A_sum = 0, B_sum = 0;
for(int i = 0; i < A.length(); i++)
A_sum += Integer.parseInt(A.split("")[i]);
for(int i = 0; i < B.length(); i++)
B_sum += Integer.parseInt(B.split("")[i]);
int sumResult = A_sum - B_sum;
if(sumResult == 0) {
int alphaResult = this.getSerialnumber().compareTo(serialNumber.getSerialnumber());
return alphaResult;
}
return sumResult;
}
return lenResult;
}
}
public class Main
{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
ArrayList<SerialNumber> list = new ArrayList<SerialNumber>(n);
for(int i = 0; i < n; i++) {
String line = br.readLine();
list.add(new SerialNumber(line, line.length()));
}
Collections.sort(list);
StringBuilder sb = new StringBuilder();
for(int i = 0; i < n; i++)
sb.append(list.get(i).getSerialnumber()).append("\n");
System.out.println(sb);
}
}
반응형
'Programando > Algorithm' 카테고리의 다른 글
정렬: Comparator (0) | 2021.05.27 |
---|---|
탐욕 알고리즘(Greedy Algorithm) (0) | 2021.05.26 |
JAVA 해시맵 사용과 정렬 알고리즘 (0) | 2021.05.25 |
정렬: 병합 정렬 알고리즘 (0) | 2021.05.24 |
JAVA 입출력과 알고리즘 (0) | 2021.05.24 |