Java 코딩테스트 공부/Java 알고리즘 공부

Java 정렬, 이분검색과 결정알고리즘 3

2022. 11. 4. 00:11

https://www.inflearn.com/course/%EC%9E%90%EB%B0%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%ED%85%8C%EB%8C%80%EB%B9%84/dashboard

 

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 - 인프런 | 강의

자바(Java)로 코딩테스트를 준비하시는 분을 위한 강좌입니다. 코딩테스트에서 가장 많이 출제되는 Top 10 Topic을 다루고 있습니다. 주제와 연동하여 기초문제부터 중급문제까지 단계적으로 구성

www.inflearn.com

 

 

문제 8 :

임의의 N개 숫자 입력으로 주어진다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면

M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을 작성하여라

첫 줄에 N M 이 주어지고

두 번째 줄에 N개의 숫자 입력이 주어진다.

 

풀이 :

이분 검색 알고리즘을 통해 문제를 해결한다.

이분 검색은 검색할 범위를 반으로 줄여가며 찾아가는 알고리즘이다.

mid = (lt + rt) / 2 에서

arr[mid] == m이면 찾은 것이다.

arr[mid] > m이면 오른쪽 반을 날려버리면 된다. rt = mid - 1 하는 것이다.

else (arr[mid] < m)이면 lt = mid + 1 해주면 된다.

 

소스코드 :

import java.util.*;
class Main {
	public int solution(int n, int m, int[] arr) {
		int answer = 0;
		Arrays.sort(arr);
		int lt = 0, rt = n-1;
		while(lt <= rt) {
			int mid = (lt +rt) / 2;
			if (arr[mid] == m) {
				answer = mid + 1;
				break;
			}
			if (arr[mid] > m) rt = mid -1;
			else lt = mid + 1;
		}
		return answer;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[] arr = new int[n];
		for(int i=0; i<n; i++) {
			arr[i] = sc.nextInt();
		}
		System.out.println(T.solution(n, m, arr));
	}
}

 

 

 

문제 9 :

첫째 줄에 곡의 개수 N과, M개의 DVD로 나눠 담을 M이 주어진다.

그 다음 줄에 각각의 곡의 길이(분 단위)가 주어진다.

첫 번째 줄부터 DVD의 최소 용량 크기를 출력하라. 단, 부른 순서는 바뀌지 않는다.

입력예제

9 3

1 2 3 4 5 6 7 8 9

출력예제

17

 

풀이 :

매개변수 탐색 알고리즘(Parametric Search)을 통해 문제를 해결할 수 있다.

구하고자 하는 답이 lt부터 rt 사이에 분명히 있다고 확신이 들 경우 적용할 수 있는 알고리즘이다.

여기서 구하고자 하는 답은 DVD의 최소 용량이고, lt는 최대값인 9, rt는 노래들 길이를 다 합한 값인 45 이다.

여기서 이분 검색을 사용한다.

lt = 9  mid = 27  rt = 45

그럼 이제 여기서 27을 DVD 한 장의 용량이라고 보는 것이다.

이렇게 용량이 27인 DVD 3장(M)의 DVD에다 9개(N)의 곡들이 담길 수 있나 보면 된다.

 

1 2 3 4 5 6  /  7 8 9  이렇게 2장 안에도 담긴다. 당연히 그러면 3장 안에도 담긴다는 것이다.

이렇게 담길 수 있나 확인하는 함수를 나중에 만들어야 한다.

어쨌든, 이렇게 mid값인 27로 3장의 DVD에 곡들이 담긴다는 것을 확인했으니 27보다 큰 값들을 볼 필요가 없다.

그럼 이제 rt값은 mid - 1인 26으로 설정된다. (현재 answer값 27)

 

lt = 9  mid = 17  rt = 26

다시 17이 답으로써 가능한 숫자인가 확인하면 된다.

1, 2, 3, 4, 5 이렇게 한계까지 1번째 DVD에 담고

6, 7을 2번째 DVD에 담는다.

그리고 8, 9를 3번째 DVD에 담는다.

이렇게 17이 답으로 가능한 숫자인 것을 확인할 수 있다. (현재 answer값 17)

17보다 큰 수들은 볼 필요가 없다. 이제 17보다 더 작은 것이 답이 될 수 있나 또 검색해봐야 한다.

 

lt = 9  mid = 12  rt = 16

1, 2, 3, 4  /  5, 6  / 7, 8..(X)

mid값인 12 안에 안 담긴다는 것을 확인할 수 있다.

이제 여기서 13부터 rt값인 16까지 검색해본다.

lt = mid + 1인 13으로 설정하고, rt = 16

lt++를 하며 13부터 16까지 검색해본다.

while (lt<=rt) 검색할텐데 13부터 16까지 못 담게되면 lt값이 rt보다 커지는 17일 때 멈추게 된다.

그렇게 17이라는 정답을 찾아낼 수 있다.

 

이해를 돕기 위해 그림을 그려보았다.

 

 

소스코드 :

import java.util.*;
class Main {
	public int count(int[] arr, int capacity) {
		int cnt = 1, sum = 0;
		for (int x : arr) {
			if (sum + x > capacity) {
				cnt++;
				sum = x;  // 끊긴 수 부터 시작해야 하므로
			}
			else sum += x;
		}
		return cnt;
	}

	public int solution(int n, int m, int[] arr) {
		int answer = 0;
		//Arrays.sort(arr);
		int lt = Arrays.stream(arr).max().getAsInt();
		int rt = Arrays.stream(arr).sum();
		while (lt <= rt) {
			int mid = (lt + rt) / 2;
			if (count(arr, mid) <= m) {
				answer = mid;
				rt = mid - 1;
			}
			else lt = mid + 1;
		}
		return answer;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[] arr = new int[n];
		for(int i=0; i<n; i++) arr[i] = sc.nextInt();
		System.out.println(T.solution(n, m, arr));
	}
}

 

 

문제 10 :

말들이 서로 가까이 있는 것을 좋아하지 않는다.

N 개의 마구간에 C 마리의 말을 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는

그 최대값을 출력하는 프로그램을 작성하시오.

첫 줄에 자연수 N과 C가 공백을 사이에 두고 주어진다.

둘째 줄에 마구간의 x좌표들이 차례대로 주어진다.

입력예제

5 3

1 2 8 4 9

출력예제

3

 

풀이 :

Parametric Search 알고리즘 통해 문제를 해결할 수 있다.

우선 Arrays.sort(arr) 하면 1 2 4 8 9

lt = 1 , rt = 9(arr에서 최대값) , mid = 5

mid = 5로 잡은 것은 가장 가까운 두 말 최대 거리가 5라고 가정하고 넣어보는 것이다.

따라서 count함수를 만들어 5가 가장 가까운 두 말의 거리인지 갯수를 세서 확인하면 된다.

거리가 5 이상인 말 개수를 세면 된다. 말들을 배치할 때 방금 배치한 말 x좌표를 저장할 ep 변수, 개수를 cnt로 둔다.

cnt가 C의 값보다 크거나 같을 경우 구하고자 하는 값이 현재 mid값보다 크다는 것이므로 lt = mid + 1 한다.

cnt가 C의 값보다 작을 경우 구하고자 하는 값이 현재 mid값보다 작다는 것이므로 rt = mid - 1 한다.

 

소스코드(빠른 입출력 사용) :

import java.util.*;
import java.io.*;
public class Main
{
    public int count(int[] arr, int mid) {
        int ep = arr[0], cnt = 1;
		for(int i=1; i<arr.length; i++) {
			if (arr[i] - ep >= mid) {
				cnt++;
				ep = arr[i];
			}
		}
        return cnt;
    }
    
    public int solution(int n, int c, int[] arr) {
		int answer = 0;
		Arrays.sort(arr);
		int lt = 1, rt = arr[n-1];
		while (lt <= rt) {
			int mid = (lt + rt) / 2;
			if (count(arr, mid) >= c) {
				answer = mid;
				lt = mid + 1;
			}
			else rt = mid - 1;
		}
        return answer;
    }
    
	public static void main(String[] args) throws IOException {
		Main T = new Main();
		//Scanner sc = new Scanner(System.in);
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		int n = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());
		int[] arr = new int[n];
		st = new StringTokenizer(br.readLine()," ");
		for (int i=0; i<n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		br.close();
		bw.write(String.valueOf(T.solution(n, c, arr)));
		bw.flush();
		bw.close();
	}
}

 

 

 

 

 

 

'Java 코딩테스트 공부 > Java 알고리즘 공부' 카테고리의 다른 글

Recursive, Tree, Graph(DFS, BFS 기초) 2 - 이진트리, 부분집합 DFS  (0) 2022.11.12
Recursive, Tree, Graph(DFS, BFS 기초) 1 - 재귀  (0) 2022.11.09
Java 정렬, 이분검색과 결정알고리즘 2  (0) 2022.09.03
Java 정렬, 이분검색과 결정알고리즘 1  (0) 2022.09.02
Java 스택, 큐 알고리즘5 + deque  (0) 2022.08.20
'Java 코딩테스트 공부/Java 알고리즘 공부' 카테고리의 다른 글
  • Recursive, Tree, Graph(DFS, BFS 기초) 2 - 이진트리, 부분집합 DFS
  • Recursive, Tree, Graph(DFS, BFS 기초) 1 - 재귀
  • Java 정렬, 이분검색과 결정알고리즘 2
  • Java 정렬, 이분검색과 결정알고리즘 1
daramG
daramG
dotori Java
daramG
다람쥐의 개발 블로그
daramG
전체
오늘
어제
  • 분류 전체보기 (193)
    • Java 코딩테스트 공부 (67)
      • Java 알고리즘 공부 (37)
      • Java 백준 문제풀이 (27)
      • Java 코테 나만의 팁 (3)
    • SQL Study (0)
      • Programmers SQL 문제풀이 (0)
      • SQLP 준비 (0)
    • 웹 개발 지식 정리 (0)
      • Servlet (0)
      • Java 정리 (0)
    • 자바 스프링 (45)
      • 스프링 공부 (4)
      • 스프링 게시판 프로젝트 (6)
      • 부트 블로그 JPA 프로젝트 (30)
      • react & springboot (5)
      • 스프링 오류창고 (0)
      • 리액트 + 스프링 프로젝트 (0)
      • pf (0)
      • pfError (0)
    • React (6)
      • React 정리 (3)
      • React 오류 창고 (3)
    • C++ 코딩테스트 공부 (중단) (20)
      • c++ 백준 문제풀이 (15)
      • c++ 알고리즘 공부 (5)
    • Unity (3)
      • Unity 공부 (3)
    • WebRTC (2)
      • WebRTC 강의학습 정리 (0)
      • WebRTC 프로젝트 (1)
    • 김영한님의 스프링 강의 학습 (10)
      • 스프링 강의 목차 (1)
      • 인텔리제이 & 스프링 기초 (1)
      • 스프링 핵심 원리 (8)
    • 전공 지식 정리 (40)
      • interview (0)
      • Java (0)
      • 운영체제 (4)
      • 데이터베이스 설계 (10)
      • 소프트웨어 공학 (3)
      • 유닉스 (14)
      • 디지털 논리회로 (0)
      • 인공지능 (7)
      • js (0)
      • etc (2)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 인공지능
  • 데이터베이스 설계
  • 김영한의 스프링 핵심 원리
  • 유닉스
  • 스프링부트 블로그 프로젝트
  • 운영체제
  • 스프링 프로젝트
  • 부트 jpa 게시판 프로젝트
  • React&Spring 강의수강
  • 노마드코더의 zoom클론코딩
  • 김영한 스프링 입문
  • Java 코테 나만의 팁
  • C++ 알고리즘
  • 디지털 논리회로
  • 스프링부트 프로젝트
  • 무서운 이야기
  • 코테 알고리즘
  • 스프링 공부
  • Unity 공부
  • java 알고리즘
  • Java 백준 문제풀이
  • 백준 c++
  • java
  • 김영한 스프링 강의

최근 댓글

최근 글

hELLO · Designed By 정상우.
daramG
Java 정렬, 이분검색과 결정알고리즘 3
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.