Comparable과 Comparator
정렬을 하기전 인터페이스인 comparable과 comparator에 대해서 알아야할 필요가 있다.
Comparable 인터페이스를 쓰려면 compareTo 메소드를 구현해야하고 Comparator 인터페이스를 쓰려면 compare 메소드를 구현해야한다.
[두 수의 비교 결과에 따른 작동 방식]
음수일 경우 : 두 원소의 위치를 교환 안함
양수일 경우 : 두 원소의 위치를 교환 함
Comparable (compareTo)
: 자기 자신과 매개 변수 객체를 비교
lang 패키지 (import 불필요)
public class ClassName implements Comparable<Type> {
/*
...
code
...
*/
// 필수 구현 부분
@Override
public int compareTo(Type o) {
/*
비교 구현
*/
}
}주의 할 점
두 수의 대소비교를 위해 두수의 차로 리턴할때 뺄셈과정에서 자료형의 범위를 초과할 수 있기때문에 주의해야한다.
Comparator (compare)
: 두 매개변수 객체를 비교
일반적인 정렬기준이 아닌 기준으로 정렬하고 싶은경우 (문자열의 길이등)
util 패키지에 있음 (util import)
import java.util.Comparator; // import 필요
public class ClassName implements Comparator<Type> {
/*
...
code
...
*/
// 필수 구현 부분
@Override
public int compare(Type o1, Type o2) {
/*
비교 구현
*/
}
}익명객체(클래스)활용하기
특정 구현 부분만 따로 사용하거나 부분적으로 기능을 일시적으로 바꿔야할 경우 사용함
=>compareTo만 사용하고 싶을때
sort의 배열과 comparator를 파라매터로 갖는 것을 이용한다
Collections.sort()도 마찬가지이다.
import java.util.Arrays;
import java.util.Comparator;
public class Test {
public static void main(String[] args) {
MyInteger[] arr = new MyInteger[10];
// 객체 배열 초기화 (랜덤 값으로)
for(int i = 0; i < 10; i++) {
arr[i] = new MyInteger((int)(Math.random() * 100));
}
// 정렬 이전
System.out.print("정렬 전 : ");
for(int i = 0; i < 10; i++) {
System.out.print(arr[i].value + " ");
}
System.out.println();
Arrays.sort(arr, comp); // MyInteger에 대한 Comparator을 구현한 익명객체를 넘겨줌
// 정렬 이후
System.out.print("정렬 후 : ");
for(int i = 0; i < 10; i++) {
System.out.print(arr[i].value + " ");
}
System.out.println();
}
static Comparator<MyInteger> comp = new Comparator<MyInteger>() {
@Override
public int compare(MyInteger o1, MyInteger o2) {
return o1.value - o2.value;
}
};
}
class MyInteger {
int value;
public MyInteger(int value) {
this.value = value;
}
}이런식으로 구현한 익명 객체를 이용하여 정렬기준을 만들어 sort해줄 수 있다.
백준 10825 : 국영수
a.compareTo(string b) : 사전순으로 같다면 0 a가 b보다 뒷순서면 양수, 아니면 음수
import java.io.*;
import java.util.*;
public class Main {
static int n,m;
static String[][] info;
static Scanner scan=new Scanner(System.in);
static StringBuilder sb=new StringBuilder();
public static void main(String[] args) {
n=scan.nextInt();
info=new String[n][4];
for(int i=0;i<n;i++) {
info[i][0]=scan.next(); //이름
info[i][1]=scan.next(); //국어
info[i][2]=scan.next(); //영어
info[i][3]=scan.next(); //수학
}
Arrays.sort(info,comp);
for(int i=0;i<n;i++) {
System.out.println(info[i][0]);
}
}
static Comparator<String[]> comp =new Comparator<String[]>() {
@Override
public int compare(String[] o1,String[] o2) {
if(Integer.parseInt(o1[1])>Integer.parseInt(o2[1])) {
return -1;
}else if (Integer.parseInt(o1[1])==Integer.parseInt(o2[1])) {
if(Integer.parseInt(o1[2])<Integer.parseInt(o2[2])) {
return -1;
}
else if(Integer.parseInt(o1[2])==Integer.parseInt(o2[2])) {
if(Integer.parseInt(o1[3])>Integer.parseInt(o2[3])) {
return -1;
}else if(Integer.parseInt(o1[3])==Integer.parseInt(o2[3])) {
if(o1[0].compareTo(o2[0])<0) {
return -1;
}
}
}
}
return 1;
}
};
}comparator를 사용하여 익명객체 생성하고 sort 해줬다. 조건을 줄때 -1로 통일하고 맨바깥을 -1로 줘서 중복코드를 줄였다. 근데 더 헷갈림 !!!
이게 진정 실버4인가 ㅠㅠ
백준 1015 : 수열 정렬
A의 원소들이 p에 대응하는 index의 값을 index로 갖는 배열이 B라는 뜻이다.
B[P[i]]=A[i] 이다.
0 3 1 4 2
import java.io.*;
import java.util.*;
public class Main {
static int n,m;
static int[][] a;
static int[] b;
static Scanner scan=new Scanner(System.in);
static StringBuilder sb=new StringBuilder();
public static void main(String[] args) {
//입력받기
n=scan.nextInt();
a=new int[n][2];
b=new int[n];
for(int i=0;i<n;i++) {
a[i][0]=scan.nextInt(); //입력 받는 값
a[i][1]=i;//index 값
}
//정렬
Arrays.sort(a,comp);
//오름차순으로 정렬한 a를 인덱스로 갖는 배열 b 생성
for(int i=0;i<n;i++) {
b[a[i][1]]=i;
}
//출력
for(int j=0;j<n;j++) {
sb.append(b[j]+" ");
}
System.out.print(sb);
}
static Comparator<int[]> comp =new Comparator<int[]>() {
@Override
public int compare(int[] o1,int[] o2) {
if(o1[0]<o2[0]) {
return -1;
}else if(o1[0]>o2[0]) {
return 1;
}else {
if(o1[1]<o2[1]) {
return -1;
}
else {return 1;}
}
}
};
}왜틀?????????????????????????????????????????????????려?????????????????????????
와 진짜 comparator 조건 줄때 o1 <o2 해줘야되는데 1 해줘서 몇시간을 헤맸다 바본가 진짜
백준 11652 : 카드
import java.io.*;
import java.util.*;
public class Main {
static int n,m;
static long[] arr;
static int[] b;
static Scanner scan=new Scanner(System.in);
static StringBuilder sb=new StringBuilder();
public static void main(String[] args) {
//입력받기
n=scan.nextInt();
arr=new long[n];
for(int i=0;i<n;i++) {
arr[i]=scan.nextLong(); //입력 받는 값
}
Arrays.sort(arr);
int cnt = 1;
int max = 1
int maxIdx = 0;
for(int i = 1; i < n; i++) {
if(arr[i] == arr[i-1]) cnt++;
else cnt = 1;
if(cnt > max) {
max = cnt;
maxIdx = i;
}
}
System.out.print(arr[maxIdx]);
}
}수범위가 int형을 초과하므로 long형으로 sort해준뒤 cnt해주면된다
급격히 쉬워진 난이도
백준 15970: 화살표 그리기
import java.io.*;
import java.util.*;
public class Main {
static int n,p,cnt=0;
static int[][] arr;
static Scanner scan=new Scanner(System.in);
static StringBuilder sb=new StringBuilder();
public static void main(String[] args) {
//입력받기
n=scan.nextInt();
arr=new int[n][2];
for(int i=0;i<n;i++) {
arr[i][0]=scan.nextInt(); //위치
arr[i][1]=scan.nextInt(); //색갈
}
//색갈별로 정렬한 후
Arrays.parallelSort(arr,comp);
// for(int i=0;i<n;i++) {
// System.out.println(arr[i][0]+" "+arr[i][1]);
// }
boolean flag =false;
for(int i=1;i<n;i++) {
if(arr[i][1]==arr[i-1][1]) {//색갈이 같으면
if(i==1) {
cnt+=arr[i][0]-arr[i-1][0];
}
if(i==n-1) {//마지막이면
int d=arr[i][0]-arr[i-1][0];
cnt+=d;
}
else if(arr[i][1]==arr[i+1][1]) {//중간위치면
int min=100000;
int a=arr[i][0]-arr[i-1][0];
int b=arr[i+1][0]-arr[i][0];
min=Math.min(a, b);
cnt+=min;
}
else if(arr[i][1]!=arr[i+1][1]) { //색갈 다를때
int c=arr[i][0]-arr[i-1][0];
cnt+=c;
}
}
else { //경계부분
cnt+=arr[i+1][0]-arr[i][0];
}
}
System.out.print(cnt);
}
static Comparator<int[]> comp =new Comparator<int[]>() {
@Override
public int compare(int[] o1,int[] o2) {
if(o1[1]<o2[1]) {
return -1;
}else if(o1[1]>o2[1]) {
return 1;
}else {
if(o1[0]<o2[0]) {
return -1;
}
else {return 1;}
}
}
};
}조건을 놓치지 않도록 조심하면 쉽게 풀 수있는 문제!
백준 1181 :단어정렬
import java.io.*;
import java.util.*;
public class Main {
static int n,p,cnt=0;
static String[][] arr;
static Scanner scan=new Scanner(System.in);
static StringBuilder sb=new StringBuilder();
public static void main(String[] args) {
//입력받기
n=scan.nextInt();
arr=new String[n][2];
for(int i=0;i<n;i++) {
String str=scan.next();
String length=Integer.toString(str.length());
arr[i][0]=str; //글자
arr[i][1]=length; //글자의 길이
}
//길이가 짧은것부터
//길이가 같으면 사전순으로
Arrays.parallelSort(arr,cmp);
System.out.println(arr[0][0]);
for(int m=1;m<n;m++) {
if(!arr[m][0].equals(arr[m-1][0])) {
System.out.println(arr[m][0]);
}
}
}
static Comparator<String[]> cmp=new Comparator<String[]>(){
@Override
public int compare(String[] o1,String[]o2) {
if(Integer.parseInt(o1[1])<Integer.parseInt(o2[1])) {
return -1;
}else if(Integer.parseInt(o1[1])>Integer.parseInt(o2[1])) {
return 1;
}
else if(Integer.parseInt(o1[1])==Integer.parseInt(o2[1])) {
return o1[0].compareTo(o2[0]);
}
else return 1;
}
};
}중복되는 문자열을 제거하는데에 애먹었다ㅜㅜ 이부분(출력하는부분) 다시보기!!
백준 20291 : 파일정리
import java.io.*;
import java.util.*;
public class Main {
static int n,p,cnt=1;
static String[] arr;
static Scanner scan=new Scanner(System.in);
static StringBuilder sb=new StringBuilder();
public static void main(String[] args) {
//입력받기
n=scan.nextInt();
arr=new String[n];
for(int i=0;i<n;i++) {
String str=scan.next();
int index=str.indexOf('.');
String str2 = str.substring(index+1,str.length());
arr[i]=str2; //확장자명
}
//정렬
Arrays.sort(arr);
//중복 있는지 확인하고 cnt
for(int j=0;j<n;) {
int cnt=1;
int k;
for(k=j+1;k<n;k++) {
if(arr[j].equals(arr[k]))cnt++; //같은 경우 cnt
else break;
}
sb.append(arr[j]+" "+cnt+"\n");
j=k;
}
System.out.println(sb.toString());
}
static Comparator<String> cmp=new Comparator<String>(){
@Override
public int compare(String o1,String o2) {
if(o1.compareTo(o2)<0) {
return -1;
}
else return 1;
}
};
}- string 자르는 방법을 알고있나요?
- 중복된 것을 빼고 갯수를 출력 할 수 있나요 ?(실제 해보기)
다할 수있으면 패스 아니면 다시해보기
프로그래머스 k번째수
import java.util.*;
class Solution {
public int[] solution(int[] array, int[][] commands) {
int[] answer = new int[commands.length];
for(int i=0;i<commands.length;i++){
answer[i]=subint(array,commands[i][0],commands[i][1],commands[i][2]);
}
return answer;
}
static int subint(int[] array,int start,int end,int num){
int[] arr= new int[end-start+1];
int a=0;
for(int i=start;i<end+1;i++){
arr[a]=array[i-1];
a++;
}
Arrays.sort(arr);
return arr[num-1];
}
}프로그래머스 H-index
import java.util.*;
class Solution {
public int solution(int[] citations) {
int answer = 0;
Arrays.sort(citations);
if(citations[citations.length-1]==0) return 0;
for(int i=0;i<citations.length;i++){
if(citations[i]>=citations.length-i){
return citations.length-i;
}
}
return 1000;
}
}
남기고 싶은 개발자입니다 :>