[ 코드트리 조별과제 ] 프로그래밍 연습 - Chapter3. 정렬

1. 일반정렬

import java.util.Arrays;
import java.util.Collections;

int n = sc.nextInt();
int[] nums = new int[n];
for(int i = 0; i < n; i++)
    nums[i] = sc.nextInt();

// 오름차순 정렬
Arrays.sort(nums);

// 내림차순 정렬
Integer[] nums2 = Arrays.stream(nums).boxed().toArray(Integer[]::new);
Arrays.sort(nums2, Collections.reverseOrder());

 

내림차순(Collections.reverseOrder)적용을 위한 객체배열로 변환 과정 : 배열의 스트림 생성 -> 박싱(원시타입 요소들을 래퍼클래스 요소들로 변환) -> 객체 배열로 변환

 

// 문자 사전순 정렬
char[] chars = str.toCharArray();
Arrays.sort(chars);
String sortedStr = new String(chars);
System.out.println(sortedStr);

 

문자의 사전순 정렬후 출력 : char배열로 변환한뒤 정렬한다.

 

 

버블정렬 알고리즘

: 인접한 두 요소를 비교하고, 잘못된 순서라면 서로 교환하는 방식을 반복하여 배열을 정렬

while(a>0){
    for(int i=0; i<a-1; i++){
        if(arr[i]>arr[i+1]){
            int temp = arr[i+1];
            arr[i+1] = arr[i];
            arr[i] = temp;
        }
    }
    a--;
}

 

 

단어들의 순서변경시 동일한 단어를 만들수 있는가? ( 애너그램 문제 )

방법1) 구성문자들을 사전순으로 정렬하여 비교(sort)

방법2) 구성문자들의 갯수를 비교(count)

 

두 개의 단어가 입력으로 주어질 때 두 단어에 속하는 문자들의 순서를 바꾸어 동일한 단어로 만들 수 있는지 여부를 출력하는 코드를 작성해보세요.

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str1 = sc.next();
        String str2 = sc.next();

        // 단어1 정렬
        char[] chars1 = str1.toCharArray();
        Arrays.sort(chars1);
        String sortedStr1 = new String(chars1);
		
        // 단어2 정렬
        char[] chars2 = str2.toCharArray();
        Arrays.sort(chars2);
        String sortedStr2 = new String(chars2); 

        if(sortedStr1.equals(sortedStr2))
            System.out.print("Yes");
        else
            System.out.print("No");
    }
}

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str1 = sc.next();
        String str2 = sc.next();

        // 두 단어가 아나그램인지 확인
        boolean isAnagram = areAnagrams(word1, word2);
        
        // 결과 출력
        if (isAnagram) {
            System.out.println("Yes, they are anagrams.");
        } else {
            System.out.println("No, they are not anagrams.");
        }
    }
   
    // 두 단어가 아나그램인지 확인하는 메서드
    public static boolean areAnagrams(String word1, String word2) {
        // 길이가 다르면 아나그램이 아님
        if (word1.length() != word2.length()) {
            return false;
        }
        
        // 각 문자의 개수를 저장할 맵
        Map<Character, Integer> charCountMap = new HashMap<>();
        
        // 첫 번째 단어의 문자 개수 세기, 각 문자의 갯수를 맵에 저장
        for (char c : word1.toCharArray()) {
            charCountMap.put(c, charCountMap.getOrDefault(c, 0) + 1);
        }
        
        // 두 번째 단어와 맵의 비교
        for (char c : word2.toCharArray()) {
        
        	// 맵에 없는 문자가 있으면 아나그램이 아님
            if (!charCountMap.containsKey(c)) {
                return false; 
            }
            
            // 존재하는 단어의 갯수는 감소 -1
            charCountMap.put(c, charCountMap.get(c) - 1);
            
            // 개수가 0이 되면 맵에서 제거
            if (charCountMap.get(c) == 0) {
                charCountMap.remove(c); 
            }
        }
        
        // 최종적으로 모든 문자의 개수가 0이 되었는지 확인
        return charCountMap.isEmpty();
    }
}

 

 

2-3. 객체정렬

객체타입을 순서비교하는 다양한 방법

 

compareTo 메서드

문자열이나 기타 객체를 사전순(lexicographical order) 또는 정의된 순서에 따라 비교할 때 사용된다.

str1.compareTo(str2)

 

• 양수 값: str1이 str2보다 사전순으로 뒤에 있음을 의미합니다.
• 음수 값: str1이 str2보다 사전순으로 앞에 있음을 의미합니다.
• 0: str1과 str2가 동일함을 의미합니다.

// 사전순으로 이름이 가장 느린 사람의 정보를 찾음
Person lastPerson = people[0];

for (int i = 1; i < n; i++) {
	if (people[i].getName().compareTo(lastPerson.getName()) > 0) {
    	lastPerson = people[i];
	}
}

 

 

Comparable 인터페이스

Comparable 인터페이스를 구현하지 않은 객체타입은 compareTo를 사용할 수 없다.

String, 기본 래퍼 클래스들(Integer, Double, Character), java.time 패키지의 날짜와 시간 관련 클래스들( LocalDate, LocalTime, LocalDateTime )은 기본적으로 이를 구현하고 있다.

※ 기본타입인 int 등에는 compareTo를 적용할 수 없음. ( int cannot be dereferenced )

 

사용자정의 클래스타입의 경우 Comparable 인터페이스를 구현하고 compareTo 메서드를 정의하여 정렬순서를 지정할 수 있다.

// 객체 정렬시 이름을 사전순으로 정렬
class Person implements Comparable<Person> {
	...
    @Override
    public int compareTo(Person other) {
        return this.name.compareTo(other.name);
    }
    ...
}

 

 

Arrays.sort 를 통해 정렬할때 compareTo메서드가 자동으로 호출된다.

compareTo 메서드의 반환 값에 따라 정렬작업이 이루어진다. (기본적으로 오름차순으로 정렬)

• 음수 반환: 호출 객체(this)가 비교 대상 객체(other)보다 작다고 간주되어, 호출 객체가 앞에 배치된다.
• 양수 반환: 호출 객체가 비교 대상 객체보다 크다고 간주되어, 호출 객체가 뒤에 배치된다.
• 0 반환: 두 객체가 같다고 간주되어, 순서를 변경하지 않는다.

@Override
public int compareTo(Student student) { // 키를 기준 오름차순 정렬합니다.
    return this.height - student.height;
}

@Override
public int compareTo(Student student) { // 키를 기준 내림차순 정렬합니다.
    return student.height-this.height;
}

 

 

Comparator 인터페이스

객체타입을 하나가 아닌 여러기준으로 정렬하고자하는 경우 사용한다.

각각의 정렬 기준에 대해 별도의 Comparator 구현 클래스를 만들어 사용할 수 있다.

Comparable은 객체 자체에 비교 로직을 구현하는 반면, Comparator는 별도의 클래스에서 비교 로직을 구현한다.

 

이때 compare함수는 compareTo함수와는 다르게 인자를 2개를 받아 기준을 설정한다.( 호출객체의 개념X )

 

import java.util.Scanner;
import java.util.Arrays;
import java.util.Comparator;

class Student {
    String name;
    int height, weight;

    public Student(String name, int height, int weight){
        this.name = name;
        this.height = height;
        this.weight = weight;
    }
};

class StudentComparator implements Comparator<Student> {
    @Override
    public int compare(Student a, Student b) { // 키를 기준 오름차순 정렬
        return a.height - b.height;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Student[] students = new Student[n];
        for(int i = 0; i < n; i++) {
            String name = sc.next();
            int height = sc.nextInt();
            int weight = sc.nextInt();
            students[i] = new Student(name, height, weight);
        }

        // custom comparator를 활용한 정렬
        Arrays.sort(array, new StudentComparator());
        //students.sort(new StudentComparator());

        // 결과를 출력합니다.
        for (int i = 0; i < n; i++){
            System.out.print(students[i].name + " ");
            System.out.print(students[i].height + " ");
            System.out.println(students[i].weight);
        }
    }
}

 

 

 

Arrays.sort 메서드는 인수로 배열과 비교 기준을 전달을 수 있다. Arrays.sort로 정렬을 진행하는 순간에 2번째 인자로 comparator 인터페이스를 정의한다. 

즉 new Comparator<Student>(){} 안에 비교함수인 compare를 override할 수 있다.

import java.util.Scanner;
import java.util.Arrays;
import java.util.Comparator;

class Student {
    String name;
    int height, weight;

    public Student(String name, int height, int weight){
        this.name = name;
        this.height = height;
        this.weight = weight;
    }
};

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Student[] students = new Student[n];
        for(int i = 0; i < n; i++) {
            String name = sc.next();
            int height = sc.nextInt();
            int weight = sc.nextInt();
            students[i] = new Student(name, height, weight);
        }

        // custom comparator를 활용한 정렬
        Arrays.sort(students, new Comparator<Student>() {  
            @Override
            public int compare(Student a, Student b) { // 키를 기준 오름차순 정렬
                return a.height - b.height;
            }
        });

        // 결과를 출력합니다.
        for (int i = 0; i < n; i++){
            System.out.print(students[i].name + " ");
            System.out.print(students[i].height + " ");
            System.out.println(students[i].weight);
        }
    }
}

Arrays.sort(people, new Comparator<Person>(){
    public int compare(Person a, Person b){
        return a.name.compareTo(b.name);
    }
});
System.out.println("name");
for(int i=0; i<5; i++)
    System.out.println(people[i]);

System.out.println();

Arrays.sort(people, new Comparator<Person>(){
    public int compare(Person a, Person b){
        return b.height-a.height;
    }
});
System.out.println("height");
for(int i=0; i<5; i++)
    System.out.println(people[i]);