KOMAS

https://www.acmicpc.net/problem/2448

• 문제 이해
• 해결 방법
• 구현 코드

문제 이해

이전에 풀었던 별 찍기 - 10번 문제와 비슷한 형태였다.

3 * 2^N을 (3, 6, 12, 24, 48...)인 수를 입력받아서 삼각 형안에 삼각형 형태로 별을 재귀적으로 찍으면 된다.

문제의 예제로 봤을 때 입력된 수는 높이가 되고, 너비는 높이 * 2인 것을 알아챌 수 있었다.

그리고 대략적으로 윗 삼각형은 현재 높이의 2로 나누어지는 부분이고, 아랫 삼각형 두개는 현재 너비를 2로 나누어

두 부분으로 나누어져 재귀적으로 그려지는 것을 대략적으로 파악한 후 문제 해결 방법을 생각하였다.

해결 방법

처음 생각은 정가운데에 어떻게 index를 찾아서 별을 찍을까 고민하다가 가장 작은 삼각형의 형태인

높이가 3일때에 높이와 너비 index에 빼는 방식으로 별을 찍으면 찍을 수 있을 것 같았고 그 방법으로

별을 찍어 문제를 해결했다. 그러므로 재귀 함수의 종료 조건은 높이가 3이므로 size가 3일 때 종료되게끔 하였다.

이러한 문제 유형은 2차원 배열을 입력의 크기만큼 생성해두고 index 조정만 잘해준다면 문제없이 풀 수 있는 문제이다.

가장 오른쪽 끝, 맨 밑의 index를 알아내어 그 부분부터 index를 빼서 별을 찍을 생각이었으므로

끝 값 index에 현재 해당되는 size만큼 빼주면 쉽게 재귀적으로 높이와 너비 부분을 인자로 넣어 재귀 함수를 호출할 수 있다.

가장 먼저 재귀 함수내에서 현재 size를 2로 나누어 간격으로 활용하였다.

예를 들어 24가 입력으로 들어오면 간격은 12가 되어 현재 간격으로 높이와 너비를 적절히 빼주면 된다.

가장 윗 삼각형은 높이가 반으로 줄어드므로 현재 높이(24) - 간격(12)으로 처리해주었다.

너비는 총 48이고 4분의3 지점이 오른쪽 끝이 되므로 현재 너비(48) - 간격(12)으로 처리했다.

아래 두개의 삼각형은 높이는 가장 아래를 사용할 것이기 때문에 그대로 사용하고,

너비는 현재 너비(48) - 간격 * 2(24)로 첫 번째 아래 삼각형을 재귀 호출하고,

두 번째 아래 삼각형은 높이와 너비를 그대로 사용하면 되었다.

종료 조건에서 별을 찍을 때는 높이와 너비가 가장 아래, 가장 오른쪽이 들어왔으므로 적절히 빼주어 삼각형을 그려주게끔 하였다.

index는 크기를 기준으로 사용했으므로 -1을 추가로 더해주면 알맞게 찍힌다.

출력을 할 때 System.out.println()을 쓰면 시간초과가 걸려서 BufferedWriter를 사용했다.

구현 코드

https://www.acmicpc.net/problem/7576

• 문제 이해
• 해결 방법
• 구현 코드

문제 이해

기본적으로 BFS를 이용한 위, 아래, 좌, 우를 0이면 1로 바꾸는 Flood fill 문제인 것은 알 수 있었다.

이 문제는 BFS의 기본 문제들과는 다르게 Flood fill의 시작 위치가 여러 개인 점이 기본 문제와는 달랐다.

Queue의 특성상 시작 토마토의 위치들인 1인 지점들을 bfs 함수를 실행 하기 이전에 전부 미리 넣어준 후

bfs를 하면 될 것 같다는 점은 쉽게 파악할 수 있었다.

그 이후 bfs를 이용해 기존하던 방식으로 각 상자에서 토마토가 1이므로 1의 주변을 익어가게끔 하면 되는 문제였다.

-1인 벽을 처리해주어야 하는 요구사항이 있지만 어차피 bfs를 할 때 0인 조건만 1로 만들어주면 되므로 0일 때만

새로운 토마토 객체를 생성해주면 되었다.

해결 방법

bfs를 실행하기 이전에 시작 토마토들인 1의 위치를 전부 Queue에 넣어 주어주어야 했다.

넣어주는 과정은 입력을 받는 과정에서 1이라면 Queue에 행, 열 위치를 알 수 있는 토마토 객체를 생성하여 넣어주었다.

추가로 토마토 객체를 생성할 때 인스턴스 변수로 며칠이 지났는지 확인할 수 있는 day를 만들어 주었다.

새로운 객체를 생성할 때 현재 Queue에서 꺼낸 반복문을 돌아가는 객체의 day 인스턴스 변수에 +1 만 해서 새로 객체를 생성할 때 지정해준다면

새로운 토마토가 생성될 때마다 이전 토마토의 day에 +1을 하므로 최소일 수를 알 수 있다.

최소일수를 알고자 할 때 모든 객체의 day의 max를 계산하면 시간이 추가로 걸리므로 이 방법보다는 전역 변수에 day를 선언해두고

가장 마지막에 생성되는 객체의 day를 전역변수 day에 저장한다면 그것이 마지막 익는 토마토의 날짜가 될 것이다. 

bfs는 2차원 배열을 탐색할 때 자주 처리해주는 2차원 배열의 범위를 벋어 나지 않게 설정해주고, 0이면 토마토 객체를 생성하고

그 부분을 1로 바꿔주어 다시 Queue에 생성되지 않도록 하였다. 0 일 때만 처리하므로 -1 인 벽을 신경 써주지 않아도 된다.

구현 코드

https://www.acmicpc.net/problem/2447

• 문제 이해
• 해결 방법
• 코드 구현

문제 이해

금방 해결할 수 있을 줄 알았는데 생각보다 시간이 걸린 문제다.

일단 문제 자체에서 재귀적인 패턴으로 해결하라고 명시되어있다.

아마 명시되어있지 않더라도 문제를 읽어보면서 3^n이 입력으로 들어오는 조건이 있을 때 입력/3으로 나누어지니 재귀를 파악할 순 있다.

예를 들어 입력이 27이라면 별이 그려지는 부분이 27 -> 9 -> 3 -> 1으로 3으로 나누어져 그려지므로

재귀적인 방법을 사용해야 한다는 걸 금방 알아챌 수 있을 것이다.

해결 방법

일단 3^N인 수를 입력받으면 행 3개, 열 3개 총 9개 부분으로 나눈 후 재귀적으로 해결해야 한다.

그러므로 재귀 함수의 선언부를 (행의 마지막 위치, 열의 마지막 위치, 3으로 나눌 size)로 만들었다.

행, 열을 마지막 위치가 아닌 시작 위치로 해도 무관하다.

중요한 점은 3으로 나눈 size만큼 더해주거나 빼주면서 아홉 부분을 재귀 함수를 호출한다는 것이다.

9                            
3,        6,        9
1, 2, 3  4, 5, 6  7, 8, 9

여기서부터 size/3을 간격이라고 하겠다.

입력이 9라고 예를 들면 3^n을 입력으로 받으므로 9에서 간격인 3씩 빼는 방식을 선택했다. 이 숫자를 행, 열 따로 재귀적으로 넘겨주면 된다.

직접 구현해보진 않았지만 3, 6, 9로 넘겨주지 않고 시작 위치부터 간격을 더하면서 1, 4, 7을 함수의 인자로 넘겨줘도 해결될 것 같다.

구현하면 반복이 될 때마다 행과 열을 간격만큼 빼주면서 총 9 부분을 호출하도록 이중 반복문을 사용했다.

그리고 정 가운데 부분은 별을 그리지 않을 것이므로 정 가운데 부분에 해당되는 부분은 재귀 함수를 호출하지 않도록 했다.

재귀 함수의 종료 조건은 size가 1이 되면 재귀 함수를 종료하게 끔 하였다.

행, 열의 크기가 1이므로 이 부분에서 전역 변수로 선언된 2차원 배열[입력 크기][입력 크기]에 별을 그려주면 된다.

급하게 생각하지 말고 2차원 배열의 index를 유지시키면서 해당 행과 열 지점을 재귀 함수로 넘겨 호출을 해주고

재귀 함수의 종료 조건만 잘 지정해준다면 풀렸던 문제였다.

결국 중요한건, for문을 이용한 index 증감 조절을 잘해주면 된다. 

이 외에도 재귀 함수를 이용한 비슷한 문제들이 백준에 있는데

재귀 함수 호출 시에 넘겨줄 index만 잘 생각해서 범위 조정해준다면 전부 해결할 수 있다.

코드 구현

[JAVA] 자바 오버 로딩 (Overloading)

하나의 클래스 안에서 여러 개의 같은 이름의 메서드를 여러 개 정의하는 것을 오버 로딩이라고 합니다.

이름이 같은 함수가 여러 개의 인자를 갖고 있는 것처럼 보여서 과적되었다고 표현하는 것입니다.

오버 로딩은 조건이 필요한데, 3가지를 기억하시면 됩니다.

• 메서드의 이름이 같아야 한다.
• 매개변수의 개수 또는 타입이 달라야 한다.
• 반환 타입이 다른 것은 오버 로딩에 영향을 미치지 않는다.

결국 오버 로딩이란 메서드들의 이름은 같지만, 매개변수의 개수 또는 타입이 달라질 때 사용하는 것입니다.

주의해야 할 점은 반환 타입이 다르다고 할지라도 이름과 매개변수가 같으면 같은 함수로 인식된다는 점입니다.

반환 타입은 오버 로딩에 영향을 주지 않습니다.

반환 타입은 넘겨주는 쪽에서 제대로 된 타입만 넘겨준다면, 받는 쪽에서 형 변환을 통해 사용할 수 있기 때문입니다.

실습 코드

매개변수의 숫자를 더하는 함수로 add 함수를 만들어놓고,

추가적으로 오버 로딩하여 타입이 다른 경우와 개수가 다른 경우를 테스트해보시면 함수의 이름이 같다고

하더라도 오버 로딩이 적용되어 올바르게 작동하는 점을 보실 수 있습니다.

반환 타입만 바꾼 경우

같은 함수의 이름과 매개변수를 같게 하여 반환 타입만 바꿔본 경우입니다. 같은 함수로 인식되어 오류가 발생합니다.

반환 타입만 바꾼다고 해서 오버 로딩이 되지 않으며 컴파일 오류가 발생합니다.

기변 매개변수

자바에서 함수의 매개 변수의 개수를 바꿔가며 줄 때 함수의 매개 변수의 선언부에 타입... 변수라고 지정해주면

타입만 맞다면 최대 개수의 255개 내에서 제한없이 함수를 호출할 수 있습니다. 사실 배열 타입으로 선언된 매개변수입니다.

주의할 점은 기본 매개변수와 같이 사용한다면 항상 선언부의 맨 뒤에 와야 합니다.

오버 로딩의 개념 자체는 어렵지 않으며, 오버 라이딩과 혼동할 수 있으니 오버 라이딩도 함께 공부하시면 좋습니다.

https://www.acmicpc.net/problem/15649

• 문제 이해
• 해결 방법
• 구현

문제 이해

먼저 N, M 두 숫자를 입력받는다. N은 1부터 N까지를 의미한다.

M은 출력 자릿수를 결정한다.

이 문제 N과 M (1)은 M 자릿수를 출력하며 1부터 N까지 중복 없이 출력하는 경우이다. 이 문제의 출력은 결국 순열을 의미한다.

N과 M 문제 시리즈 같은 경우는 순열, 중복순열, 조합, 중복 조합 등을 백트래킹을 이용해서 구현하는 방법을 훈련할 수 있다.

이 문제는 백트래킹을 몰랐다면 풀기 어려웠을 것 같다.

해결 방법

우선 재귀 함수를 이용하여 자리수를 하나씩 채워간다. 즉 재귀가 될 때마다 자릿수가 다음 자릿수로 넘어간다.

재귀의 인자로 자리수 번호를 0부터 시작하여 앞부터 채워나간다.

재귀가 진행될 때 마다 0 1 2 3 4 자릿수를 채워나간다. 자릿수를 넘치면 종료 조건이 된다. 

재귀 함수 내에서 반복문으로 1부터 N까지 진행하게 해 두고 반복 문안에 재귀 함수를 만들어두면 1 -> 1- > 1 ->....로 재귀 함수가 호출이 되고, 자릿수가 넘쳐서 종료 조건을 만나면 이전 재귀함수로 돌아와 1 -> 1 -> 1 -> 2 이런 식으로 다음 반복을 진행하게 되어 모든 경우의 수를 출력할 수 있을 것이다.

하지만 이 방법은 중복순열이 되므로 중복된 숫자를 출력하지 않게 하도록 방문처리를 해주어야 했다.

중복된 숫자를 출력하지 않도록 하는 중복처리는 boolean[] 배열을 이용해서 재귀 함수 호출 이전에 for문 안에서

방문하지 않았다면 방문 처리한 후 다음 재귀 함수를 호출해서 다음 재귀로 넘어가도록 하였다.

이렇게 되면 다음 재귀 함수에서 1부터 사용하려 하겠지만 방문처리가 되었다면 다음 숫자의 반복으로 진행이 되므로

중복된 숫자가 출력되지 않도록 처리를 해줄 수 있다.

재귀 함수가 종료조건을 만나면 이전 재귀 함수 위치로 돌아오고 해당 수의 방문처리를 해제해준다.

여기서 이런식으로 방문 처리를 해제해주면 어차피 다음 반복문은 +1 이므로 해당 자릿수에서는 같은 숫자를 출력하지 않을 것이다.

* 예를들어 1234 출력 후 1234가 다시 안 되는 이유는 다음 반복을 진행하므로 1235가 된다. 

결국 방문처리 해제는 해당 자리수를 위한 것이 아니라 반복문이 전부 종료되면 이전 자릿수의 재귀 함수 호출로 돌아갈 것이므로 그곳에서

해당 숫자를 사용하기 위해 해체해주는 것이다.

마지막으로 재귀가 진행될때마다 자릿수에 중복 없이 저장될 숫자를 저장할 배열을 자리수 크기만큼 만들어둔다.

재귀 함수의 종료 조건은 자릿수가 넘치면 종료된다.

배열은 index가 0부터 시작하므로 자릿수가 넘치는 경우는 각 숫자를 저장한 배열의 index가 M 자릿수가 될 때이다.

재귀 함수를 종료시키며 이때 숫자를 저장해두었던 배열을 출력한다.

구현

[JAVA] 자바 BufferedReader 사용법

자바에서 입력을 받을 때 Scanner 클래스로 입력을 받아왔었다.

BufferedReader가 사용하기 불편해서 Scanner가 등장한 걸로 알고 있지만 백준 문제를 풀다 보면 Scanner를 사용했을 때

입력 자체에서 시간 초과가 걸리는 경우가 많아서 BufferedReader를 다시 사용하게 되었다.

Scanner는 내부적으로 정규 표현식이 너무 많이 적용되어있어서 parse 할 때는 편리하지만, 성능이 희생당한다.

추가로 출력을 해주는  BufferedWriter도 있지만, 출력을 할 때 StringBuilder에 담아서 출력만 해도 출력 시간 초과는 해결된다.

이 글에서는 BufferedReader만 간단하게 사용하는 법을 정리하기로 했다.

BufferedReader 사용법

사용하기 위해선 3가지 코드를 작성해주어야 한다.

import java.io.BufferedReader;

import java.io.InputStreamReader;

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

main함수에 throws IOException를 추가해주면 기본적인 준비는 마쳤다.

고려해야할 점은 br.readLine()의 return은 String이므로 String으로 입력을 받아야한다.

또한 BufferedReadr는 Line 단위로 읽는다.

자주 사용하는 추가적인 함수들

문자를 입력을 받은 경우 보통 두 가지 경우가 발생한다.

• 입력받은 문자를 숫자로 변환할 경우 
• 입력받은 문자를 특정 문자 기준으로 자를 경우

11줄) 문자를 숫자로 변환할 경우는 Integer.parseInt()로 변환해주면 된다.

문자를 특정문자 기준으로 자를 경우 두 가지 방법이 가능하다.

14줄) StringTokenizer를 사용할 경우 StringTokenizer 생성자에 입력받을 문자를 넣은 후, nextToken() 함수로 하나 씩 가져와 사용할 수 있다.

공백이 아닌 특정 문자 기준으로 자르고 싶을때에는 new StringTokenizer(br.readLine(), "자를문자");

18줄) String.split()을 사용할 경우 반환을 String [] 배열로 받아주어야 한다. split() 함수의 인자로 자를 문자를 입력하면 된다.

[JAVA] 자바 Iterator와 ListIterator 사용법

자바에서는 Collection 인터페이스를 구현한 자료구조인 ArrayList, LinkedList, HashSet, TreeSet 등의 요소를 하나씩 반복하여

모든 요소를 확인할 수 있는 Iterator (단방향)와 ListIterator(양방향)가 있습니다.

Iterator 구현도

인터페이스가 추상메서드를 갖고 있다면 해당 인터페이스를 구현하는 클래스는 모두 해당 메서드의 구현부를 작성해야 합니다.

Iterator는 iterator()라는 함수명을 갖고 있는 추상 메서드가 반환을 합니다.

iterator() 추상 메서드의 위치는 Iterable이라는 인터페이스에서 작성을 해뒀습니다.

결국 Iterable을 구현한 모든 클래스는 iterator()라는 함수의 구현부를 작성해야합니다.

Collection 인터페이스

Collection 인터페이스가 Iterable를 상속받았습니다.

그래서 Collection을 구현한 자료구조 API는 iterator()함수를 구현을 해놨습니다.

실제 구현부는 ArrayList, LinkedList, HashSet, TreeSet 와 같은 실제 인스턴스를 생성하는 클래스에서 구현을 합니다.

설계 방식은 전부 다르므로 Iterator를 통해 요소를 가져오고 삭제하는 과정도 따로 작업을 해놨습니다.

iterator()를 호출하면 Itr이라는 내부 클래스명으로 Iterator를 상속받고, 객체를 생성해서 돌려줍니다.

iterator()의 반환인 Iterator 인터페이스가 Collection 순회를 돕는 hasNext(), next(), remove()를 구현하도록 하고 있습니다.

Iterator를 상속했으니, Iterator it = list.iterator() 와 같이 사용합니다.

주의점

List는 저장 순서를 유지하기 때문에 iterator를 사용하면 저장 순서를 유지하며 요소를 확인할 수 있지만,

Set은 저장 순서를 유지하지 않기 때문에 저장 순서대로 요소를 확인할 수 없습니다.

인터페이스 구현 순서

1. Iterable
2. Collection
3. List, Set
4. ArrayList, LinkedList, HashSet, TreeSet 등

아래 사진은 ArrayList 내부에 Iterator를 반환하는 iterator() 함수의 작성 내용입니다.

iterator()의 직접적인 구현은 ArrayList, LinkedList, HashSet, TreeSet에 작성하는 걸 확인할 수 있습니다.

iterator() 함수를 호출하게 되면 Itr() 인스턴스를 생성하여 return합니다.

Itr은 내부 클래스로 Iterator 인터페이스의 추상 메서드 hasNext(), next(), remove() 를 모두 구현합니다.

Iterator의 메서드는 JAVA API에서 확인할 수 있습니다.

https://docs.oracle.com/en/java/javase/15/docs/api/java.base/java/util/Iterator.html

Iterator, ListIterator 사용법

Iterator의 구현도는 복잡하지만 실제 사용하려는 프로그래머 입장에서는 iterator의 사용은 아주 단순합니다.

주의할 점은 Iterator, ListIterator의 cursor 위치는 시작할 때 맨 앞 요소 그 앞에 있습니다.

cursor의 위치는 요소를 가리키고 있는 것이 아니라 요소와 요소 사이에 있다라고 생각하시면 됩니다.

Iterator의 사용

결과

ListIterator의 사용

ListIterator는 Iterator와 사용방법이 비슷합니다. 대신 ListIterator는 이전 요소로 되돌아갈 수 있습니다.

13, 14줄) it.next()를 부르면 다음 요소로 넘어갑니다. 15줄) it.previous() 호출하면 이전 요소로 되돌아갈 수 있습니다.

이런 식으로 양방향으로 이동 가능한 것이 ListIterator의 특징입니다.

여기서 cursor의 위치가 요소와 요소 사이에 있다는 것을 출력을 통해 확인해볼 수 있습니다. 

13줄) next() 함수를 호출하면 결과는 1입니다. cursor는 1과 2 사이에 있으며 왼쪽 요소(1)를 반환합니다.

14줄) next() 함수를 한번 더 호출하면 결과가 2입니다. cursor는 2와 3 사이에 있으며 왼쪽 요소(2)를 반환합니다.

여기까지 코드를 실행하면 현재 cursor의 위치는 2와 3사이 입니다.

이제 15줄) previous() 함수를 호출하면 cursor가 왼쪽으로 이동하며 cursor의 위치는 1과 2 사이가 됩니다.

대신 반환 요소를 현재 위치에서 오른쪽의 있는 요소(2)를 반환합니다.

이렇듯 커서는 요소와 요소 사이에 있으며, cursor가 이동한 후, 지나온 요소를 반환한다고 생각하시면 됩니다.

결과

[JAVA] 알고리즘 DFS [Depth-First Search] 깊이 우선 탐색

DFS [Depth-First Search]는 깊이 우선 탐색이며 깊이를 우선적으로 탐색합니다. 

2차원 배열이나 그래프 탐색에서 한번 방문한 노드는 다시 방문하지 않으며 깊이 탐색을 통해 방문하여 모든 노드를 탐색하는 방법입니다.

BFS와 마찬가지로 모든 노드를 탐색하는 방법 중 하나입니다.

• DFS - 재귀, stack 자료 구조 활용
• BFS - Queue 자료 구조 활용

DFS를 코드로 구현하기 위해선 3가지가 필요합니다.

• 탐색할 2차원 배열 또는 그래프
• 방문처리를 하기 위한 boolean type 
• Stack 자료 구조 또는 재귀 함수

방문체크를 위한 boolean 배열과 그래프를 선언합니다.

추가로 Stack 자료 구조를 활용하기보다는 재귀 함수를 통해서 구현해보도록 하겠습니다.

가장 먼저 DFS의 매개변수로 들어온 int x 노드부터 깊이 탐색을 진행합니다.

x 노드를 다시 방문하지 않도록 방문처리를 가장 먼저 처리해주도록 하겠습니다. 

x 노드와 연결된 노드들을 확인하기 위해 for (int i = 0; i < graph [x]. length; i++) 반복문을 사용하여

x 노드와 연결된 모든 노드들을 확인해줍니다.

반복을 통해 하나씩 확인해가며  if (! visited [graph [x][i]])를 이용하여 이미 방문이 돼있다면 true,

방문하지 않았다면 false 이므로 방문하지 않아야만 재귀 함수를 통해 해당 노드를 DFS 인자로 넣은 후 호출해줍니다.

여기서 생각해야 할 점은 재귀 함수를 호출하여 제어를 넘겨주었으므로

for 반복문은 재귀 함수가 완전히 처리된 이후에 다시 제어를 얻어 진행하던 반복을 진행하게 됩니다.

호출한 함수가 완료되야 제어를 얻어 다음 노드로 반복을 진행하게 됩니다.

이러한 재귀 함수를 이용하는 점이 바로 Stack 자료 구조 방식으로 깊이 탐색을 가능하도록 해줍니다.

간단하게  말하자면, 해당 dfs함수에서 재귀함수를 호출하면 현재 진행하는 반복이 멈춘후 재귀함수를 먼저 진행한다. 라고 생각하시면 됩니다.

전체 코드

[JAVA] 알고리즘 BFS [Breadth-First Search] 너비 우선 탐색

BFS [Breadth-First Search]는 너비 우선 탐색이며 너비를 우선적으로 탐색합니다. 

2차원 배열이나 그래프 탐색에서 한번 방문한 노드는 다시 방문하지 않으며 주변을 순차적으로 방문하여 모든 노드를 탐색하는 방법입니다.

모든 노드를 탐색하는 알고리즘으로 깊이 우선 탐색을 하는 DFS와는 달리 Stack을 이용하지 않으며 Queue를 이용하여 전개할 수 있습니다.

• DFS - 재귀, stack 자료 구조 활용
• BFS - Queue 자료 구조 활용

BFS를 코드로 구현하기 위해서 3가지를 우선적으로 구현해놓아야 합니다. 

• 탐색할 2차원 배열 또는 그래프
• 방문처리를 하기 위한 boolean type 
• Queue 자료 구조

굳이 static으로 처리할 필요는 없습니다.

여러 함수에서 사용될 것이라 예상되면 매개변수로 넘겨주는 방법 대신에 클래스 변수로 처리하여

모든 함수에서 바로 사용할 수 있게끔 하는 편입니다.

앞서 선언된 3가지를 이용해서 BFS함수를 작성하도록 하겠습니다.

[JAVA] 자바 Comparable과 Comparator 사용법

자바에서 Comparable과 Comparator은 둘 다 인터페이스이며, 정렬을 위해서 사용한다.

인터페이스이므로 구현을 통해 사용해야 하며 기본형 비교가 아닌 객체 비교를 위해 만들어졌다.

결론부터 말하자면, Comparable은 객체 내부에 비교 기준을 부여하여 다른 객체와 비교를 하는 것이고,

Comparator은 객체 외부에서 비교할 두 객체를 비교하여 비교 기준으로써의 역할을 한다.

여기서 주목할 점은 정렬을 해주는 것이 아니라, 비교 기준을 제공해준다는 점이다. 직접적으로 정렬을 진행하는 부분은 유틸 클래스가 처리해준다.

배열의 정렬을 직접 구현해보았다면 두 요소를 비교할 때 비교 연산자 크기 비교를 통해 true, false의 결과로 Swap을 하여 정렬을 한다는 점을 알 수 있을 것이다. 객체 비교에서는 Comparable과 Comparator는 바로 이러한 true, false 같은 정렬 기준을 제공하고, 유틸 클래스가 Swap을 처리하는 코드라고 생각하면 된다.

일반적으로 자바에서는 기본형 타입의 비교는 비교 연산자(==,<=,>=,<,>)등을 통해 손쉽게 비교할 수 있다. 하지만 객체 내부의 어떤 field를 비교하고 싶을 때에 객체 자체를 기본형 타입처럼 비교 연산자를 사용하게 되면 객체의 참조값을 비교하기 때문에 올바른 비교 결과를 얻을 수 없다. 그러므로 객체 내부 특정 field를 이용하여 정렬하고자 할 때를 위해 Comparable과 Comparator가 필요하게 되었다. field를 비교하게 되면 그 결과로 객체를 정렬을 할 수 있다.

Comparable과 Comparator를 사용하기 이전에 알아야 할 것

예를 들어 배열의 요소가 두 개인 3과 5 인 배열을 오름차순 한다고 가정해보자.

배열이 [3, 5] 순서로 정렬돼있다고 가정했을 때

두 값을 뺄셈 연산하면 그 결과가 -2이다. [ ex) 3 - 5= - 2 ] 그러므로 뒤 값이 큰 걸 알 수 있다. 오름차순 정렬이므로 그대로 둔다. 

배열이 [5, 3] 순서로 정렬돼있다고 가정했을 때

두 값을 뺄셈 연산하면 그 결과가 2이다. [ ex) 5 - 3 = 2 ] 그러므로  앞 값이 큰 걸 알 수 있다. 오름차순 정렬을 해야 하므로 두 수의 위치를 Swap 한다.

오름차순 정렬에서는 뺄셈 결과가 음수면 앞 값이 작으므로 정렬이 올바르다. 그 위치 그대로 둔다.

뺄셈 결과가 양수면 앞 값이 크므로 오름차순 정렬을 위해 Swap을 해줘야 함을 알 수 있다.

밑에서 사용할 compareTo 함수는 return이 양수면 Swap 시킨다.

곧 이 말은, 뺄셈의 결과가 어떤 수이냐에 따라 Swap을 할지 말지인 정렬 기준을 제공할 수 있다는 점이다.

Comparable 사용법

Comparable은 위에서 서술했듯, 인터페이스이므로 추상 메서드를 갖고 있다. 갖고 있는 추상 메서드는 compareTo 하나이다. Comparable의 사용법은 객체 내부에서 비교 기준을 제공하므로 비교할 객체에 Comparable을 구현받아 객체 내부에 Comparable의 메서드인 compareTo를 Overriding 하여 사용해야 한다.

사람의 정보(이름, 나이)가 들어있는 객체를 정의하고 나이 순서로 정렬하고자 할 때