백준) 수학(피타고라스), 이분 탐색

숫자 카드 2 10816번

---

내가 떠올린 풀이 해설

이분 탐색 문제를 풀어봤었지만 조금만 응용하니까 못 푸는 문제가 발생했다. 이 문제는 이분 탐색으로 상한 과 하한을 구해서 그 길이를 빼서 같은 값의 길이를 구하는 문제이다. 하한을 구하는 메서드에서 만약 찾으려는 값이 arr배열 mid위치의 값보다 같거나 작을 때 end를 mid값으로 바꾸고 조건에 만족하지 않을 때 start를 mid + 1 값으로 바꾼다. 상한의 경우에는 찾으려는 값이 arr배열 mid 위치의 값 보다 크거나 같을 때 start 값을 mid + 1의 값으로 바꾸고 조건에 만족하지 않으면 end 값을 mid 값으로 바꿔준다. 

---

정확한 풀이

import java.util.*;
import java.io.*;

public class Baek10816 {
	static int[] arr;
	static int n;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		n = Integer.parseInt(br.readLine());
		arr = new int[n];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr);
		
		int m = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < m; i++) {
			int find = Integer.parseInt(st.nextToken());
			bw.append((right(find) - left(find)) + " ");
		}
		bw.flush();
		bw.close();
	}

	private static int left(int find) {
		int start = 0;
		int end = n;
		while(start < end) {
			int mid = (start + end) / 2;
			if(find <= arr[mid]) {
				end = mid;
			}
			else {
				start = mid + 1;
			}
		}
		return start;
	}

	private static int right(int find) {
		int start = 0;
		int end = n;
		while(start < end) {
			int mid = (start + end) / 2;
			if(find >= arr[mid]) {
				start = mid + 1;
			}
			else {
				end = mid;
			}
		}
		return start;
	}
}

---

직각 삼각형 4153번

---

내가 떠올린 풀이 해설

단순히 구현문제인것 같다. 하지만 이렇게 코드를 짜면 정답은 나오지만 좋지 않은 풀이인 것 같다. 단순이 if, else if, else로 피타고라스 정리를 이용해 풀었다. 각 변을 제곱해서 두 변을 합한 값이 다른 값과 같으면 right 다르면 wrong으로 풀었다.

---

정확한 풀이

import java.util.*;
import java.io.*;

public class Baek4153 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int h = Integer.parseInt(st.nextToken());
		while(n != 0) {
			if((n*n + m*m) == h*h) {
				System.out.println("right");
			}
			else if((h*h + m*m) == n*n) {
				System.out.println("right");
			}
			else if((n*n + h*h) == m*m) {
				System.out.println("right");
			}
			else {
				System.out.println("wrong");
			}
			st = new StringTokenizer(br.readLine());
			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());
			h = Integer.parseInt(st.nextToken());
		}
	}
}

---

오늘의 회고

오늘은 단순 수학문제와 이분 탐색 문제를 풀었습니다. 이분 탐색 문제를 그 전에도 풀어봐서 금방 해결할 수 있을 것이라고 생각했는데 조금만 응용해서 나오면 풀지 못하는 문제가 발생했습니다. 문제를 해결할 때 넓은 시야로 접근하는 방법에 대해 공부를 해야 될 것 같습니다. 알고리즘을 공부해도 잘 늘지 않는 것 같습니다ㅠㅠ 더 열심히 공부하겠습니다.