각 플랫폼에서 맨해튼거리로 L 보다 같거나 작은 거리 내 동물들을 다 잡을 수 있다고 가정했을 때
잡을 수 있는 모든 동물의 수를 구하는 문제이다!
플랫폼의 수를 M, 동물의 수를 N, 거리를 L이라고 둔다.
플랫폼의 y좌표는 어짜피 0이므로, 플랫폼의 x좌표를 저장할 배열을 만들어준다. 값을 입력받고 오름차순 정렬해준다.
Long[] plate = new Long[M];
...
Arrays.sort(plate);
이렇게 된다면 plate[0] 에는 x축에 가장 가까운 사대가, plate[plate.length-1]에는 x축에서 가장 먼 사대가 되는 것이다.
동물의 x, y좌표를 입력받으면서
plate를 기준으로 start값과 end 값을 잡아준다.
가장 초기에는 start는 0, end는 plate.length-1로 둔다.
mid값은 (start + end)/2 이다.
이분탐색을 돌며 plate[mid]에서 해당 동물의 거리를 구하고, 그 값을 기준으로
1. L과 같거나 작으면 답을 추가한다.
2. L보다 크다면 ...
// 모든 사대는 y의 값이 0이다. 따라서 맨해튼 거리를 구할 때 mid값이 바뀌어도 x좌표끼리의 값만 바뀌지, y 값은 항상 일정하다.2-1. plate[mid]-x가 0보다 크다면, L과 같거나 작게 만드려면 plate[mid] 의 값이 줄어들어야된다. 따라서 mid값을 줄이기 위해 end값을 mid-1 로 바꾼다.
2-2. plate[mid]-x가 0보다 작다면, plate[mid] 값은 항상 양수기때문에 값이 커져야된다. 따라서 start값을 mid + 1로 바꾼다.
이렇게 이분탐색을 시행하면 문제가 풀린다!
이분탐색을 들어가기 전
동물의 y값이 L보다 이미 큰 상태라면 -> 모든 동물이 다 포함될 수 없으므로 이분탐색 하지말고 바로넘긴다!
이거까지 하면 실행속도가 더 줄어든다.
import java.io.*;
import java.util.*;
publicclassMain{
publicstaticvoidmain(String[] args)throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
int M = Integer.parseInt(st.nextToken()),
N = Integer.parseInt(st.nextToken()),
L = Integer.parseInt(st.nextToken());
Long[] plate = new Long[M];
st = new StringTokenizer(bf.readLine());
for(int i=0;i<M;i++) {
plate[i] = Long.parseLong(st.nextToken());
}
Arrays.sort(plate);
int ans = 0;
for(int i=0;i<N;i++) {
st = new StringTokenizer(bf.readLine());
Long x = Long.parseLong(st.nextToken()), y = Long.parseLong(st.nextToken());
int start = 0, end = M-1;
if(y > L) continue;
while(start <= end) {
int mid = (start+end)/2;
Long target = plate[mid] - x;
Long distance = Math.abs(target) + y;
if(distance <= L) {
ans++;
break;
} elseif(target > 0) {
end = mid - 1;
} else {
start = mid + 1;
}
}
}
System.out.println(ans);
}
}
숫자 N개를 입력받아, 숫자끼리 비교하며 0~9 중 같은 숫자가 쓰이는 경우가 있다면 ans++ 해주면 된다.
앗... 자리수가 0~9까지로 단 10자리?!
둘 다 있는지 비교?!
이것은...
비트마스킹.
과거의 나는 비트마스킹을 정말 싫어하였지만
이제는 그것도 다 옛말.
나는 비트의 몸을 맡기는 비트마스커 뤂시우가 되었다.
N개의 수를 입력받을 때, 각각의 자리수로 for문을 한 번 더 돌려, 해당하는 수의 위치의 비트를 1로 바꿔준다.
예를 들어, 비트를 바꾸기 전
int number = 0;
으로 설정해준다.
해당 number을 이진수로 표현하자면
number
9
8
7
6
5
4
3
2
1
0
여부
0
0
0
0
0
0
0
0
0
0
일 것이다.
만약 입력받은 수가 32라면
String temp = "32";
temp.length()로 for문을 돌렸을 때, 처음 temp.charAt(POINT) 은 '3'일 것이다.
그렇다면, 우리가 number에 적용해야 하는 숫자는
temp
9
8
7
6
5
4
3
2
1
0
여부
0
0
0
0
0
0
1
0
0
0
일 것이다.
따라서 1을 왼쪽으로 3번 shift연산 후,
number |= temp.charAt(j) - '0';
number와 이를 합치면 된다!
2도 이와같이 진행하면, 최종적으로 number은
number
9
8
7
6
5
4
3
2
1
0
여부
0
0
0
0
0
0
1
1
0
0
1100 이렇게 될 것이다.
마찬가지로, 282도 이와같이 나타낼경우
number
9
8
7
6
5
4
3
2
1
0
여부
0
1
0
0
0
0
0
1
0
0
100000100 이렇게 될 것이다. 마지막 2를 적용할 때, 이미 2가 1이 있지만 합집합 연산하면 그대로 1이 적용된다.
이 숫자들을 HashMap nums에 갯수와 함께 넣는다!
그 후, HashMap을 돌면서 같은 nums에 대해 1개 이상일 경우 ans를 업데이트 해준다.
for (Map.Entry<Integer, Integer> entry:nums.entrySet()) {
int num = entry.getKey();
int cnt = entry.getValue();
ans += (long)cnt*(cnt-1)/2; //cnt 중 순서 없이 2개 뽑기
이 num을 다른 HashMap내 num 들과 비교해아하는데, 중복 방지를 위해 현재의 num보다 큰 애들과 비교해준다.
비교하는 수를 num = 32, num2 = 282라고 가정해보자.
두 수는 "2" 라는 공통된 수를 갖고있다. 이는 비트마스킹 된 값으로 쉽게 찾을 수 있는데
num
9
8
7
6
5
4
3
2
1
0
여부
0
0
0
0
0
0
1
1
0
0
이것은 32의 nums 값이고,
num2
9
8
7
6
5
4
3
2
1
0
여부
0
1
0
0
0
0
0
1
0
0
이것은 282의 nums 값이다.
이 둘을 교집합연산 (&) 하면
num&num2
9
8
7
6
5
4
3
2
1
0
여부
0
0
0
0
0
0
0
1
0
0
공통으로 갖는 2만 1이되고, 나머지는 0이 됨을 알 수 있다.
따라서 num&num2 연산을 했을 시 0이 아니라면, 공통된 수를 갖고 있는 것이다!
이때는 num이 가지고있는 갯수 중 하나와, num2가 가지고 있는 갯수 중 하나를 뽑아야되기 때문에 nums.get(num) * nums.get(num2) 로 ans를 업데이트한다.
for (int num2 : nums.keySet()) {
if(num >= num2) continue; //num보다 작은 경우 continue처리if((num & num2) != 0) {
ans += (long) cnt*nums.get(num2);
}
}
이 과정을 모두 끝낸다면
맞으면 된다!
전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
publicclass 수업시간에교수님몰래교실을나간상근이_2825{
publicstaticvoidmain(String[] args)throws NumberFormatException, IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(bf.readLine());
Map<Integer, Integer> nums = new HashMap<>();
for(int i = 0; i < N; i++) {
String temp = bf.readLine();
int number = 0;
for(int j = 0; j < temp.length(); j++) {
number |= 1 << (temp.charAt(j) - '0');
}
nums.put(number, nums.getOrDefault(number, 0) + 1);
}
long ans = 0;
for (Map.Entry<Integer, Integer> entry:nums.entrySet()) {
int num = entry.getKey();
int cnt = entry.getValue();
ans += (long)cnt*(cnt-1)/2;
for (int num2 : nums.keySet()) {
if(num >= num2) continue;
if((num & num2) != 0) {
ans += (long) cnt*nums.get(num2);
}
}
}
System.out.println(ans);
}
}
제 코드 및 다른 팀원들의 코드를 내맘대로 리뷰하는 중 여러 Handler를 사용하면 코드가 더 깔끔하고 유지보수가 편해질 것 같아 상의도 없이 만들고 PR날린 그것,
ErrorHandler, Validator
기존 코드를 봅시다
@Service@RequiredArgsConstructorpublicclassBattleServiceImplimplementsBattleService{
//생략@OverridepublicvoidregistBattle(BattleInviteRequest battleInviteRequest, User user){
//생략if (battleInviteRequest.getOppositeUserId() == user.getId()) {
thrownew IllegalArgumentException("Not valid user");
}
if (battleInviteRequest.getTime() <= 0) {
thrownew RuntimeException("Wrong time setting");
}
아...
진짜 아... 싶죠? 분명 던지는 에러들이 서버 상 오류가아닌 비지니스로직 적 이루어질 수 있는 에러인데, 저렇게 서비스단에 2~3줄 심지어 if문으로 메서드 안에 넣으면...... 나중에 혹시라도 수정하게되거나 로직을 변경해야 되는 일이 생겼을 시 굉장히 귀찮아지겠죠?ㅎㅎ....
여기서 제가 생각해낸 방법은
1. 체크해야되는 조건들을 하나의 파일로 묶는다.
2. 오류 결과들을 하나의 파일에 정리한다
3. 던진다!
의 과정입니다.
먼저, 저 말도안되는 Not a valid user과 Wrong time setting을 과감히 지우고, "ErrorCode"의 Enum을 만들었습니다.
@Getter@AllArgsConstructorpublicenumErrorCode{
INVALID_BATTLE_TIME("최소 10분부터 최대 60분까지 설정 가능합니다."),
INVALID_USER("유저 설정이 유효하지 않습니다."),
INVALID_BATTLE_STARTTIME("시작 시간은 최소 60분 후부터 가능합니다."),
INVALID_OPINION_LENGTH("선택지는 최대 16자까지 작성 가능합니다."),
DUPLICATED_BATTLE("이미 해당시간에 예정된 배틀이 존재합니다."),
ENDED_BATTLE("응답 기간이 종료된 배틀입니다.");
privatefinal String message;
}
public classCustomExceptionextendsRuntimeException{
privatefinalErrorCode errorCode;
public CustomException(ErrorCode errorCode) {
super(errorCode.name());
this.errorCode = errorCode;
}
public ErrorCode getErrorCode() {
return errorCode;
}
}
그리고, 저 errorcode를 throw할 수 있는 custom exception을 정의해줍니다.
여기서 잠깐! RuntimeException을 extends하는 이유! 왜 하필 많은 오류 중 Runtime exception일까! 저는 굉장히 궁금했습니다. 사실 이름만 보면 그냥 Exception이 더 일반적으로 보이는데 쓰면 계속 throw를 하래잖아요! 그래서 패트병 대신 텀블러로 커피를 1회 마시고 GPT선생님께 여쭈어봤죠.
역시 우리으 친절하신 즤선생님,,
RuntimeException과 IllegalArgumentException과 같이 평소에 우리가 사용해도 try-catch 등을 쓰지 않아도 되는 Exception들은 Unchecked Exception이라고 합니다! 그에 반해, 일반 Exception은 Checked Exception이라고 try-catch나 throws를 해야된다고 하네요.
그래서 아무튼 Exception이 아닌 것들 중 가장 무난한 RuntimeException을 채택하였습니다.
그 후 원래 제가 만들어놨던 GlobalExceptionHandler 안에 제 작고 소중한 CustomException도 추가해줬어요...><