퍼즐 게임 챌린지 [프로그래머스]

Level 2

[PCCP 기출문제] 2번 / 퍼즐 게임 챌린지 JAVA 코드

문제 이해

• n개의 퍼즐을 제한 시간 limit 내에 풀어야 함
• 각 퍼즐의 난이도는 diffs[i]
• 내 숙련도 level이 diffs[i]보다 크거나 같으면 times[i]만에 바로 품
  • level < diffs[i]면 (diffs[i] - level + 1) * times[i]으로 현재 퍼즐을 풀고, times[i-1]로 전 퍼즐을 다시 풀고 와야 한다
    • 이 때 전 퍼즐은 한 번 시도만에 끝난다
• 난이도, 소요 시간, 숙련도 모두 양의 정수
• 제한 시간 내에 퍼즐을 모두 해결하기 위한 숙련도의 최솟값을 정수로 리턴하도록 함수 작성하라

해결 방안

이분탐색으로 최적 답안을 찾았다.

1. 숙련도의 범위가 양의 정수고, 최댓값은 100,000로 명시되어 있으니, start = 1, end = 100000
2. 중간값에 대해 check 함수를 수행한다
3. check 함수는 중간값을 숙련도로 가정하여 퍼즐을 풀어서 시간 제한 내에 가능한지 boolean 값으로 리턴한다
4. 가능하면 숙련도의 최솟값을 구하기 위해 end = mid - 1로 다시 이분탐색을 수행한다
5. 불가능하면 가능한 숙련도를 찾는 게 우선이기 때문에 start = mid + 1로 더 높은 숙련도로 탐색한다

public int solution(int[] diffs, int[] times, long limit) {
    int answer = 0;

    int start = 1, end = 100000;
    while (start <= end) {
        int mid = start + (end - start)/2;
        if (check(mid, diffs, times, limit)) {
            answer = mid;
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }

    return answer;
}

private boolean check(int mid, int[] diffs, int[] times, long limit) {
    long timeTaken = times[0];
    for (int i = 1; i < diffs.length; i++) {
        if (diffs[i] <= mid) {
            timeTaken += times[i];
        } else {
            timeTaken += (diffs[i] - mid) * (times[i] + times[i-1]) + times[i];             
        }
    }
    return limit >= timeTaken;
}

---

이모티콘 할인행사 [프로그래머스]

lvl2

이모티콘 할인행사 JAVA 코드

문제 이해

• 목표
  • 1. 이모티콘 플러스 서비스 가입자를 최대한 늘린다
  • 2. 이모티콘 판매액을 최대한 늘린다
  • 첫번째 목표가 우선이고 두번째 목표는 그 다음
• n명의 카카오톡 사용자에게 이모티콘 m개를 할인하여 판매한다
  • 이모티콘마다 할인율은 상이할 수 있으며, 할인율은 10%, 20%, 30%, 40% 중 하나
• 각 사용자는 다음 기준을 따른다
  • 자신의 기준에 따라 일정 비율 이상 할인하는 이모티콘은 모두 구매한다
  • 각 사용자는 자신의 기준에 따라 이모티콘 구매 비용의 합이 일정 가격 이상이 되면 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입한다
• 1<= users의 길이 = n <= 100
  • users[i]는 [비율, 가격]
• 1 <= emoticons의 길이 = m <= 7
  • emoticons의 원소는 100의 배수

해결 방안

1. 할인율 배열을 정의한다

private static final int[] discounts = {10, 20, 30, 40};

2. 조합으로 이모티콘에 할인율을 배정한다

private void genComb(int depth, int[] res, int[][] users, int[] emoticons) {
    if (depth == emoticons.length) {
        ...
        return;
    }

    for (int i = 0; i < discounts.length; i++) {
        res[depth] = discounts[i];
        genComb(depth + 1, res, users, emoticons);
    }
}

3. 각 조합이 완성될 때마다 최대 값을 업데이트한다

각 사용자에 대해 이모티콘의 할인율을 배정한 가격의 총합을 계산하고, 이 결과가 사용자의 기준되는 금액보다 크면 구독자로 센다

if (depth == emoticons.length) {
    int subs = 0, spentTotal = 0;
    for (int[] user : users) {
        int spent = 0;
        for (int i = 0; i < emoticons.length; i++) {
            if (res[i] >= user[0]) {
                spent += emoticons[i] * (100 - res[i]) / 100;
            }
        }
        if (spent >= user[1]) {
            subs ++;
        } else {
            spentTotal += spent;
        }
    }
    if (subs > subscribers) {
        subscribers = subs;
        profit = spentTotal;
    } else if (subs == subscribers) {
        profit = Math.max(profit, spentTotal);
    }
    return;
}

---

활주로 건설 [SWEA]

unrated

활주로 건설 JAVA 코드

문제 이해

• N * N 크기의 절벽지대에 활주로를 건설한다
  • 셀의 값은 그 지형의 높이를 의미한다
• 활주로는 높이가 동일한 구간에 건설이 가능하다
• 경사로는 길이가 X, 높이가 1이다
  • 높이 차이가 1이고, 낮은 지형의 높이가 동일하게 경사로의 길이만큼 연속되는 곳에 설치할 수 있다
• 동일한 셀에 두 개 이상의 경로를 겹쳐서 사용할 수 없다
• 활주로를 건설할 수 있는 경우의 수를 계산하라

해결 방안

각 row와 column에 대해 활주로 건설이 가능한지 확인한다

1. 현재와 다음 높이를 비교한다

2. 높이가 같으면 경사로 건설 없이도 활주로 건설이 가능하기 때문에 다음으로 넘어간다

if(line[i] == line[i + 1]) continue;

3. 현재 높이가 다음 높이보다 1 작으면 현재 높이 포함 X 길이만큼 전까지 공간에 경사로가 설치 가능한지 확인한다

3-1. boolean[] used에 경사로 건설에 사용된 셀을 표시해서 하나의 셀에 두 개 이상의 경사로가 겹치지 않도록 방지한다

3-2. 인덱스가 0보다 작으면 범위 밖으로 실패한다
3-3. 높이가 다르면 경사로 건설이 불가하다

else if(line[i] + 1 == line[i + 1]){
    for(int j = 0; j < X; j++){
        int idx = i - j;
        if(idx < 0 || line[idx] != line[i] || used[idx]){
            return false;
        }
        used[idx] = true;
    }
}

4. 현재 높이가 다음 높이보다 1 크면 현재 높이 포함 X 길이만큼 후까지 공간에 경사로가 설치 가능한지 확인한다

4-1. 3-1와 동일
4-2. 인덱스가 N보다 크거가 같으면 범위 밖으로 실패한다
4-3. 3-3와 동일
4-4. 탐색 중인 i 인덱스를 X-1 만큼 이동시켜서 경사로 이후부터 탐색을 진행하도록 한다

else if(line[i] - 1 == line[i + 1]){
    for(int j = 1; j <= X; j++){
        int idx = i + j;
        if(idx >= N || line[idx] != line[i + 1] || used[idx]){
            return false;
        }
        used[idx] = true;
    }
    i += X - 1; 
}

5. 2, 3, 4 단계에 해당하지 않으면 높이 차가 2이상이므로 높이가 1로 제한된 경사로도 보완하지 못하는 차이다.

---

충돌위험 찾기 [프로그래머스]

lvl 2

충돌위험 찾기 JAVA 코드

문제 이해

• n개의 포인트가 존재한다
  • 2 <= n <= 100
• x개의 로봇이 존재한다
  • i번째 로봇은 routes[i]의 경로를 갖는다
  • 경로는 포인트의 인덱스로 구성된다 (1~n)
• 모든 로봇들이 자신의 경로를 따라서 이동할 때 2 개 이상의 로봇이 같은 좌표에 존재하면 충돌 위험이다
  • 로봇은 자신의 경로를 따라 한 포인트에서 그 다음 포인트로 이동하는데, 이 때 row먼저 움직인 다음 col을 움직인다
• 총 충돌 위험 수를 구하시오

해결 방안

1. 각 로봇의 상세 경로를 구한다

row 먼저 움직이므로 y값부터 변경하고, 그 다음 x값을 변경한다

longestPath 변수는 static하게 가장 긴 경로의 길이를 저장하여 모든 경로를 동시에 탐색할 때 사용한다

private List<int[]> findRoute(int[] route, int[][] points) {
    List<int[]> path = new ArrayList<>();
    int[] way = new int[route.length];
    for (int i =0 ; i < route.length; i++) {
        way[i] = route[i] -1;
    }

    int y = points[way[0]][0], x = points[way[0]][1];
    path.add(new int[] {y, x});
    for (int i = 1; i < route.length; i++) {
        int nextY = points[way[i]][0], nextX = points[way[i]][1];
        int[] move = new int[2];
        while (y != nextY) {
            if (y < nextY) {
                y ++;
                path.add(new int[] {y, x});
            } else {
                y --;
                path.add(new int[] {y, x});
            }
        }
        while (x != nextX) {
            if (x < nextX) {
                x ++;
                path.add(new int[] {y, x});
            } else {
                x --;
                path.add(new int[] {y, x});
            }
        }
    }
    longestPath = Math.max(longestPath, path.size());
    return path;
}

2. 경로를 모두 수합한 후, 시간대 별로 같은 위치에 존재하는 로봇이 있는지 확인한다

public int solution(int[][] points, int[][] routes) {
    int answer = 0;


    List<List<int[]>> allRoutes = new ArrayList<>();
    
    // 각 로봇의 경로에 대해 상세 경로를 수합한다
    for (int[] route : routes) {
        allRoutes.add(findRoute(route, points));
    }
    
    // 0초부터 가장 긴 상세 경로가 걸린 시간까지 탐색하는데,

    for (int i = 0 ; i < longestPath; i++) {

        // 같은 시간대에 같은 위치에 존재하는 로봇의 개수를 저장한다
		Map<Point, Integer> map = new HashMap<>();
        for (int j = 0; j < allRoutes.size();j++) {
            if (i >= allRoutes.get(j).size()) continue;
            int[] loc = allRoutes.get(j).get(i);
            Point p = new Point(loc[0], loc[1]);
            if (!map.containsKey(p)) map.put(p, 1);
            else map.put(p, map.get(p) + 1);
        }

        for (Map.Entry<Point, Integer> e : map.entrySet()) {
            if (e.getValue()>= 2) answer++;
        }
    }

    return answer;
}

Point 클래스는 다음과 같이 정의한다

static class Point {
    int r, c;
    Point(int r, int c) {
        this.r =r;
        this.c=c;
    }

    @Override
    public boolean equals(Object o) {
        if (o == this) return true;
        Point p = (Point) o;
        if (p.r == this.r && p.c == this.c) return true;
        return false;
    }

    @Override
    public int hashCode() {
       return Objects.hash(r, c);
    }
}