흠 어려워 보이는 걸
갑자기 알게된 사실 ?
일단 k랑 n을 받으려고
StringTokenizer st = new StringTokenizer(br.readLine());
int k = Integer.parseInt(st.nextToken());
int n = Integer.parseInt(st.nextToken());
이렇게 했다. 한 줄을 읽어서 공백 기준으로 잘라서 각각의 변수에 저장 !
그리고 이미 가지고있는 전선의 길이를 배열에 저장하려고 했는데
for(int i=0;i<k;i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
그냥 이렇게 하니까 안 됐음
Y? 다음 줄의 입력을 받아서 st.nextToken으로 찢어야되는데 입력이 없으니까 !
for(int i=0;i<k;i++) {
st = new StringTokenizer(br.readLine());
arr[i] = Integer.parseInt(st.nextToken());
}
요렇게 해야함 !
암튼 그래서 잘 입력 받았고
전선의 갯수와 길이를 입력을 받고 여기서 필요한 갯수만큼을 잘라내서 만들었을 때의 전선의 최대 길이 !
필요한 전선의 갯수를 구할 때까지 반복문
그 안에 배열(이미 갖고있는 전선의 갯수가 들어있는)의 길이만큼 반복을 해서 잘라내는 반복문
{ 어떻게 잘라내냐면 배열의 요소를 끄집어내서 계속 증가하는 수 num으로 나눠
1. 모든 요소를 다 나눌 수 있는지를 조건문으로 검사
2. 다 나눠진다면 나눠진 몫을 count로 헤아려 (흠 그러면 맨 처음 반복문을 while로 해야될 듯)
그 count가 필요한 전선의 갯수랑 같다면 반복문 break;
3. 아 근데 그 중에 최대의 길이를 구해야하니까 max로 최대 전선의 길이를 만족할 때까지 반복을 또 걸어줘야할 듯 ?
대충 구상은 끝 낼 구현해보쟝
3/19
위의 알고리즘에서 수정사항을 거쳐서 햇는데 시간초과가 나와서
1. while문을 true로 계속 반복시켜서 그 안에
for문 하나를 둠.{ 배열 요소의 길이만큼 반복을 할 거고
하나의 배열요소를 계속 증가할 수인 length로 나눠줘서 그 몫을 num에 저장. count라는 변수에 num을 계속 더 해나감.
-> 이 두 줄을 걍 num배열을 없애고 한 줄로 진행. // 이 부분을 한 줄로 바꾸니까 2%진행은 되는데 또 시간초과 나옴.
조건 if (arr[i]/length ==0)이면 어느 한 요소를 나눠서 쓸 수 없는 거니까 continue로 했는데 이게 아닌 break같다.
조건 if(count ==n) 이면{그 안에 if (max < length){ max = length; break; } 전선의 최댓값을 구해.
}// for문 끝
if(length > Array.stream(arr).max().getAsInt())
break; // 나눠줄 길이가 배열의 최댓값 요소보다 커지면 while도 종
}//while문 끝
이렇게 하니까 생각보다 간단하게 문제는 풀었는데 시간초과가 나온다.
package algorithm;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main{
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()); // 이미 갖고 있는 랜선의 갯수
int n = Integer.parseInt(st.nextToken()); // 필요한 랜선의 갯수
int arr[] = new int[k]; //갖고있는 랜선의 길이값을 저장할 배열
int length = 0; //계속 증가하며 기존 랜선을 잘라낼 랜선의 길이
int max = 0; //랜선 길이의 최댓값을 비교해주고 저장할 변수
int count =0; //잘라낸 랜선의 갯수 세기
int num =0; //length로 나눠져서 생긴 랜선의 갯수
for(int i=0;i<k;i++) {
st = new StringTokenizer(br.readLine());
arr[i] = Integer.parseInt(st.nextToken());
}//전선의 길이를 배열에 저장
while(true) {
count = 0;
length++; //계속 증가하며 배열요소와 나눠줄 전선의 길이
for(int i=0;i<k;i++) {//배열의 길이만큼 반복
//num = arr[i] / length;
count+=arr[i] / length; //잘라진 전선의 갯수
if(arr[i] / length == 0)
break; //랜선의 길이가 잘라낼 랜선의 길이보다 작으면 계속 반복 진행
if(count == n) {
if(max < length)
max=length;
break; //그냥 끝내면 안 되고 그때의 전선의 길이가 최댓값인지를 구해야함.
}
}
if(length > Arrays.stream(arr).max().getAsInt()) //나눠줄 길이가 배열의 최댓값 요소보다 커지면
break;
}
System.out.println(max);
}
}
일단 처음 완성 코드
어떻게 하면 시간을 줄일 수 있을까 ?
이문제는 이진탐색을 사용해야한다고 한다 !
와우..... 또 하나 배웠다. 하긴 1씩 늘려서 하는게 의미는 없어보인다. 의미는 있을지 몰라도 시간이 오래걸리니 결국 의미가 없어진다 ! 그럼 이진탐색을 어떻게 구현하는지 알아야겠다
- 구현
- 배열을 정렬한다.
- 중간값을 구한다. mid = (low + high) /2
- array[mid] 값과 구하고자 하는 key값을 비교한다.
- key > mid : low = mid + 1 (왼쪽 반을 버림)
- key < mid : high = mid -1 (오른쪽 반을 버림)
- key == mid : 구하고자 하는 값을 찾음. → 중간 값 리턴
- low > high가 될 때까지 1~3 반복
되게 간단한데 이 이진탐색을 어디에 적용해야하냐 ? 바로 length를 1씩 증가해서 비교해주지말고 이진탐색으로 비교.. 인데 그러면 그 값이 담긴 배열이 있어야 하지 않나 ? ㅠ 그거 담는데도 시간이 걸릴 것 같은데 ....
아 ! 그 기준을 배열 요소의 최소값의 중간값으로 잡으면 되겠다 !
후 ㅋ 너무 어지러워서 슬쩍 답안 참고함
BinarySearch에서는 정렬이 필수
아 근데 왜 자꾸 틀렸대 ????????????????????????? 짜증난다
와 .. 자료형으로 long을 안 써줘서 계속 틀렸었따
총 정리 다시 ....
일단 여기서 썼던 배열의 최댓값 구하는 함수
스트림 형태로 만들고 max(), min()을 사용해준뒤 꺼내오면 됨.
Arrays.stream(배열이름).max().getAsInt()
Arrays.stream(배열이름).min().getAsInt()
자료형을 long(8bytes== 64 bit)을 써야했다. (int는 4bytes == 32bit). 조건에 랜선의 길이는 2의 31승 -1 이라고 하였는데
mid를 구할 때 low + high를 하게되면 int의 범위인 2의 31승을 넘기 때문이당.
package algorithm;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main{
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()); // 이미 갖고 있는 랜선의 갯수
int n = Integer.parseInt(st.nextToken()); // 필요한 랜선의 갯수
int arr[] = new int[k]; //갖고있는 랜선의 길이값을 저장할 배열
for(int i=0;i<k;i++) {
arr[i] = Integer.parseInt(br.readLine());
}//전선의 길이를 배열에 저장
Arrays.sort(arr); //랜선 길이값을 오름차순 정렬
int count =0;//잘라낸 전선의 갯수
long low = 0;
long high =arr[k-1];
long mid;
while(low <=high) {
count=0;
mid = (low+high)/2;
for(int i=0;i<k;i++)
count += arr[i] / mid;
if(count < n) {
high = mid -1;
}
else if(count >= n) {
low = mid + 1;
}
}
System.out.println(high);
}
}
이진탐색을 알게된 좋은 알고리즘 !
이진탐색은 정렬 필수 !
근데 마지막...으로 저기 low를 0으로 하면 Run Time Error (/by zero)가 뜬다.. ! ㅜ
1로 해야함 이건 왜인지 잘 모르겠는 걸 ㅠ
0으로 나누면 오류가 난다고 하는데 여기서 나누는 코드는
count += arr[i] / mid; 이거 밖에 없다. 윗줄에서 mid = (low+high)/2 여기서 mid가 0이 나오면 저 런타임에러가 뜨므로 음.. high가 0이되고 low는 0부터 시작하게되면 mid도 0이어서 high가 0이 되어도 에러나는 것을 막기 위해 low를 1부터 시작해줌.
뭐하나 쉬운게 없군
4/11
2805번 나무자르기 문제를 풀 때 이분탐색을 써서 이 글을 다시 참고했다.
그러면서 자료형을 long형으로 설정해야할 일이 있어서 공부해보다가 이것도 다시 풀어보게 되었는데
mid를 일단 long으로 해야하는 건 맞다. 극단적으로 나무의 길이가 2의 31승 -1 이었다고 할 때 high랑 low도 같은 값이었다고 치면 mid는 high+low 하고 /2를 하니까 아직은 안 넘음. 근데 count 조건에 따라 low가 mid+1이 될 때 int자료형 최대값을 넘어버림. 그럼 low가 long형이 되어야하고 low와 high값이 더해져서 mid가 되니까 high도 mid도 그냥 다 long형이어야한다. 근데 틀렸다네 왜
package algorithm;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
class Main{
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());
int N = Integer.parseInt(st.nextToken());
Integer arr[] = new Integer[K];
for(int i = 0;i<K;i++) {
arr[i] = Integer.parseInt(br.readLine());
}
//이진탐색
Arrays.sort(arr);
long high = arr[arr.length-1]/2;
long low = 0;
long mid = 0;
while(low<=high) {
int count = 0;
mid = (high+low)/2;
for(int i=0;i<K;i++) {
count += arr[i] / mid;
}
if(count < N) {
high = mid - 1;
}
else if(count >=N) {
low = mid + 1;
}
}
System.out.println(high);
}
}
아하 저기서 high를 젤 마지막 요소 /2를 해주면 안 됐음
근데 그거 고쳤더니 by zero 오류가 났당. 음 이게 high도 0이고 low도 0일 때 /2를 해서 생기는 오류라 low의 초기값을 1로 해줘야할 것 같다.
전보단 훨씬 수월하게 이해가 되네 끄읏 ~
'알고리즘 > 백준' 카테고리의 다른 글
1920번 문제 : 수 찾기 (0) | 2023.03.20 |
---|---|
1874번 문제 : 스택 수열 (0) | 2023.03.19 |
1436번 문제 : 영화감독 (0) | 2023.03.18 |
1259번 문제 : 팰린드롬수 (0) | 2023.03.17 |
1018번 문제 : 체스판 다시 칠하기 (0) | 2023.03.16 |