728x90
숫자 카드 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());
}
}
}
오늘의 회고
오늘은 단순 수학문제와 이분 탐색 문제를 풀었습니다. 이분 탐색 문제를 그 전에도 풀어봐서 금방 해결할 수 있을 것이라고 생각했는데 조금만 응용해서 나오면 풀지 못하는 문제가 발생했습니다. 문제를 해결할 때 넓은 시야로 접근하는 방법에 대해 공부를 해야 될 것 같습니다. 알고리즘을 공부해도 잘 늘지 않는 것 같습니다ㅠㅠ 더 열심히 공부하겠습니다.
728x90
'알고리즘 > 알고리즘 문제풀이' 카테고리의 다른 글
| 백준) BFS, 다익스트라 (0) | 2022.07.19 |
|---|---|
| 백준) 우선순위 큐, DP (0) | 2022.07.18 |
| 백준) 수학, 이분 탐색 (0) | 2022.07.13 |
| Do it! 알고리즘 코딩 테스트(87번 ~ 88번) (0) | 2022.07.12 |
| Do it! 알고리즘 코딩 테스트(85번 ~ 86번) (0) | 2022.07.05 |
