Codeforces 풀이를 위한 JAVA 문법 정리-3

시작

마지막으로 Java에서 활용할 수 있는 자료구조들과 정렬 방법에 대해 알아보겠습니다.

 

Stack

Stack의 가장 큰 특징인 Last In First Out 을 기억하고 있으면 해당 자료구조의 동작이 쉽게 이해될 것이라 생각합니다. 

즉, 먼저 들어간 자료가 나중에 나오는 구조입니다. 

Stack에 가장 기본적인 문제로 boj.kr/10828 문제가 있습니다. 

이 문제는 Stack에 대해 이해하고 제공하고 있는 함수에 대해 활용할 수 있는지 확인하는 문제입니다.

 

ArrayList

Java에서 ArrayList는 List 인터페이스를 상속받은 클래스로 일반 배열과는 달리 가변적으로 데이터를 저장할 수 있는 선형리스트 입니다. 

즉, 배열과 달리 ArrayList 객체들이 추가되어 저장 용량을 초과하면 자동으로 부족한 만큼 저장 용량을 늘립니다. 

 

HashMap

Java에서 HashMap은 Map인터페이스를 상속하고 있기 때문에 Map 성질을 그대로 가지고 있습니다. 

Map의 구조가 Key, Value 형태이기 때문에 HashMap도 같은 구조를 가지고 있습니다. 

여기서 주의해야할 점은 값은 중복으로 저장할 수 있지만 키는 중복으로 저장할 수 없습니다. 

HashMap에서 Hashing을 사용하고 있기 떄문에 데이터를 검색하는데 O(1) 안에 수행할 수 있습니다. 

HashMap의 경우에 프로그래머스에 완주하지 못한 선수 문제를 풀어보게 되면 단번에 느낌이 올것입니다.

(*HashSet의 경우에는 입력 시 중복 입력 된 수를 제외하고 저장됩니다. )

 

Queue

Java에서 Queue는 Stack과 다르게 First In First Out의 형태를 가집니다. 먼저 들어온 데이터가 가장 먼저 나가는 구조를 갖습니다. 

BFS 알고리즘을 해결할 때 많이 사용하게 되며 boj.kr/1260 문제를 해결해보면서 Queue 사용법을 쉽게 익혀볼 수 있습니다.

 

정렬

배열에 대한 정렬에 대해 우선 살펴보겠습니다. 

Arrays.sort 기본 정렬은 오름차순 입니다. 

반대로 내림차순을 수행하기 위해서는 Wrapper 클래스를 사용해줘야 합니다. 

 

배열에 대한 정렬이 아니라 기본 자료형의 Wrapper 클래스의 객체들을 이용해야 하는 경우 Collections.sort를 사용하게 됩니다. 

Comparable : 객체 간의 일반적인 정렬이 요구될 때 사용합니다.
                        Comparable 인터페이스를 확장해서 compareTo() 메소드를 구현하게 됩니다. 

Comparator : 객체 간의 특정한 정렬이 요구될 떄 사용합니다. 
                        Comparator 인터페이스를 확장해서 compare() 메소드를 구현하게 됩니다. 

Collections.sort 를 하는데 두번째 인자에 바로 인라인으로 삽입하여 사용할 수 있습니다. 

이는 익명 클래스에 주로 사용하는데, 코드 중간 마다 정렬 기준이 달라질 수 있기 때문입니다. 

Comparator 구조를 사용하게 됩니다. 

 

이번에는 클래스를 생성해서 Comparable 를 상속 받아서 compareTo 함수를 오버로딩 하는 구조로 사용해보겠습니다. 

 

이 두 방법을 이용해 백준 문제에서 바로 활용해 보겠습니다. 

두 문제다 간단히 정렬만 해주면 해결할 수 있습니다. 

 

boj.kr/11650 : 익명 클래스에 Comparator을 사용합니다. 

 

boj.kr/11651 : Comparable을 사용합니다.