고민의 흔적

숫자 카드 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());
		}
	}
}

오늘의 회고

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

1978번 소수 찾기

내가 떠올린 풀이 해설

소수를 찾는 기본 문제이다. 소수를 찾기 위해 아래의 코드를 추가시켰다.

for(int j = 2; j < arr[i]; j++) {
   if(arr[i] % j == 0) {
      isPrime = false;
      break;
   }

위의 코드 if문이 실행되면 소수가 아니므로 isPrime에 false를 하고 break로 빠져나왔다. 마지막에 만약 isPrime이면 cnt를 늘려주는 식으로 소수의 개수를 구했다.

정확한 풀이

import java.util.*;
public class Baek1978 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n  = sc.nextInt();
		int[] arr = new int[n];
		for(int i = 0 ; i < n; i++) {
			arr[i] = sc.nextInt();
		}
		int cnt = 0;
		for(int i = 0; i < n; i++) {
			boolean isPrime = true;
			if(arr[i] == 1) {
				continue;
			}
			for(int j = 2; j < arr[i]; j++) {
				if(arr[i] % j == 0) {
					isPrime = false;
					break;
				}
			}
			if(isPrime) {
				cnt++;
			}
		}
		System.out.println(cnt);
	}
}

1654번 랜선 자르기

내가 떠올린 풀이 해설

변수의 크기를 고려해서 변수를 선언해야 된다. 그렇지 않으면 답이 틀렸다고 나온다. 이 문제 또한 기본 이분 탐색 문제이다. 렌선의 최소 길이인 1로 start를 잡고 end는 렌선 배열의 최대 값을 선언해준다.  while문에서 start가 end보다 작거나 같을 때까지 반복한다. while문 안에서 이분 탐색으로 총 만들 수 있는 개수를 구해주면 된다.

정확한 풀이

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

public class Baek1654 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int k = Integer.parseInt(st.nextToken());
		long n = Long.parseLong(st.nextToken());
		
		long[] arr = new long[k];
		for(int i = 0; i < k; i++) {
			arr[i] = Long.parseLong(br.readLine());
		}
		Arrays.sort(arr);
		
		long start = 1;
		long end = arr[k - 1];
		long mid = 0;
		
		while(start <= end) {
			mid = (start + end) / 2;
			int sum = 0;
			for(int i = 0; i < k; i++) {
				sum += arr[i] / mid;
			}
			if(sum < n) {
				end = mid - 1;
			}
			else {
				start = mid + 1;
			}
		}
		System.out.println(end);
	}
}

오늘의 회고

기본 문제들이라 문제를 해결하는데 어려움은 없었습니다.

제가 이번에 스터디에 참여하게 되었습니다. 주제를 잡고 스터디하는 것이 아니라 모여서 각자 코딩하고 어떤 공부를 하는지 이야기하는 모임입니다. 일요일에 처음 참여하게 되었는데 앞으로도 다른 스터디나 스터디를 꾸준히 할 생각입니다. 스터디에 참여하게 된 이유는 따로 같은 분야에 계신 선배님들을 만날 기회가 없고 스터디 카페에 박혀있어 우울해지는 것 같아 참여하게 되었습니다. 스터디에 계신 분들도 다 저보다 연차가 높은 선배님들이라 열심히 배우겠습니다. 내일은 프로그래머스 중간고사가 있어서 중간고사 시험을 보고 오겠습니다. 중간고사 문제는 외부로 유출이 안돼서 블로그에 작성은 하지 못할 것 같습니다.