하지만 있는지 없는지 true, false로 반환을 해줄 뿐 어느 인덱스에 있는지는 binary_search 함수로는 알 수 없다.
그래서 사용하는 것이 upper_bound, lower_bound 함수이다.
upper_bound와 lower_bound의 첫 번째, 두 번째 인자는 내가 찾고 싶은 범위를 주소로 지정해주면 된다. 꼭 배열 전체, 벡터 전체일 필요는 없다. 해당 범위를 지정해주고 그 안에 있는지만 찾고 싶으면 그렇게 지정해주면 된다. binary_search 함수의 인자와 똑같다.
세 번째 인자도 binary_search의 세 번째 인자처럼 몇 개 있는지 알고 싶은 그 대상을 적어주면 된다.
lower_bound 함수는 내가 찾고자 하는 그 대상이 저장된 인덱스 중 가장 작은 인덱스를 반환한다.
upper_bound 함수는 내가 찾고자 하는 그 대상이 저장된 인덱스 중 가장 큰 인덱스+1을 반환한다.
예를 들어 정렬된 arr 배열에 다음과 같이 저장되어 있었다고 하자.
1 3 4 4 7 10 10 10 13 17
lower_bound(arr, arr + 10, 10)을 한다면 10이 처음 등장하는 인덱스인 인덱스 5의 주소를 반환한다.
upper_bound(arr, arr + 10, 10)을 한다면 10이 마지막으로 등장하는 인덱스+1인 인덱스 8의 주소을 반환한다.
iterator(메모리 주소)를 반환하기 때문에 몇 번째 인덱스인지 알아보고 싶으면 배열이나 벡터의 시작주소를 빼보면 된다.
일단 lower_bound와 upper_bound 함수의 반환값을 알아보기 위해서 그냥 출력해보면
이렇게 10의 시작인덱스, 10의 마지막 인덱스+1을 출력하는 것을 볼 수 있다. 그 인덱스에 뭐가 들어있는지 알아보고 싶으면 역참조 연산자 *로 데이터에 접근해서 출력해보면 된다. 10의 마지막 인덱스 한 칸 뒤에는 13이 저장되어 있으니 13이 출력될 것을 알 수 있다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
cin.tie(NULL);
ios::sync_with_stdio(false);
int n;
cin >> n;
vector<int> v(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
}
sort(v.begin(), v.end());
int m;
cin >> m;
for (int i = 0; i < m; i++) {
int target;
cin >> target;
int start = 0;
int end = v.size() - 1;
int key = -1;
while (start <= end) {
if (v[(start + end) / 2] == target) {
key = (start + end) / 2;
break;
}
else if (v[(start + end) / 2] > target) {
end = (start + end) / 2 - 1;
}
else if (v[(start + end) / 2] < target) {
start = (start + end) / 2 + 1;
}
}
if (key == -1) cout << 0 << '\n';
else cout << 1 << '\n';
}
return 0;
}
이진탐색으로 풀었더니 60ms로 성공
혹시나 하고 C++에 있는 find() 함수를 사용해서 풀어봤다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int n, m;
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
cin >> m;
for (int i = 0; i < m; i++) {
int temp;
cin >> temp;
vector<int>::iterator iter;
iter = find(arr.begin(), arr.end(), temp);
if (iter != arr.end()) {
cout << 1 << '\n';
}
else cout << 0 << '\n';
}
return 0;
}
무려 1796ms로 성공. 있는지 없는지 한 번만 찾아볼거면 굳이 정렬하는 시간을 들여서까지 이진탐색을 할 필요는 없는데 이 경우는 한 배열에서 어떤 숫자가 있는지 없는지 여러번 찾아볼 것이기 때문에 이진탐색이 훨씬 효율적이다. 정렬을 한 번만 해주면 그 후로 매우 빠르게 찾을 수 있다.
람다식은 불필요한 코드를 생략하고 메소드 내부 코드만 작성해서 간단하게 인터페이스 객체를 생성하는 방법이었다.
하지만 람다식도 불필요한 부분들이 있다. 다음 코드를 보자.
interface ReturnNumber {
void function(int n);
}
public class LambdaTest {
public static void main(String[] args) {
printNumber(x -> System.out.println(x), 10); //받은 수를 그대로 반환하는 ReturnNumber 객체를 만들어서 넘겨줌
}
static void printNumber(ReturnNumber returnNumber, int num) {
returnNumber.function(num);
}
}
이 코드를 보면 x -> System.out.println(x)라는 람다식으로 ReturnNumber 객체를 만들어서 메소드의 인자로 넘겨줬다.
하지만 이 람다식은 너무 간단하다. 받은 것을 그대로 출력하라는 것인데 x를 두 번이나 썼다. 이 x를 불필요한 부분이라고 생각해서 이런 간단한 코드들은 메소드참조를 써서 더욱 더 간결하게 만들 수 있게 했다.
interface ReturnNumber {
void function(int n);
}
public class LambdaTest {
public static void main(String[] args) {
printNumber(System.out::println, 10); //받은 수를를 그대로 반환하는 ChangeNumber 객체를 만들어서 넘겨줌
}
static void printNumber(ReturnNumber returnNumber, int num) {
returnNumber.function(num);
}
}
이렇게 System.out::println만 해주면 인자를 받아서 그 인자를 출력하도록 하는 메소드를 구현한 것이다.
람다식인 x -> System.out.println(x)보다 훨씬은 아니지만 메소드 참조를 사용하니 조금 더 간결해졌다.
다음 코드를 보자.
public class LambdaTest {
public static void main(String[] args) {
String[] names = {"Bill", "jane", "Anne", "billy", "Tom", "jake", "amily", "Susan"};
Arrays.sort(names);
for(String s : names)
System.out.print(s + " ");
}
}
대소문자가 구별되어 정렬됨
이렇게 Arrays.sort() 메소드를 사용해서 배열을 정렬하면 자동으로 오름차순 정렬이 되는데 문자열의 경우 유니코드의 값을 기준으로 오름차순 정렬을 하기 때문에 소문자는 무조건 대문자보다 뒤에 오게 된다.
만약 이것이 싫다면 내가 원하는 정렬기준으로 compare(T o1, T o2) 메소드를 구현한 Comparator 인터페이스를 객체를 Arrays.sort() 메소드의 두 번째 인자로 넣어주면 된다. 그런데 String 클래스에 대소문자 구별없이 이미 만들어져있는 메소드가 있다. 그 메소드를 부르면 Comparator 객체를 반환하는 것은 아니고 그 메소드의 반환값을 compareTo(T o1, T o2) 메소드의 반환값으로 구현만 해주면 된다. String 클래스에 있는 compareToIgnoreCase() 메소드이다.
import java.util.Arrays;
public class LambdaTest {
public static void main(String[] args) {
String[] names = {"Bill", "jane", "Anne", "billy", "Tom", "jake", "amily", "Susan"};
Arrays.sort(names, (a, b) -> a.compareToIgnoreCase(b));
for(String s : names)
System.out.print(s + " ");
}
}
이렇게 람다식으로 Arrays.sort() 메소드의 두 번째 인자에 대소문자를 구분 안 하는 Comparator 객체를 넣어주면
이렇게 대소문자 구별 없이 정렬된 것을 볼 수 있다.
하지만 (a, b) -> a.compareToIgnoreCase(b)에서 a, b가 두 번씩 사용되어 불필요한 코드라고 생각해서 이것도 메소드 참조로 표현할 수 있도록 했다.
import java.util.Arrays;
public class LambdaTest {
public static void main(String[] args) {
String[] names = {"Bill", "jane", "Anne", "billy", "Tom", "jake", "amily", "Susan"};
Arrays.sort(names, String::compareToIgnoreCase);
for(String s : names)
System.out.print(s + " ");
}
}
String::compareToIgnoreCase 이렇게 메소드 참조를 사용하면 코드가 좀 더 간결해졌다.
이 코드의 실행결과는 위 코드의 실행결과와 정확히 똑같다.
그리고 스트림에서 특히 람다식과 메소드 참조가 정말 유용하게 사용되는데
list.removeIf(x -> Objects.isNull(x));
이런 코드도 메소드 참조를 이용하면
list.removeIf(Objects::isNull);
이렇게 더 간결하게 줄일 수 있다.
list.forEach(x -> System.out.println(x));
이런 코드도 메소드 참조를 이용하면
list.forEach(System.out::println);
이렇게 줄일 수 있다.
메소드 참조의 규칙을 정리하자면 다음과 같다.
람다식
메소드 참조
static 메소드
a ->클래스이름.메소드(a)
클래스이름::메소드이름
인스턴스 메소드
(a, b) -> a.메소드(b)
클래스이름::메소드이름
(a) -> 객체.메소드(a)
객체::메소드이름
생성자
(a) -> new 생성자(a)
생성자이름::new
배열 생성자
(a) -> new 타입[a]
타입::new
첫 번째 예제 코드에서 배운 a -> System.out.println(a)를 System.out::println으로 줄이는 것은 이 표에서 3번째 즉, 인스턴스 메소드에서 (a) -> 객체.메소드(a)를 객체::메소드이름으로 바꾸는 것에 해당한다. (System.out은 표준 출력을 담당하는 객체이다.)
두 번째 예제 코드에서 배운 a.compareToIgnoreCase(b)를 String::compareToIgnoreCase로 바꾸는 것은 이 표에서 두 번째 즉, (a, b) -> a.메소드(b) 에서 클래스이름::메소드이름으로 바꾸는 것에 해당한다.
생성자와 배열 생성자를 메소드 참조로 바꾸는 예를 살펴보자. 스트림을 배우지 않았다면 낯설 수 있지만 그래도 메소드 참조를 어떻게 사용하는지 감이 올 것이다.
import java.util.ArrayList;
import java.util.Arrays;
public class LambdaTest {
public static void main(String[] args) {
ArrayList<String> names = new ArrayList<>();
names.add("Peter");
names.add("Paul");
names.add("Mary");
Employee[] employees = names.stream().map(Employee::new).toArray(Employee[]::new);
System.out.println(Arrays.toString(employees));
}
}
class Employee {
String name;
public Employee(String name) {
this.name = name;
}
@Override
public String toString() {
return name;
}
}
String 타입의 ArrayList names를 메소드 참조를 이용해서 배열로 바꿔주었다. Employee 클래스의 생성자와 Employee[] 배열 생성자를 메소드 참조로 표현했다.
조금 어려울 수도 있는데 그러면 그냥 람다식을 사용하면 되고 사실 메소드 참조는 아까 봤던 예제 정도가 자주 쓰인다.
