소소한 개발일지

문제

정수 n과 k 그리고 정수배열 n의 길이의 speed와 efficiency가 주어졌습니다. 1부터 n까지 n명의 엔지니어가 있으며 speed[i]와 efficiency[i]는 i번째 엔지니어의 속도와 효율을 의미합니다.

최대 k명의 다른 엔지니어를 n명 중에 선택하여 최대 performance를 낼 수 있는 팀을 만드세요.

팀의 performance는 엔지니어들의 speed를 더한 값에 선택한 엔지니어들 중 최소 efficiency를 곱한 값 입니다.

팀의 최대 performance를 반환하세요. 답이 큰 수일 수 있으니, 답에 modulo \(10^9 + 7\) 연산 후 반환하세요.

예시

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
Output: 60
최대 performance를 낼 수 있는 팀은 엔지니어 2(speed=10 and efficiency=4)와 엔지니어 5(speed=5 and efficiency=7)를 선택하는 것 입니다.
performance는 (10 + 5) * min(4, 7) = 15 * 4 = 60 입니다.

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
Output: 68
위의 예제와 같은 조건이지만 k = 3입니다.
최대 performance를 낼 수 있는 팀은 엔지니어 1과, 엔지니어 2, 그리고 엔지니어 5를 선택하는 것 입니다.
performance = (2 + 10 + 5) * min(5, 4, 7) = 17 * 4 = 68.

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
Output: 72

제약조건

1 <= k <= n <= 105
speed.length == n
efficiency.length == n
1 <= speed[i] <= 10^5
1 <= efficiency[i] <= 10^8

풀이 : Greedy

문제를 쉽게 보고 풀다가 나중에 잘 못 이해한 부분이 있는 것을 확인했습니다 . 이런식의 문제는 처음 풀어보기도 했습니다..

쉽게 오해할 수 있는 부분을 짚고 풀이방식을 설명하며 진행하겠습니다.

최대 k명의 엔지니어를 선택

최대 k명이라는 뜻은 선택된 엔지니어의 수가 k 보다 작을수도 있는 것 입니다.

예를 들어, 엔지니어 1(speed = 10, efficiency = 10)과 엔지니어 2(speed = 1, efficiency = 1)가 있고 k = 2라고 가정합시다.

엔지니어 1 만 고른다면 performance는 100이고 (10 * 10) 엔지니어 2 도 같이 고른다면 11 (11 * 1)입니다.

그렇기에 k명을 넣어서 performance를 계산하는 DFS는 잘못된 접근 이었습니다.

자, 그럼 위의 내용을 고려하며 풀이를 진행하겠습니다.

1. efficiency 기준으로 정렬하기

performance는 선택된 엔지니어 중 최소 efficiency를 곱해줘야 합니다.즉, efficiency가 높을 수록 performance가 커질 확률이 커집니다. 그렇기에 높은 efficiency를 앞으로 올 수 있게 정렬을 합니다.

2. speed에 대해 min heap을 사용하기

priority queue를 사용하여 선택된 엔지니어의 speed를 저장합니다. min heap이기에 제일 위에는 제일 작은 speed가 들어있습니다.

speed는 크면 클 수록 좋기에 k가 넘어가 제거를 할 경우 제일 작은 speed를 빼야합니다.

efficiency로 정렬된 엔지니어를 돌아가며 최대 k명의 엔지니어들을 선택하고 speed를 더해줍니다. 그 후 현재까지 performance와 현재 efficiency에 더해준 speed를 곱한 값과 비교합니다. efficiency가 큰 값부터 작은 값 순으로 들어 있으니 현재 efficiency 값이 최소 efficiency 입니다.

만약 k명이 넘어갈 경우 더해준 speed에서 제일 작은 speed를 빼는데 해당 값은 min heap 제일 위에 저장이 되어 있습니다.

또한, k보다 적게 엔지니어를 선택할 수도 있는데, 이럴경우는 절대적으로 efficiency가 제일 큰 엔지니어들로 구성되지 않으면 성립하지 않습니다. 이 부분이 이해가 애매했었는데 엔지니어 1(speed = 10, efficiency = 10)과 엔지니어 2(speed = 200, efficiency = 1)가 있고 k = 2 일 때 각각 한 명을 고를 경우 performance는 100과 200 입니다.

하지만 둘 다 고를 경우, 1 * 210 = 210 으로 k 이하로 구성할 때 효율이 제일 좋은 엔지니어를 빼면 안된다는 것을 알 수 있습니다.

검증해서 적어보고 싶은데 기회가 생긴다면 진행해보겠습니다.

그리고 모든 경우의 수를 진행한다면 time out이 나게됩니다...

코드는 아래와 같습니다.

class Solution {
    public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
        int[][] engineers = new int[n][2];
        for (int i = 0; i < n; i++)
            engineers[i] = new int[] {efficiency[i], speed[i]};
        Arrays.sort(engineers, (a, b) -> Integer.compare(b[0], a[0]));

        long speedSum = 0;
        long answer = 0;
        PriorityQueue<Integer> speedMinHeap = new PriorityQueue<>();
        for (int[] engineer : engineers) {
            int currEfficiency = engineer[0];
            int currSpeed = engineer[1];

            if (speedMinHeap.size() >= k)
                speedSum -= speedMinHeap.poll();
            speedMinHeap.add(currSpeed);
            speedSum += currSpeed;
            
            answer = Math.max(answer, speedSum * currEfficiency);
        }

        return (int)(answer % 1000000007);
    }
}

저에게는 hard 다운 문제였습니다.

은근히 DFS나 DP는 조건만 잘걸면 쉽게 풀 수 있는 것 같은데 Greedy는 이해하기 어려울 때가 많은 것 같습니다.

의견 및 질문은 늘 환영합니다 :)

문제

문자열 s와 integer k가 주어졌습니다. s에서 첫 k개의 문자들 중 하나를 선택해 문자열의 끝으로 보낼 수 있습니다.

위의 방법을 몇 번이든 적용해서 만들 수 있는 문자열 중 사전순으로 제일 작은 문자열을 반환해주세요.

예시

Input: s = "cba", k = 1
Output: "acb"
1번째 이동, 'c'를 끝으로 보내 "bac"를 만든다. ("cba -> bac")
2번째 이동, 'b'를 끝으로 보내 "acb"를 만든다. ("bac -> acb")

Input: s = "baaca", k = 3
Output: "aaabc"
1번째 이동, 첫번째 문자인 'b'를 끝으로 보내 "aacab"를 만든다. ("baaca" -> "aacab")
2번째 이동, 세번째 문자인 'c'를 끝으로 보내 "aaabc"를 만든다. ("aacab" -> "aaabc")

제약조건

1 <= k <= s.length <= 1000
s는 영어 소문자로 이뤄져있습니다.

풀이 : 구현

문제를 이해하는데 헷갈려서 시간이 좀 걸렸습니다. 하지만 문제풀이 자체는 간단했습니다.

아마 이런식으로 풀게 하려던 것 같지는 않은데 풀이방식은 아래와 같습니다.

1. k > 2, 문자열 정렬 후 제일 작은 문자열을 반환하기

뒤로 보낼 수 있는 문자가 2개 이상이라면 시간은 걸려도 문자열로 모든 순열을 만들 수 있습니다.

즉, 문자열을 문자 배열로 만들어 정렬해서 반환하면 됩니다.

2. k == 1, 후보 순열의 대소비교 후 제일 작은 문자열을 반환하기

뒤로 보낼 수 있는 문자가 1개 라면 만들 수 있는 순열의 개수는 정해져 있습니다.

문자열의 길이가 n이라면 n번 만큼 첫 글자를 맨 뒤로 넣을 수 있으므로 n번의 대소비교만 진행하면 됩니다.

즉, 가능한 모든 순열을 비교해 최소의 문자열을 반환하면 됩니다.

코드는 아래와 같습니다.

class Solution {
    public String orderlyQueue(String s, int k) {
        if (k > 1) {
            char ch[] = s.toCharArray();
            Arrays.sort(ch);
            return new String(ch);
        }
        else {
            String minStr = new String(s);

            for (int i = 0; i < s.length(); i++) {
                s = s.substring(1) + s.substring(0, 1);
                
                if (minStr.compareTo(s) > 0) {
                    minStr = s;
                }
            }
            
            return minStr;
        }
    }
}

성능향상을 위해 문자열 연산이 많기에 불변객체인 String 대신 가변객체인 StringBuilder로 바꿨습니다.

코드는 아래와 같습니다.

class Solution {
    public String orderlyQueue(String s, int k) {
        if (k > 1) {
            char ch[] = s.toCharArray();
            Arrays.sort(ch);
            return new String(ch);
        }
        else {
            String minStr = new String(s);
            StringBuilder sb = new StringBuilder(s);

            for (int i = 0; i < s.length(); i++) {
                char firstChar = sb.charAt(0);
                sb.deleteCharAt(0);
                sb.append(firstChar);
                
                String rotatedStr = sb.toString();
                if (minStr.compareTo(rotatedStr) > 0) {
                    minStr = rotatedStr;
                }
            }
            
            return minStr;
        }
    }
}

hard라고 하기엔 묘한 문제였습니다.

자주 나올 것 같은 유형은 아니고 "이런 것도 있구나..." 하고 넘어가면 좋을 것 같습니다.

의견 및 질문은 늘 환영합니다 :)

문제

도시의 스카이라인은 멀리서 봤을 때 도시의 건물들로 인해 만들어진 실루엣의 외곽선을 뜻한다.

건물들의 위치와 높이가 주어졌을 때, 이 건물들로 만들어진 스카이라인을 집합해서 반환하면 된다.

건물의 기하학적 정보가 buildings 라는 배열로 주어진다, buildings[i] = [lefti, righti, heighti]

• lefti는 i번째 건물의 왼쪽 끝 좌표이다.
• righti는 i번째 건물의 오른쪽 끝 좌표이다.
• heighti는 i번째 건물의 높이이다.

모든 건물들이 완전히 평평한 표면에서 (높이 : 0) 세워진 완벽한 직사각형 이라고 가정해도 됩니다.

스카이라인은 "key points"로 이뤄진 list로 표현되어야 하고 x좌표로 정렬되어야 합고 다음과 같은 형태여야 합니다.

[[x1, y1], [x2, y2], ...]

각 key point는 스카이라인 왼쪽 부분이고, list의 마지막 point만 늘 y좌표가 0이며 skyline의 끝인 건물들의 오른쪽 끝 부분을 의미합니다.

왼쪽 끝과 오른쪽 끝 사이의 건물들 사이 땅만 있더라도 스카이라인의 외곽선에 포함되어야 합니다.

참고 : 스카이라인 출력에 같은 높이가 연속적으로 나오면 안됩니다. 예를 들어, [..., [2 3], [4 5], [7 5], [11 5], [12 7], ...] 이 되면 안됩니다. 중간에 높이가 5인 부분들이 하나로 합쳐져, [..., [2 3], [4 5], [12 7], ...] 로 반환되어야 합니다.

예시

Input: buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
Output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
A는 input인 건물들이다.
B는 건물들로 만들어진 스카이라인 이다. 빨간 점들이 output으로 출력되는 key point들 이다.

Input: buildings = [[0,2,3],[2,5,3]]
Output: [[0,3],[5,0]]

제약조건

1 <= buildings.length <= 104
0 <= lefti < righti <= 2^^31 - 1
1 <= heighti <= 2^^31 - 1
buildings는 lefti를 기준으로 오름차순으로 정렬되어 있습니다.

풀이 : 구현

간만에 풀어 본 hard 난이도 문제였습니다. 문제를 읽고 hard 난이도가 맞나 생각했지만 난이도 답게 그리 쉽지는 않았습니다.

초반에 떠오른 풀이는 아래와 같습니다.

스카이라인의 왼쪽 끝에서 오른쪽 끝까지의 높이를 계산하고 연속적인 값은 제외하기

input을 모두 돌려가며 left부터 right까지 height의 값을 넣으려고 했습니다.

만약 해당 건물에 값이 있다면 제일 높은 height 값을 유지하려고 했습니다.

하지만 제약조건을 보니 건물의 위치가 int의 범위라 비효율 적이라 생각했습니다. 기각!

아무리 생각해도 확고한 답이 나오지 않아 자료들을 참고했습니다...

결론은 input으로 들어온 각 건물들의 left, right 좌표에 대해 height을 확인하는 방법입니다.

스카이라인의 외곽선은 건물들의 왼쪽 끝과 오른쪽 끝으로만 구성되어 있습니다.

1. 각 건물의 좌표를 위치와 높이 기준으로 정렬하기

우선적으로 각 건물의 양 끝점을 위치와 높이로 저장했습니다.

정렬 기준은 위치가 작을수록 (왼쪽 일수록) 앞으로 정렬하되, 같은 위치라면 더 높은 높이가 앞으로 정렬되었습니다.

다만 건물의 오른쪽 점은 높이를 음수로 저장하여 정렬하게 하여 같은 위치에 여러 건물의 양 끝점이 있다면 아래와 같이 정렬하였습니다.

왼쪽 + 높음 > 왼쪽 + 낮음 > 오른쪽 + 낮음 > 오른쪽 + 높음

음수로 저장한 이유는 아래에서 추가적으로 설명하겠습니다.

2. 각 건물의 좌표에서의 최대 높이 구하기

PriorityQueue로 해당 위치에서 제일 높은 높이를 저장할 수 있게 구현했습니다.

1번에서 정렬된 위치의 높이를 확인했을 때 양수면 해당 높이를 PriorityQueue에 넣고 음수면 해당 높이를 PriorityQueue에서 뺐습니다.그렇게 되면 왼쪽에서 부터 모든 건물들의 높이를 보되 제일 높은 위치를 PriorityQueue에서 확인할 수 있고 건물의 오른쪽 위치를 발견하면 해당 높이를 PriorityQueue에서 제거하여 스카이라인 외곽선을 확인하게 했습니다.

직전 스카이라인의 높이와 현재 높이가 다르다면 해당 위치와 높이를 저장했습니다. 그 부분이 스카이라인에서 수직으로 변하는 부분이기 때문입니다.

코드는 아래와 같습니다.

class Solution {
    class Point implements Comparator<Point> {
        int pos;
        int height;

        public Point() {

        }

        public Point(int pos, int height) {
            this.pos = pos;
            this.height = height;
        }

        @Override
        public int compare(Point p1, Point p2) {
            if (p1.pos == p2.pos) {
                return Integer.compare(p2.height, p1.height);
            }
            return Integer.compare(p1.pos, p2.pos);
        }
    }

    public List<List<Integer>> getSkyline(int[][] buildings) {
        List<Point> points = new ArrayList<>();
        for (int[] building : buildings) {
            points.add(new Point(building[0], building[2]));
            points.add(new Point(building[1], -building[2]));
        }
        Collections.sort(points, new Point());

        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        pq.offer(0);
        int prevMax = 0;

        List<List<Integer>> result = new ArrayList<>();
        for (Point point : points) {
            if (point.height > 0) {
                pq.offer(point.height);
            }
            else {
                pq.remove(-point.height);
            }

            int currMax = pq.peek();
            if (prevMax != currMax) {
                result.add(new ArrayList<>(List.of(point.pos, currMax)));
                prevMax = currMax;
            }
        }

        return result;
    }
}

성능향상을 위해 PriorityQueue를 TreeMap으로 바꿨습니다. PriorityQueue에서 원소를 제거하면 O(N)이지만 TreeMap에서 원소를 제거하면 O(NlogN)이기 때문입니다.

TreeMap은 키의 중복이 허용되지 않기에 count를 값으로 주어 현재 해당 위치에 같은 높이의 점이 몇개 있는지를 세주었습니다.

코드는 아래와 같습니다.

class Solution {
    class Point implements Comparator<Point> {
        int pos;
        int height;

        public Point() {

        }

        public Point(int pos, int height) {
            this.pos = pos;
            this.height = height;
        }

        @Override
        public int compare(Point p1, Point p2) {
            if (p1.pos == p2.pos) {
                return Integer.compare(p2.height, p1.height);
            }
            return Integer.compare(p1.pos, p2.pos);
        }
    }

    public List<List<Integer>> getSkyline(int[][] buildings) {
        List<Point> points = new ArrayList<>();
        for (int[] building : buildings) {
            points.add(new Point(building[0], building[2]));
            points.add(new Point(building[1], -building[2]));
        }
        Collections.sort(points, new Point());

        TreeMap<Integer, Integer> heightMap = new TreeMap<>(Collections.reverseOrder());
        heightMap.put(0, 1);
        int prevMax = 0;

        List<List<Integer>> result = new ArrayList<>();
        for (Point point : points) {
            if (point.height > 0) {
                heightMap.put(point.height, heightMap.getOrDefault(point.height, 0) + 1);
            }
            else {
                int heightCnt = heightMap.get(-point.height);
                if (heightCnt == 1) {
                    heightMap.remove(-point.height);
                }
                else {
                    heightMap.put(-point.height, heightCnt - 1);
                }
            }

            int currMax = heightMap.firstKey();

            if (prevMax != currMax) {
                result.add(new ArrayList<>(List.of(point.pos, currMax)));
                prevMax = currMax;
            }
        }

        return result;
    }
}

처음에는 건물의 시작과 끝을 boolean으로 주려고 했지만 오히려 가독성이 떨어지고 compare 메소드가 깔끔해지지 않아 음수를 활용했습니다. 생각보다 고민이 필요한 문제였습니다.

의견 및 질문은 늘 환영합니다 :)