인프런, 자바(Java) 알고리즘 문제풀이
Sorting and Searching - 0610. 마구간 정하기
🗒️ 문제
🎈 나의 풀이
private static boolean stableCheck(int[] arr, int distance, int m) {
int p = arr[0];
m--;
for(int i=1; i<arr.length; i++) {
if(arr[i] - p >= distance) {
m--;
p = arr[i];
}
if(m == 0) return true;
}
return false;
}
private static int solution(int n, int m, int[] arr) {
int answer = 0;
int lt = 1;
int rt = arr[n-1];
while(lt <= rt) {
int mid = (lt + rt) / 2;
if(stableCheck(arr, mid, m)) {
answer = mid;
lt = mid + 1;
} else rt = mid - 1;
}
return answer;
}
public static void main(String[] args) {
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();
Arrays.sort(arr);
System.out.println(solution(n, m, arr));
}🖍️ 강의 풀이
public int count(int[] arr, int dist){
int cnt=1;
int ep=arr[0];
for(int i=1; i<arr.length; i++){
if(arr[i]-ep>=dist){
cnt++;
ep=arr[i];
}
}
return cnt;
}
public int solution(int n, int c, int[] arr){
int answer=0;
Arrays.sort(arr);
int lt=1;
int 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){
Main T = new Main();
Scanner kb = new Scanner(System.in);
int n=kb.nextInt();
int c=kb.nextInt();
int[] arr=new int[n];
for(int i=0; i<n; i++) arr[i]=kb.nextInt();
System.out.println(T.solution(n, c, arr));
}💬 짚어가기
해당 문제는 결정 알고리즘을 이용하여 해결할 수 있다. 나의 풀이에서는 lt에 마구간 사이 거리의
최소값인 1을 담고, rt에는 마구간의 마지막 좌표를 담은 후 이분탐색을 통해 최적의 값을 찾도록
구성하였다.
stableCheck() 메소드에서는 전달 받은 distance로 마구간에 m개의 말을 채울 수 있는지
확인하는 메서드이다. 반복문으로 모든 마구간을 순회하며 p 마구간의 좌표에서 현재 인덱스의
마구간 좌표 값의 차가 distance 보다 크거나 같은 경우 m(말의 수)을 -1하는 로직이다.
(중간에 m이 음수인 경우 반복문을 종료하는 코드를 추가하면 시간을 단축할 수 있을 것 같다.)
강의 풀이에서는 마찬가지로 이분탐색을 수행한다. count() 메소드 또한 같은 방식으로 마구간에
들어갈 수 있는 최대 말의 마리수를 반환한다. 이후 조건에 따라 이분 탐색을 수행하여 문제를 해결한다.
☕️ 여담으로
아래는 결정 알고리즘에 무지한 채로 멍청하게 삽질한 기록이다..🥲
내가 짰지만 겨우 하루 지난 시점에 벌써 읽기가 힘들다ㅋㅋ
public static class Stable {
public boolean horse = false;
public int x = 0;
public int distance = 0;
public Stable(int x) {
this.x = x;
}
}
private static int solution(int n, int m, int[] arr) {
Arrays.sort(arr);
List<Stable> list = new ArrayList<>();
for(int i : arr) list.add(new Stable(i));
list.get(0).horse = true;
list.get(list.size() - 1).horse = true;
m = m - 2;
if(m == 0) {
return Math.abs(list.get(0).x - list.get(list.size() - 1).x);
}
while(m > 0) {
for(int i=1; i<list.size() - 1; i++) {
Stable s = list.get(i);
if(!s.horse) {
int next = 1;
while (true) {
Stable f = list.get(i + next);
if (f.horse) {
s.distance = Math.abs(s.x - f.x);
break;
} else next++;
}
next = 1;
while (true) {
Stable f = list.get(i - next);
if (f.horse) {
s.distance = Math.min(s.distance, Math.abs(s.x - f.x));
break;
} else next++;
}
}
}
int maxDis = 0;
int index = 0;
for(int i=1; i<list.size() - 1; i++) {
Stable s = list.get(i);
if(!s.horse && s.distance > maxDis) {
index = i;
maxDis = s.distance;
}
}
list.get(index).horse = true;
m--;
if(m == 0) return maxDis;
}
return 0;
}
public static void main(String[] args) {
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(solution(n, m, arr));
}우선, Stable 클래스를 만들어 마구간이 말을 가졌는지의 유무를 체크하고, 마구간의 x좌표를
보관할 수 있는 변수와, 특정 마구간과의 거리를 보관할 수 있는 distance 변수를 생성했다.
로직의 흐름
-
마구간을
Stable객체로 생성하기
마구간 배열을 순회하며 모두 객체로 만들어 준다. 이를list에 추가한다. -
말 2 마리 넣기
말은 최소 2 마리 이상이다. 따라서 두 말의 거리가 최대가 될 수 있도록 1번 마구간과 마지막
마구간에 말을 넣는다. -
조건 체크 : 말이 단 2마리인 경우
만약 말이 2마리 뿐이라면 바로 두 마구간 사이의 거리를 리턴한다.
(사실 해당 코드는 테스트 케이스에서 말이 2마리인 경우에 실패하여 추가한 어거지 조건문이다.) -
말이 들어있는 마구간과의 거리 구하기
반복문으로 빈 마구간을 순회하며, 이후 마구간 중 말이 들어있는 마구간까지 사이의 거리를Stable
객체의distance에 보관한다. -
말이 들어있는 마구간과의 최소 거리 구하기
이전과 반대 방향으로 빈 마구간을 순회하며, 이전 마구간 중 말이 들어있는 마구간까지 사이의 거리를
기존에 저장되어있는distance값과 비교하여, 더 긴 값을 보관한다. -
거리가 가장 긴 마구간 찾기
빈 마구간중distance가 가장 긴 마구간에 말을 보관한다. -
4~6번 과정을 반복하며 말들을 마구간에 보관하고, 마지막 말을 보관할 할 때 최대distance를
반환한다.
위와 같은 흐름으로 코드를 작성하였는데, 결과는 오답! 통과하지 못하는 테스트 케이스가 발생하였다.
생각해보니 내 로직은 말을 순차적으로 넣을 때에만 해당되며, 문제에서 요구하는 말 보관 방식이 아니다.
삽질 끝에 로직 전체를 새로 짰다...
