[240222] 알고리즘 리부트 13일차 - 백준 7785 자바

[Part1-Chapter05-Clip01]

 

 

정렬이란, 일반적으로 숫자를 오름차순으로 정렬하거나 문자를 사전 순으로 정렬하는 것을 말한다. 더 나아가 데이터 집합을 적합한 순서로 배치하는 것을 말하는데 이름과 나이의 속성을 가진 객체가 있다면 그 안에서 나이가 어린 사람을 먼저 정렬하고 나이가 같은 경우 이름이 빠른 사람을 먼저 정렬하는 예시를 들 수 있겠다.

 

다양한 정렬 알고리즘과 그 시간 복잡도는 다음과 같다. 삽입 정렬은 그동안 많이 구현해왔고 퀵 정렬의 경우 분할 정복 재귀를 사용하며 면접에서도 많이 질문하는 알고리즘이기도 하다. 병합 정렬과 힙 정렬 구현도 잘 알아두어야 한다. 

 

 

그리고 기본적으로 언어에서도 정렬을 위한 라브러리를 제공하는데 Util 패키지에서 제공하는 Arrays.sort(자바의 Primitive 타입 배열)을 활용하면 숫자는 오름차순으로 문자는 사전 순으로 정렬된다. 리스트 자료 구조를 정렬하기 위해서는 Collections 패키지를 활용한다.

 

라이브러리에서 제공하는 정렬을 사용할 때는 각 정렬 방식이 어떠한 특징을 가지고 있는지 잘 파악하는 것이 중요하다.

 

Primitive []에 적용되는 sort와 Object[]에 적용되는 sort 차이

 

아래 자료에서 보듯이 전자는 추가적인 메모리를 사용하지 않으며 보통의 NlogN보다 좀 더 빠른 성능을 기대해볼 수 있다. 또한 같은 값이면 입력된 순서를 보장하지 않고(unstable) 정렬된다. 후자는 병합 정렬을 기반으로 해서 시간복잡도는 NlogN를 유지하고 같은 값을 가진 경우 입력 값의 순서에 따라 먼저 정렬(stable) 됨을 알 수 있다. 

 

예를 들어 최대 100만개의 정수를 오름차순으로 정렬하는 문제의 경우 int[] 에 담아 정렬하면 최대 N^2의 시간 복잡도를 가지기 때문에 시간 초과를 만나게 된다. 하지만 primitive 타입이 아닌 Integer[]에 담아 정렬하면 최대 NlogN의 시간 복잡도로 문제를 통과하게 된다. 이런 식으로 정렬을 사용하는 것이 유리한지 판단할 수 있다.

 

 

내림차순 정렬의 경우 primitive 배열의 경우 역순으로 출력하는 방법 밖에 없지만, Integer와 같이 Object 배열의 경우 Arrays.sort(objectArr, Collections.reverseOrder()) 를 사용해 내림차순으로 정렬이 가능하다. 그 이유는 해당 메서드가 Comparator 인터페이스를 구현하고 있기 때문이다.

 

 

보다 복잡한 정렬을 구현하고 싶다면 아래와 같이 compare 메서드를 오버라이딩 하여 비교 방식을 직접 선언할 수 있다. (아래는 내림차순을 직접 구현한 것이다.)

 

위 식은 람다식으로도 가능하다. Comparator는 compare 추상 메서드 하나만 가진 함수형 인터페이스이기 때문에  Arrays.sort(objectArray, (o1,o1)-> o2-o1);

 

그 밖에도 사용자가 정의한 객체(다수의 속성을 가진)를 정렬할 때는 Comparable, Comparator를 이용해 정렬 방식을 오버라이딩하여 정렬을 구현할 수 있다. 지속적으로 사용한다면 Comparable을 한 번 사용하고 만다면 Comparator를 구현하는 것이 선호된다. 

 

우측의 경우에도 람다식으로 구현이 가능하다. 

Arrays.sort(students, (o1, o2)->{
	if( o1.age == o2.age){
    	return o1.name.compareTo(o2.name):
    }
    return o1.age-o2.age;
})

 

[Part1-Chapter05-Clip04]

- 백준 7785 회사에 있는 사람

 

 

 

왠지 이 방식으로 풀기를 원하신 건 아닌 것 같긴 한데 간략하게 풀 수 있으려면 set을 이용해야겠다는 생각이 들었다. 다행히도 로그를 기록하기 전에 들어와 있던 사람이 없기 때문에 enter이면 set에 넣어주고  leave이면 set에서 이름을 찾아 꺼내어주면 간단했다. 그 다음은 이 set에 남아있는 사람을 순서가 있는 자료구조에 담아서 정렬하는 것인데... 단 한번도 set에서 꺼내본 적이 없다는 것이 난감했다. 순서가 없는 자료구조임에 따라 인덱스로 접근할 수 없었다. 찾아보니 Iterator를 구현해서 set의 요소를 하나씩 접근할 수 있어서 하나씩 꺼내 다시 자료 구조에 담고 위에서 배운대로 String은 Object 객체 정렬임에 따라 Collections.reverseOrder()를 이용해 역순으로 정렬했다. 

package BaekJoon.sort;

import java.util.*;

public class BJ7785 {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        HashSet<String> names = new HashSet<>();

        while (n-- > 0) {
            String name = sc.next();
            String state = sc.next();

            if (state.equals("enter")) names.add(name);
            else names.remove(name);
        }

        int len = names.size();

        String [] attendList = new String[len];

        // Set은 순서 없이 요소를 저장하는 자료 구조라서
        // Iterator를 이용해서 하나씩 꺼내서 작업할 수 있음!
        Iterator<String> iterator = names.iterator();

        int idx = 0;

        while(iterator.hasNext()){
            attendList[idx++] = iterator.next();
        }

        Arrays.sort(attendList, Comparator.reverseOrder());

        for(int i =0; i<len; i++){
            System.out.println(attendList[i]);
        }

    }
}