[커뮤러닝/9기/Java] 2. 1주차 문제 (1)

2023-01-11부터 시작한 커뮤러닝 9기 Java 프로그램 수업이 시작했다.

 

1주차의 커리큘럼으로 그리디 / 정렬 / 이분탐색 / 시뮬레이션이 있으며 오늘까지 총 1주차의 8문제 중 4문제를 접근했다.

 

0) 공통

- 하루에 하나의 문제유형으로 풀기 시작했다.

- (※ 각 하루마다 푸는 2번째 문제는 저작권 문제로 넘어가겠습니다.)

 

1) 1일차

문제 설명

N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5g 기지국은 4g 기지국보다 전달 범위가 좁아, 4g 기지국을 5g 기지국으로 바꾸면 어떤 아파트에는 전파가 도달하지 않습니다.

예를 들어 11개의 아파트가 쭉 늘어서 있고, [4, 11] 번째 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 만약 이 4g 기지국이 전파 도달 거리가 1인 5g 기지국으로 바뀔 경우 모든 아파트에 전파를 전달할 수 없습니다. (전파의 도달 거리가 W일 땐, 기지국이 설치된 아파트를 기준으로 전파를 양쪽으로 W만큼 전달할 수 있습니다.)

• 초기에, 1, 2, 6, 7, 8, 9번째 아파트에는 전파가 전달되지 않습니다.

• 1, 7, 9번째 아파트 옥상에 기지국을 설치할 경우, 모든 아파트에 전파를 전달할 수 있습니다.

• 3개의 아파트보다 더 많은 아파트 옥상에 기지국을 설치할 경우에도 모든 아파트에 전파를 전달할 수 있습니다.

이때, 우리는 기지국을 최소로 설치하면서 모든 아파트에 전파를 전달하려고 합니다. 위의 예시에선 최소 3개의 아파트 옥상에 기지국을 설치해야 모든 아파트에 전파를 전달할 수 있습니다.

아파트의 개수 N, 현재 기지국이 설치된 아파트의 번호가 담긴 1차원 배열 stations, 전파의 도달 거리 W가 매개변수로 주어질 때, 모든 아파트에 전파를 전달하기 위해 증설해야 할 기지국 개수의 최솟값을 리턴하는 solution 함수를 완성해주세요

제한사항

• N: 200,000,000 이하의 자연수
• stations의 크기: 10,000 이하의 자연수
• stations는 오름차순으로 정렬되어 있고, 배열에 담긴 수는 N보다 같거나 작은 자연수입니다.
• W: 10,000 이하의 자연수

입출력 예

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다

입출력 예 #2

• 초기에, 1~6, 12~16번째 아파트에는 전파가 전달되지 않습니다.

• 3, 6, 14번째 아파트 옥상에 기지국을 설치할 경우 모든 아파트에 전파를 전달할 수 있습니다.

 

- 첫번째 문제는 "기지국 설치", Level3의 자바 문제가 나왔다. 

https://school.programmers.co.kr/learn/courses/30/lessons/12979

- 처음에는 N이 200,000,000으로 되어있어 이분탐색으로 접근하였지만 이분탐색의 문제점으로 중앙을 강조하여 하나씩 더 추가되는 경우가 생겼다. (풀이 설명 : https://velog.io/@qodlstjd12/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EA%B8%B0%EC%A7%80%EA%B5%AD-%EC%84%A4%EC%B9%98-Java)

- 계속 풀다가 전혀 몰라 문제를 끝내고 게시되어 있는 수업과 설명을 들었고 너무나도 단순하고, 쉽게 설명을 하였고 이를 계속 적어가며 풀었습니다.

- 풀이하면서 알게 된 것 : 처음부터 쭉 2 * w + 1 만큼 비어있는지 확인하고 다음 값이 현재 보여주고 있던 stations(기지국) 배열의 인덱스에 해당하는 최소값 범위보다 큰 경우 이를 전파에 속한 기지국에 위치하기 때문에 이를 무시하고 stations의 인덱스를 증가시키고(중요1) 해당 stations 인덱스의 전파 거리 최대값 + 1로 넘겨야하는 것(중요2)으로 계속해서 하나씩 확인 할 수 있는 최적해를 찾는 그리디(Greedy) 알고리즘이라는 것을 판단 할 수 있게 되었습니다.

 

class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        int si = 0;
        int position = 1;
        
        while(position <= n) {
            // 기지국의 위치가 아직 판명이 되며, 기지국 최저 전파 위치보다 크다면
            if(si < stations.length && stations[si] - w <= position) {
                position = stations[si] + w + 1; // 현재 기지국의 최대 전파 위치의 한칸 앞으로 배치
                si++; // 다음 기지국 위치로 조정
            } else {
                answer++;
                position += 2 * w + 1;
            }
        }

        return answer;
    }
}

 

2) 2일차

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

입출력 예

- 2일차의 첫번째 문제는 '가장 큰 수', Level2의 자바 문제가 나왔다.

- 주어진 정수를 통해 가장 큰 값을 만드는 것이기 때문에 바로 Arrays.sort와 Comparator를 생각했고 이는 맞았습니다.

- 허나, 이제 숫자에 대해 정렬을 할 때 각 숫자를 String으로 변경 후 charAt(0)의 내림차순을 하면서 charAt(0)가 같을 경우에 추가로 조건을 걸었습니다.

- 주어진 테스트케이스에서 [3, 30, 34]를 확인할 때 각 숫자의 길이만큼 for문을 돌려 charAt(0)보다 작은 값이 있다면 해당 숫자의 count를 감소, 같거나 큰 값이 있다면 count를 증가하여 count 비교하여 정렬하는 식으로 테스트 케이스에는 넘어갔지만

 

[30, 34, 330, 310, 309, 301] 와 같이 charAt(0)이 같은 여러가지를 정렬했을 때, 309가 310보다 낮게 나와야함에도 불구하고 309 -> count = 0(0에서 감소, 9에서 증가), 310 -> count = -1(0, 1 에서 감소) 로 원하는 정렬이 나타나지 않았습니다.

 

[틀린 코드]

Arrays.sort(nums, (o1, o2) -> {
    // 맨 앞의 숫자가 같다면 추가해야하는 조건들이 있다.
    if(o1.charAt(0) == o2.charAt(0)) {
        if(o1.length() != o2.length()) {
            int count1 = 0, count2 = 0;
            for(int i = 1; i < o1.length(); i++) {
                if(o1.charAt(0) > o1.charAt(i)) count1--;
                else count1++;
            }

            for(int i = 1; i < o2.length(); i++) {
                if(o2.charAt(0) > o2.charAt(i)) count2--;
                else count2++;
            }
            return -(count1 - count2);
        } else {
            return -(Integer.parseInt(o1) - Integer.parseInt(o2));
        }
    } else {
        return -(o1.charAt(0) - o2.charAt(0));
    }
});

어떻게 하면 정렬을 할 수 있을까 했던 것을 조금 고민하다가 금방 해결하였습니다.

 

[정답 코드]

Arrays.sort(nums, (o1, o2) -> {
    return (o2+o1).compareTo(o1+o2);
});

이와 같이 단 한 줄로 두 정수의 String 합계를 앞뒤로 바꾸며 큰 값을 비교하는 것이었습니다.

 

이와 바꾸고 0으로만 구성된 값이 존재했을 경우 0으로 치환하는 문제만 해결하고 100점을 맞게되어 처음으로 스스로 풀게 된 것에 기뻐했습니다.

 

내일도 어떤 문제가 나와 절 다듬을 수 있을지 궁금합니다.