본 아티클에서는, 제너릭스로 구현된(자료형에 구애받지 않고 사용할 수 있게 구현) 메서드를 사용해볼 것입니다..
새로운 자료형(클래스) 제너릭스로 구현
//--- 신체검사 데이터 ---//
class PhyscData {
private final String name; // 이름
private final int height; // 키
private final double vision; // 시력
//--- 생성자(constructor) ---//
public PhyscData(String name, int height, double vision) {
this.name = name;
this.height = height;
this.vision = vision;
}
//--- 문자열로 만들어 반환하는 메서드 --//
public String toString() {
return name + " " + height + " " + vision;
}
//--- 키의 오름차순으로 정렬하기 위한 comparator ---//
public static final Comparator<PhyscData> HEIGHT_ORDER =
new HeightOrderComparator();
private static class HeightOrderComparator implements Comparator<PhyscData> {
public int compare(PhyscData d1, PhyscData d2) {
return (d1.height > d2.height) ? 1 :
(d1.height < d2.height) ? -1 : 0;
}
}
}
PhyscData라는 자료형에 대해 Binary Search를 사용하려고 합니다.
PhyscData라는 클래스 내부에 Comparator를 하나 구현했습니다. (외부에 구현해도 상관 없습니다.)
그리고 구현한 Comparator 내부에는 compare라는 메서드를 구현해야 합니다.
PhyscData 객체들의 순서를 비교할 때, height를 기준으로 하며,
더 큰 height를 가진 객체가 오른쪽에 오도록(오름차순) 정렬 규칙을 정한 것입니다.
binarySearch 메서드 사용
class BinarySearch1 {
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
PhyscData[] x = { // 키의 오름차순으로 정렬
new PhyscData("강민하", 162, 0.3),
new PhyscData("이수연", 168, 0.4),
new PhyscData("황지안", 169, 0.8),
new PhyscData("유서범", 171, 1.5),
new PhyscData("김찬우", 173, 0.7),
new PhyscData("장경오", 174, 1.2),
new PhyscData("박준서", 175, 2.0),
};
System.out.print("키가 몇 cm인 사람을 찾고 있나요?: ");
int height = stdIn.nextInt(); // 킷값을 읽어 들임
int idx = Arrays.binarySearch(
x, // 배열 x에서
new PhyscData("", height, 0.0), // 키가 height인 요소를
PhyscData.HEIGHT_ORDER // HEIGHT_ORDER에 의해 검색
);
if (idx < 0)
System.out.println("그 값의 요소가 없습니다.");
else {
System.out.println("그 값은 x[" + idx + "]에 있습니다.");
System.out.println("찾은 데이터: " + x[idx]);
}
}
}
위의 코드는 PhyscData의 배열에서 Binary Search를 실행하고 있습니다.
Arrays.binarySearch 메서드의 인자로 배열, key값, Comparator를 구현한 객체가 들어감을 확인할 수 있습니다.
만약 찾는 값이 존재한다면, 위치(인덱스)를 반환합니다.
존재하지 않는다면, 만약 값이 존재한다면 어디에 위치해야하는지를 알려주는 값을 음수로 반환합니다.
이를 삽입 포인트(insertion point)라고 하는데,
insertioin point = -(원래 위치했어야 하는 인덱스 값) - 1로 주어집니다.
만약 배열이 Comparator에 정의된 compare 메서드의 규칙에 따라 정렬되어 있지 않다면,
정확하지 않은 값을 반환합니다.
binarySearch 메서드는 정렬이 된 배열을 가정하고 검색을 실행하기 때문입니다.
내림차순으로 수정해보기
package chapter3;// 신체검사 데이터 배열에서 이진 검색
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
class BinarySearch1 {
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
PhyscData[] x = { // 시력의 내림차순으로 정렬
new PhyscData("박준서", 175, 2.0),
new PhyscData("유서범", 171, 1.5),
new PhyscData("장경오", 174, 1.2),
new PhyscData("황지안", 169, 0.8),
new PhyscData("김찬우", 173, 0.7),
new PhyscData("이수연", 168, 0.4),
new PhyscData("강민하", 162, 0.3),
};
System.out.print("시력이 몇인 사람을 찾고 있나요?: ");
double vision = stdIn.nextDouble(); // 킷값을 읽어 들임
int idx = Arrays.binarySearch(
x, // 배열 x에서
new PhyscData("", 0, vision), // 시력이 vision인 요소를
PhyscData.VISION_ORDER // HEIGHT_ORDER에 의해 검색
);
if (idx < 0)
System.out.println("그 값의 요소가 없습니다.");
else {
System.out.println("그 값은 x[" + idx + "]에 있습니다.");
System.out.println("찾은 데이터: " + x[idx]);
}
}
}
//--- 신체검사 데이터 ---//
class PhyscData {
private final String name; // 이름
private final int height; // 키
private final double vision; // 시력
//--- 생성자(constructor) ---//
public PhyscData(String name, int height, double vision) {
this.name = name;
this.height = height;
this.vision = vision;
}
//--- 문자열로 만들어 반환하는 메서드 --//
public String toString() {
return name + " " + height + " " + vision;
}
//--- 시력의 내림차순으로 정렬하기 위한 comparator ---//
public static final Comparator<PhyscData> VISION_ORDER =
new HeightOrderComparator();
private static class HeightOrderComparator implements Comparator<PhyscData> {
public int compare(PhyscData d1, PhyscData d2) {
return (d1.vision < d2.vision) ? 1 :
(d1.vision > d2.vision) ? -1 : 0;
}
}
}
시력의 내림차순으로 정렬된 배열에서 이진 탐색을 수행하도록 코드를 수정했습니다.
입력을 받는 자료형을 double로 바꾸고,
Comparator의 compare 메서드가 vision을 기준으로,
그리고 반대 방향으로 정렬을 수행하도록 수정했습니다.
System.out.println("idx: " + idx);
위와 같은 코드를 추가하여 idx의 값을 살펴봅시다.
idx는 -5가 됩니다.
만약 0.77이 존재했다면 idx가 4였을 것이므로,
(-4) - 1 = -5의 값이 나온 것입니다.
PhyscData[] x = { // 시력의 내림차순으로 정렬
new PhyscData("박준서", 175, 2.0),
new PhyscData("유서범", 171, 1.5),
new PhyscData("장경오", 174, 1.2),
new PhyscData("김찬우", 173, 0.7),
new PhyscData("황지안", 169, 0.8),
new PhyscData("이수연", 168, 0.4),
new PhyscData("강민하", 162, 0.3),
};
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int inputNumber = scanner.nextInt();
for (int i = inputNumber; i > 0; i--) {
System.out.println(i);
}
scanner.close();
}
}
입력 받은 숫자를 1까지 감소시키며 출력하는 아주 간단한 문제를 자바로 구현했다.
이를 파이썬 코드로 바꾸면,
파이썬 코드
n = int(input())
for i in range(n):
print(n - i)
ㅋㅋㅋㅋ
구글에 '코딩테스트 파이썬 vs 자바'로 검색해서 나오는 대부분의 글을 다 읽어봤는데,
많은 사람들이 기업 코딩테스트 수준에서는 자바로 풀어도 시간이 부족할 정도로 나오지 않을 것이라고 말한다.
중급자 이상이 되면, 구현을 떠올리는 과정이 어렵지
익숙한 언어로 구현하는 것은 일도 아니라고 한다.
하지만 분명 구현하거나 수정하는 데 소요되는 시간이 길어지면
그만큼 히든 케이스를 찾거나 고민할 수 있는 시간이 줄어드는 것은 확실할 거라 생각한다.
이런 저런 이유로 오래 고민하다가..
결국 자바로 공부를 시작하기로 했다.
코딩테스트 공부를 하면서 동시에 자바 언어로 여러 알고리즘을 구현해보고 언어에 익숙해지는 과정,
그리고 어려운 문제를 고민하면서 자바의 자료구조도 뜯어볼 수 있을테니,
일석이조의 효과를 누리는 것이 낫겠다고 판단했다.
웬만한 문제 풀이도 구글에 자바로 나와있고, 백준에 많은 코드도 공유되어 있으니
공부하는 데에도 큰 문제가 없겠다는 생각.
단기적으로 공부할 것이 아니고,
장기적으로 내가 목표로 하는 수준(골드 2~3)에 도달하는 데에는 언어가 큰 지장을 주지 않을 것이라고 판단했다.
