백준 1920번: 수 찾기

코드: https://github.com/kgh128/Problem-Solving/blob/main/src/Baekjoon/p1920.java

1. 변수 선언 및 입력받기

모든 정수의 범위는 -231 보다 크거나 같고 231보다 작으므로 N개의 정수가 있는 배열 stNum과 M개의 정수가 있는 배열 cpNum을 int형 배열로 선언한다.

• byte: -27 ~ 27-1
• short: -215 ~ 215-1
• int: -231 ~ 231-1
• long: -263 ~ 263-1

변수의 이름을 의미있게 짓자. 계속 틀려서 코드를 자세히 뜯어봤는데, cpNum 배열을 채우는 반복문에서 M을 N으로 쓴 것을 발견했다. 비슷하게 생긴 알파벳을 변수 이름으로 설정하면 오타가 나기는 쉽고, 발견하기는 어렵다.

2. 이분탐색

이분탐색을 사용해서 cpNum 배열의 각 요소가 stNum 배열에 존재하는지 확인한다.
이분탐색의 대상이 되는 배열인 stNum을 오름차순으로 정렬한다.

Arrays.sort(stNum);	// Java에서 오름차순 정렬

Java의 이분탐색 함수를 이용하여 이분탐색을 한다. 직접 구현하면 10줄 이상의 코드를 더 쳐야하는데, Arrays.binarySearch(arr, key)를 이용하면 1줄로 끝낼 수 있다.

Arrays.binarySearch(arr, key)는 arr 배열 안에 key 값이 존재하면 key와 일치하는 요소의 인덱스(0 이상)를 반환하고, 존재하지 않으면 음수를 반환한다.
key와 일치하는 요소가 없어도 arr 배열 안에서 key 값의 적절한 위치를 찾아서 반환하는데, arr 배열 안에는 key 값이 존재하지 않는다는 의미로 위치에 마이너스를 붙여서 음수로 반환한다.

// cpNum[i]가 stNum 배열 안에 존재하면 1 출력
if (Arrays.binarySearch(stNum, cpNum[i] >= 0) {
	bw.append("1\n");
}
// cpNum[i]가 stNum 배열 안에 존재하지 않으면 0 출력
else {
	bw.append("0\n");
}

3. 출력

결과(1 또는 0)이 나올 때마다 System.out.println() 함수를 호출하여 결과를 출력하지 말고, 버퍼(bw)에 모아놓았다가 한 번에 출력(System.out.print(bw);)해서 성능을 높인다. 버퍼로는 가변 문자열 자료형인 StringBuilder를 사용한다. 결과가 나올 때마다 버퍼 문자열에 해당 결과를 이어붙여야 하기 때문이다.

String은 불변하는(immutable) 자료형이다. .concat(값) 또는 + "값"을 사용해서 문자열을 이어붙이면 String 참조 변수가 가리키는 기존 객체를 버리고 새로운 객체를 할당한다. 따라서 이 연산을 많이 사용할 경우 성능이 좋지 않다.

반면에, StringBuffer와 StringBuilder는 가변하는(mutable) 자료형이므로 .append(값)을 통해서 문자열을 이어붙여도 참조 변수가 가리키는 기존 객체를 버리지 않고, 그 객체의 값을 변경한다. 따라서 문자열을 계속 수정해야 하는 경우 이 자료형들을 쓰는 것이 더 좋은 성능을 보인다.