코딩테스트 연습 - 가장 큰 정사각형 찾기 | 프로그래머스 스쿨

1과 0으로 이루어진 2차원 배열 board에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 반환

먼저 떠오르는 방식은 완전 탐색이다. 모든 가능한 정사각형의 크기를 다 확인하는 것이다. 하지만 이는 시간복잡도 O(n^2m^2)으로 비효율적이다.

따라서 dp를 생각해 보자.

dp[i][j]에서의 최대 정사각형의 크기는 어떻게 판단할까?

dp[i][j]에서의 최대 정사각형은 min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1이 된다.

import java.util.*;

class Solution
{
    public int solution(int [][]board)
    {
        for (int i = 1; i < board.length; i++) {
            for (int j = 1; j < board[i].length; j++) {
                if (board[i][j] == 1) {
                    board[i][j] += Math.min(board[i - 1][j], Math.min(board[i][j - 1], board[i - 1][j - 1]));
                }
            }
        }
        
        int x = Arrays.stream(board).flatMapToInt(Arrays::stream).max().getAsInt();

        return x * x;
    }
}

코딩테스트 연습 - 도둑질 | 프로그래머스 스쿨

인접한 집을 털면 경보가 울린다.

그리고 집이 원형으로 배치되어 있다.

돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최대 값은?

이 두 가지 특징이 있는 상황이다.

핵심은 원형 구조이다. 따라서 1번 집이 제일 중요해진다. 1번 집을 털게 되면 마지막 집을 털 수 없게 된다. 1번 집을 털지 않는다면 마지막 집을 털 수 있게 된다.

dp [i]를 i번째 위치에서의 최댓값이라 생각해 보자. 이 값은 i-2를 털고 i를 터는 경우와 i-1을 털고 i를 안터는 경우 두 가지 중 큰 값이 될 것이다.

그런데 앞서 말했듯이 1번집부터 털지 안 털지 별개의 배열로 관리해야 한다.

import java.util.*;

class Solution {
    public int solution(int[] money) {
        int n = money.length;
        int[] dp1 = new int[n + 1];
        int[] dp2 = new int[n + 1];
        dp1[0] = money[0];
        dp1[1] = money[0];
        dp2[0] = 0;
        dp2[1] = money[1];
        
        for (int i = 2; i < n - 1; i++) {
            // 첫 집을 터는 경우
            dp1[i] = Math.max(dp1[i - 2] + money[i], dp1[i - 1]);
        }
        
        for (int i = 2; i < n; i++) {
            dp2[i] = Math.max(dp2[i - 2] + money[i], dp2[i - 1]);
        }
        
        return Math.max(dp1[n - 2], dp2[n - 1]);
    }
}

2295번: 세 수의 합

N(5 ≤ N ≤ 1,000) 개의 자연수로 이루어진 집합 U.

U에서 적당히 3개의 수를 뽑았을 때 그 세 수의 합 d도 U안에 포함되는 경우가 있을 수 있다.

이때 가장 큰 d를 찾아라

집합의 크기는 최대 1000이다. 집합이니 중복은 존재하지 않는다.

1000개에서 3개를 뽑고 전부 확인하면 시간초과가 발생할 것이다.

또한 집합 U의 원소는 2억보다 작거나 같은 자연수이다. 세 수를 더한 경우에도 정수 범위 내로 처리 가능하다.

두 수의 합으로 만들 수 있는 숫자들을 미리 기록해 놓고 빠르게 찾을 수 있으면 해결할 수 있다.

1. 두 수의 조합으로 만들 수 있는 합을 Set으로 관리
2. 입력받은 집합을 오름차순으로 정렬하고 뒤에서부터 확인
3. 현재 정답 후보와 후보 앞에 있는 숫자들을 빼가며 해당 값이 두 수의 합 Set에 존재하는지 확인

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {

    static FastReader scan = new FastReader();
    static int N;
    static List<Integer> nums;

    static void input() {
        N = scan.nextInt();
        nums = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            nums.add(scan.nextInt());
        }

        Collections.sort(nums);
    }

    static void solve() {
        Set<Integer> twoSum = new HashSet<>();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                twoSum.add(nums.get(i) + nums.get(j));
            }
        }

        for (int i = nums.size() - 1; i > 0; i--) {
            for (int j = i - 1; j >= 0; j--) {
                int cand = nums.get(i) - nums.get(j);
                if (twoSum.contains(cand)) {
                    System.out.println(nums.get(i));
                    return;
                }
            }
        }

    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

코딩테스트 연습 - 롤케이크 자르기 | 프로그래머스 스쿨 (programmers.co.kr)

조각마다 동일한 가짓수의 토핑이 올라가 있으면 공평하게 나누어진 것이다.

→ 토핑의 개수보다는 가짓수가 중요하다.

롤 케이크를 공평하게 자르는 방법의 수를 구하시오.

전체 토핑을 관리하며 포인트를 이동시켜 가며 확인을 한다.

1. 토핑 종류 : 개수 Map으로 기록
2. 포인터를 0부터 오른쪽으로 이동시켜한다.
3. 해당 포인터의 토핑을 Map 에서 1개 뺀다. 만약 개수가 0이 되면 제거한다.
4. 현재 내 토핑은 Set을 통해 관리한다.
5. 최종적으로 내 토핑 set과 전체 토핑 map의 크기가 같으면 공평한 것이다.

import java.util.*;

class Solution {
    public int solution(int[] topping) {
        Map<Integer, Integer> toppings = new HashMap<>();
        Set<Integer> myToppings = new HashSet<>();
        int answer = 0;
        
        for (int t : topping) {
            toppings.put(t, toppings.getOrDefault(t, 0) + 1);
        }
        
        for (int i = 0; i < topping.length; i++) {
            int t = topping[i];
            myToppings.add(t);
            toppings.put(t, toppings.get(t) - 1);
            if (toppings.get(t) == 0) {
                toppings.remove(t);
            }
            
            if (myToppings.size() == toppings.size()) {
                answer++;
            }
        }
        return answer;
    }
}

코딩테스트 연습 - 전화번호 목록 | 프로그래머스 스쿨 (programmers.co.kr)

한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 한다.

예를 들어 ["119", "97674223", "1195524421"] 이 주어졌다면 “119”는 “1195524421”의 접두어가 됩니다.

어떤 번호가 다른 번호의 접두어인 경우가 있으면 false 그렇지 않다면 true

우선 접두어라는 것이 앞에 있다는 소리니 길이가 짧을 수밖에 없다. 주어진 배열을 길이로 정렬부터 하는 게 맞다는 생각이 든다.

트라이를 사용할까?

트라이를 구성하고 길이가 짧은 단어 부터 삽입해 간다.

삽입도중에 단어가 완성됐다는 플래그가 나오면 false를 반환하고 종료한다.

import java.util.*;

class Solution {
    static class TrieNode {
        Map<Character, TrieNode> children = new HashMap<>();
        boolean isEndOf = false;
        
        public boolean isEndOf() {
            return isEndOf;
        }
        
        public void setEndOf(boolean end) {
            isEndOf = end;
        }
    }
    
    static class Trie {
        TrieNode root;
        
        public Trie() {
            root = new TrieNode();
        }
        
        public boolean insert(String word) {
            TrieNode current = root;
            for (char ch : word.toCharArray()) {
                current.children.putIfAbsent(ch, new TrieNode());
                current = current.children.get(ch);
                if (current.isEndOf()) {
                    // 삽입중인데 이미 단어가 완성된게 있다 -> 접두어 존재
                    return false;
                }
            }
            current.setEndOf(true);
            return true;
        }
    }
    
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book, (a, b) -> Integer.compare(a.length(), b.length()));
        Trie trie = new Trie();
        for (String number : phone_book) {
            if (!trie.insert(number)) {
                return false;
            }
        }
        
        return true;
    }
}

그런데 이 문제는 잘 생각해 보면 그럴 필요가 없다. 그냥 정렬해서 이전 것과 비교하면 된다. 문자열의 정렬은 사전순으로 이루어진다. 예를 들어 ["119", "97674223", "1195524421"] 이것의 정렬의 결과는 ["119", "1195524421", "97674223"] 이 된다. 따라서 접두어는 반드시 한 칸 앞에 존재한다.

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book);
        for (int i = 1; i < phone_book.length; i++) {
            if (phone_book[i].startsWith(phone_book[i - 1])) {
                return false;
            }
        }
        return true;
    }
}

코딩테스트 연습 - 지형 이동 | 프로그래머스 스쿨 (programmers.co.kr)

각 칸에는 높이가 적혀있고 이동하려면 칸 사이 높이차가 height 이하여야 한다.

height보다 많이 나는 경우에는 사다리를 설치해서 이동할 수 있다.

사다리 설치 비용은 높이차만큼 들어간다.

최대한 적은 비용이 들도록 사다리를 설치해서 모든 칸으로 이동 가능하게 하라.

시작점 위치는 중요하지 않다. 어차피 모든 점을 도달하려면 어느 점에서 시작하던 상관없다.

현재 위치에서 이동 위치는 이동 가능한 지점과 이동 불가능한 지점으로 나누어진다.

이동 가능한 위치는 그냥 이동하면 된다. 이제 이동 불가능한 지점을 어떻게 다룰지 생각해야 한다.

현재 탐색 가능 범위를 탐색하면서 사다리를 설치해야 하는 위치와 비용을 저장한다.

그중 가장 적은 비용을 꺼내 사다리를 설치하고 그 지점부터 탐색을 다시 시작한다.

지속적으로 사다리 설치 후보를 추가해 가면서 모든 지점이 탐색될 때까지 탐색한다.

1. (0,0)부터 시작해서 탐색을 진행한다. 이 과정은 BFS를 통해 탐색을 한다.
2. 사다리를 설치해야 하는 지점이 있다면 PQ에 좌표와 비용을 추가한다.
3. 탐색 가능한 범위를 탐색한 후 모든 지점이 탐색되지 않았다면 사다리를 하나 꺼내서 설치한다.
4. 만약 사다리를 설치한 위치가 이미 방문된 곳이라면 다음 사다리를 꺼낸다.
5. 이 과정은 모든 지점 탐색이 완료될 때까지 반복한다.

import java.util.*;

class Solution {
    static class Point {
        int r;
        int c;
        int cost;
        
        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
        
        public Point(int r, int c, int cost) {
            this.r = r;
            this.c = c;
            this.cost = cost;
        }
    }
    
    static int[][] DIRECTION = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    public int solution(int[][] land, int height) {
        int N = land.length;
        boolean[][] visited = new boolean[N][N];
        PriorityQueue<Point> pq = new PriorityQueue<>(Comparator.comparingInt(p -> p.cost));
        pq.add(new Point(0, 0));
        int visitCount = N * N;
        int totalCost = 0;
        
        while (true) {
            // 아직 모든 지점을 방문하지 않음.
            Point start = null;
            while (!pq.isEmpty()) {
                start = pq.poll();
                if (!visited[start.r][start.c]) break; 
            }
            
            Queue<Point> q = new LinkedList<>();
            q.add(start);
            visited[start.r][start.c] = true;
            totalCost += start.cost;
            visitCount--;
            
            while (!q.isEmpty()) {
                Point curr = q.poll();
                for (int d = 0; d < 4; d++) {
                    int nr = curr.r + DIRECTION[d][0];
                    int nc = curr.c + DIRECTION[d][1];
                    
                    if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
                    if (visited[nr][nc]) continue;
                    
                    int gap = Math.abs(land[nr][nc] - land[curr.r][curr.c]);
                    if (gap <= height) {
                        q.add(new Point(nr, nc));
                        visited[nr][nc] = true;
                        visitCount--;
                    } else {
                        pq.add(new Point(nr, nc, gap));
                    }
                }
            }
            
            if (visitCount == 0) {
                return totalCost;
            }
        }
    }
    
}

코딩테스트 연습 - 튜플 | 프로그래머스 스쿨 (programmers.co.kr)

문자열 s가 표현하는 튜플을 배열에 담아 반환하시오.

예를 들어 s = “{{2}, {2,1}, {2,1,3}, {2,1,3,4}}” 이면 튜플은 (2, 1, 3,4)가 된다.

다음으로 s = "{{1,2,3}, {2,1}, {1,2,4,3}, {2}}” 역시도 튜플은 (2, 1, 3, 4)이다.

문자열을 잘 분리하는 것이 핵심이다.

"{{1,2,3}, {2,1}, {1,2,4,3}, {2}}” 를 기준으로 생각해 보자. 각 집합을 구분하는 구분자는 “,”이다. 그렇지만 “,”를 기준으로 나누면 집합 내의 ‘,’의 존재 때문에 안된다.

따라서 ”},”를 기준으로 나누면 어떨까? 우선 시작과 끝의 “{”, “}” 는 없애고 본다.

"{1,2,3}, {2,1}, {1,2,4,3}, {2”

“{1, 2, 3” , “{2, 1”, {1, 2, 4, 3”, “{2”이가 된다.

이제 이거를 숫자의 개수를 기준으로 정렬을 해야 한다.

즉 [”2”, “2, 1”, “1, 2, 3”, “1, 2, 4, 3”] 으로 만들어야 튜플을 구할 수 있다.

1. substring을 통해 문자열을 잘라낸다.
2. 그 후 구분자룰 “},”로 삼아 문자열을 배열로 분리한다.
3. 길이 순으로 오름차순 정렬을 한다.
4. Set을 통해 중복된 숫자 처리를 한다. LinkedHashSet을 사용해 삽입 순서를 유지해 해당 set을 통해 정답을 구성하겠다.

import java.util.*;

class Solution {
    public int[] solution(String s) {
        s = s.substring(1, s.length() - 2);
        String[] splited = s.split("},");
        Arrays.sort(splited, (a, b) -> Integer.compare(a.length(), b.length()));
        for (int i = 0; i < splited.length; i++) {
            splited[i] = splited[i].substring(1);           
        }
        
        Set<Integer> set = new LinkedHashSet<>();
        for (String words : splited) {
            for (String num : words.split(",")) {
                int v = Integer.parseInt(num);
                if (set.contains(v)) continue;
                set.add(v);
                break;
            }
        }
        
        return set.stream().mapToInt(Integer::intValue).toArray();
    }
}

코딩테스트 연습 - 외벽 점검 | 프로그래머스 스쿨 (programmers.co.kr)

외벽의 총둘레는 n미터. 원형 구조. 취약점 존재

취약점을 점검하기 위해 보내야 하는 친구 수의 최솟값은?

어떤 친구를 어느 지점에 배치해야 할지를 결정해야 하는 문제이다.

원형 외벽을 계산하기 위해 선형으로 변경해야 한다. 배열을 두 배로 늘려 처리할 수 있다.

방향은 따로 고려하지 않아도 된다. 예를 들어 4 → 9 반시계나 9 → 4 시계나 똑같은 범위다.

가장 먼저 떠오르는 것은 dist의 최대가 8이기 때문에 8! 의 모든 경우의 수로 앞에서부터 배치해 가며 들어가는 사람들 확인해 보는 것이다.

1. dist를 통해 순열을 구성한다.
2. 취약점의 시작위치를 변경해 가며 순열을 통해 확인해 본다.
   1. 현재 취약점은 확장돼 있는 상태
   2. 커버한 개수를 통해 모든 지점을 검사했는지 확인해야 한다.
      1. 즉 해당 순열이, 해당 시작점에서, 범위를 커버가능한가 → 3중 루프가 된다.
3. 커버가 가능하다면 답을 갱신한다.

import java.util.*;

class Solution {
    
    int answer = Integer.MAX_VALUE;
    
    public int solution(int n, int[] weak, int[] dist) {
        List<int[]> result = new ArrayList<>();
        permutate(0, new int[dist.length], dist, new boolean[dist.length], result);
        check(n, result, weak);
        
        return answer;
    }
    
    private void check(int n, List<int[]> result, int[] weak) {
        int l = weak.length;
        int[] extendedWeak = extendWeak(n, weak);
        
        for (int[] dist : result) {
            for (int start = 0; start < l; start++) {
                int cnt = 1; // start를 시작점으로 해서 투입한 사람 수
                int end = extendedWeak[start] + dist[cnt - 1];
                for (int i = start; i < start + l; i++) {
                    if (extendedWeak[i] > end) {
                        cnt++; // 추가 투입
                        if (cnt > dist.length) break;
                        end = extendedWeak[i] + dist[cnt - 1];
                    }
                }
                answer = Math.min(answer, cnt);
            }
        }
        
        if (answer > result.get(0).length) answer = -1;
    }
    
    private int[] extendWeak(int n, int[] weak) {
        int l = weak.length;
        int[] extendedWeak = new int[2 * l];
        for (int i = 0; i < l; i++) {
            extendedWeak[i] = weak[i];
            extendedWeak[i + l] = weak[i] + n;
        }
        return extendedWeak;
    }
    
    private void permutate(int depth, int[] selected, int[] dist, boolean[] visited, List<int[]> result) {
        if (depth == dist.length) {
            result.add(selected.clone());
            return;
        }
        
        for (int i = 0; i < dist.length; i++) {
            if (visited[i]) continue;
            selected[depth] = dist[i];
            visited[i] = true;
            permutate(depth + 1, selected, dist, visited, result);
            selected[depth] = 0;
            visited[i] = false;
        }
    }
}

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

라이언(우승자), 어피치(도전자)

어피치가 먼저 n발을 쏜 후 라이언이 화살 n발을 쏜다.

k(1 ~ 10)점을 어피치가 a발맞추고 라이언이 b발맞춘 경우 더 많은 화살을 k점에 맞힌 선수가 k점을 가져간다. 단, a = b 일 경우는 어피치가 k점을 가져한다.

k점을 많이 맞춘다고 k점 보다 많은 점수를 가져가는게 아니라 k점만 가져한다.

모든 결과가 나왔을 때 최종 점수가 더 높은 선수를 우승자로 결정한다. 단, 최종 점수가 같을 경우 어피치가 우승한다.

현재 상황은 어피치는 이미 n발을 다 쐈고 라이언이 n발을 쏠 차례이다.

라이언이 가장 큰 점수 차이로 이기기 위해서 n 발의 화살을 어떤 과녁 점수에 맞혀야 하는가. 만약 라이언이 우승할 수 없는 경우 [-1]을 return

라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return

점수가 10~0점 까지 있다. 라이언이 해당 점수를 가져갈지 말지를 결정하는 문제이다.

해당 점수를 가져가려면 어피치가 맞춘 개수 + 1 개를 맞춰야 한다.

그렇다면 완전탐색을 통해서 모든 경우의 수를 확인하면 된다. 여기서 변하는 값은 표적의 인덱스와 남은 화살의 개수가 될 것이다.

화살이 0개 미만이 되면 더 이상 선택을 할 수 없어진다.

그런데 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우의 조건을 해결해야 한다.

만약 점수 차이가 갱신이 되면 해당 배열을 저장한다. 점수 차이가 동일하다면 두 배열을 비교해 낮은 점수가 많은 배열을 선택해서 저장한다.

import java.util.*;

class Solution {
    
    static int maxScoreGap = Integer.MIN_VALUE;
    static int[] answer = {};
    
    public int[] solution(int n, int[] info) {
        int[] ryan = new int[11];
        dfs(0, n, ryan, info);
        
        return maxScoreGap <= 0 ? new int[]{-1} : answer;
    }
    
    private void dfs(int idx, int n, int[] ryan, int[] apeach) {
        if (n == 0 || idx == 11) {
            // 모든 화살을 쐈거나, 마지막 과녁까지 끝났다.
            int gap = calculateGap(ryan, apeach);
            int[] copiedRyan = ryan.clone();
            copiedRyan[10] += n; // 마지막 과녁까지 했는데 화살이 남은 경우 0점에 몰아준다.
            if (maxScoreGap < gap) {
                answer = copiedRyan;
                maxScoreGap = gap;
            } else if (maxScoreGap == gap) {
                compareResult(copiedRyan);
            }
            return;
        }
        
        // 획득 가능하며 해당 점수 획득
        if (n >= apeach[idx] + 1) {
            ryan[idx] = apeach[idx] + 1;
            dfs(idx + 1, n - ryan[idx], ryan, apeach);
            ryan[idx] = 0; 
        }
        // 해당 점수 패스
        dfs(idx + 1, n, ryan, apeach); 
    }
    
    private int calculateGap(int[] ryan, int[] apeach) {
        int ryanScore = 0;
        int apeachScore = 0;
        for (int i = 0; i < 11; i++) {
            if (ryan[i] == 0 && apeach[i] == 0) {
                continue;
            }
            
            if (ryan[i] > apeach[i]) {
                ryanScore += 10 - i;
            } else {
                apeachScore += 10 - i;
            }
        }
        return ryanScore - apeachScore;
    }
    
    private void compareResult(int[] ryan) {
        // answer와 ryan을 비교해서 낮은 점수가 더 많은 경우
        for (int i = 10; i >= 0; i--) {
            if (ryan[i] > answer[i]) {
                answer = ryan.clone();
                break;
            } else if (ryan[i] < answer[i]) {
                break;
            }
        }
    }
    
}

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

n개의 퀸이 서로를 공격할 수 없도록 배치하는 방법.

퀸을 순열로 배치하면 된다. 그런데 퀸을 배치할 때 고려해야 하는 요소는 무엇일까?

그건 바로 다른 퀸들의 위치이다. 퀸을 놓을 때 다른 퀸들을 공격할 수 있는 위치라면 놓아서는 안된다.

그렇다면 관리해야 할 것은? 이전에 놓았던 퀸들의 위치를 관리해야 한다. 어차피 같은 row에는 놓을 수 없으므로 퀸들의 위치는 1차원 배열로 col만 관리하면 될 것 같다.

1. row를 0~n까지 순회하면서 퀸을 놓을 col을 결정한다.
2. 이때 이전 row에 위치한 퀸들과의 관계를 고려해 퀸을 놓는다.

class Solution {
    
    static int[] cols;
    static int answer = 0;
    
    public int solution(int n) {
        cols = new int[n];
        dfs(0, n);
        return answer;
    }
    
    private void dfs(int row, int n) {
        if (row == n) {
            answer++;
            return;
        }
        
        for (int col = 0; col < n; col++) {
            if (isPossible(row, col)) {
                cols[row] = col;
                dfs(row + 1, n);
                cols[row] = 0;
            }
        }
    }
    
    private boolean isPossible(int row, int col) {
        // row, col = 현재 놓을 위치
        for (int prevRow = 0; prevRow < row; prevRow++) {
            // 이전 row에 놓았던 것들
            int prevCol = cols[prevRow];
            
            if (col == prevCol) return false;
            if (row + col == prevRow + prevCol) return false;
            if (row - col == prevRow - prevCol) return false;
        }
        return true;
    }
}

주의해야 할 점은 직전 row에 대해서만 검사하는 것이 아니라 이전 모든 row들에 대해 검사를 진행해야 한다는 점이다.