프로그래머스 완전 탐색

문제

풀이

class Solution {
    public int solution(int[][] sizes) {
        int answer = 0;
        int mv = 0;
        int mh = 0;
        for(int i = 0; i < sizes.length; i++) {
            int v = Math.max(sizes[i][0],sizes[i][1]);
            int h = Math.min(sizes[i][0],sizes[i][1]);
            mv = Math.max(mv, v);
            mh = Math.max(mh, h);
        }
        return answer = mv * mh;
    }
}

결과

문제

풀이

import java.util.*;

class Solution {
    public int[] solution(int[] answers) {
        int[] first = { 1, 2, 3, 4, 5 }; // 1번 수포자(5개씩 반복)
        int[] second = { 2, 1, 2, 3, 2, 4, 2, 5 }; // 2번 수포자(8개씩 반복)
        int[] third = { 3, 3, 1, 1, 2, 2, 4, 4, 5, 5 }; // 3번 수포자(10개씩 반복)
        int[] score = { 0, 0, 0 }; // 수포자들의 각 점수
        
        for(int i = 0; i < answers.length; i++) {
            if(answers[i] == first[i % 5]) {
                score[0]++;
            }
            if(answers[i] == second[i % 8]) {
                score[1]++;
            }
            if(answers[i] == third[i % 10]) {
                score[2]++;
            }
        }
        
        int max = Math.max(score[0], Math.max(score[1], score[2]));
        
        ArrayList<Integer> arr = new ArrayList<Integer>();
        for(int i = 0; i < score.length; i++) {
            if(max == score[i]) {
                arr.add(i + 1);
            }
        }
        
        int[] answer = new int[arr.size()];
        for(int i = 0; i < arr.size(); i++) {
            answer[i] = arr.get(i);
        }

        return answer;
    }
}

결과

문제

풀이

import java.util.*;

class Solution {
    static HashSet<Integer> set = new HashSet<>(); // 중복값 제거 위해
    static char[] arr; // 종이조각 저장
    static boolean[] visited; // 사용여부
        
    public int solution(String numbers) {
        int answer = 0;
        arr = new char[numbers.length()];
        visited = new boolean[numbers.length()];
        
        for(int i = 0; i < numbers.length(); i++) {
            arr[i] = numbers.charAt(i); 
        }
                
        dfs("", 0);
        
        answer = set.size();
        return answer;
    }
    
    // dfs 재귀. 가능한 숫자 조합 찾아서 소수면 set에 추가
    public void dfs(String str, int index){
        int num;
        if(str != "") {
            num = Integer.parseInt(str);
            if(isPrime(num)) { // 소수라면
                set.add(num); // set에 추가
            }
        }
        if(index == arr.length) { // 끝까지 했을 경우
            return; 
        }
        
        for(int i = 0; i < arr.length; i++) {
            if(visited[i]) continue; // 방문한 노드면 넘어가기
            visited[i] = true; 
            dfs(str + arr[i], index + 1); // 방문 했을 시 재귀
            visited[i] = false; // 백트래킹
        }
    }

    public boolean isPrime(int num) {
        if(num == 0 || num == 1) {
            return false;
        }
        for(int i = 2; i * i <= num; i++) {
            if(num % i == 0) {
                return false;
            }
        }
        return true;
    }
}

결과

문제

풀이

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        int n = brown + yellow;
        
        for (int i = 3; i < n; i++) {
            int j = n / i;
            if (n % i == 0 && j >= 3) {
                int col = Math.max(i, j);
                int row = Math.min(i, j);
                int y = (col - 2) * (row - 2);
                if (y == yellow) {
                    answer[0] = col;
                    answer[1] = row;
                    return answer;
                }
            }
        }
        
        return answer;
    }
}

결과

문제

풀이

class Solution {
    public int answer = 0;
    public boolean[] visited;

    public int solution(int k, int[][] dungeons) {
        visited = new boolean[dungeons.length];
        dfs(0, k, dungeons);
        return answer;
    }

    public void dfs(int depth, int k, int[][] dungeons) {
        for(int i = 0; i < dungeons.length; i++) {
            if(!visited[i] && dungeons[i][0] <= k) {
                visited[i] = true;
                dfs(depth + 1, k - dungeons[i][1], dungeons);
                visited[i] = false;
            }
        }
        answer = Math.max(answer, depth);
    }
}

결과

문제

풀이

import java.util.*;

class Solution {
    public List<Integer>[] list;
    public int solution(int n, int[][] wires) {
        int answer = 100;
        list = new List[n + 1];
        for(int i = 0; i <= n; i++) {
            list[i] = new ArrayList<>();
        }

        for(int[] wire : wires) {
            list[wire[0]].add(wire[1]);
            list[wire[1]].add(wire[0]);
        }

        for(int[] wire : wires) {
            int a = bfs(wire[0], wire[1], n);
            int b = bfs(wire[1], wire[0], n);
            answer = Math.min(answer, Math.abs(a - b));
        }

        return answer;
    }

    public int bfs(int v1, int v2, int n) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[n + 1];

        int count = 0;

        queue.add(v1);
        visited[v1] = true;

        while(!queue.isEmpty()) {
            int current = queue.poll();
            count++;
            for(int next : list[current]) {
                if(next != v2 && !visited[next]) {
                    queue.add(next);
                    visited[next] = true;
                }
            }
        }

        return count;
    }
}

결과

문제

풀이

import java.util.*;

class Solution {
    static String[] arr;
    static List<String> list;
    public int solution(String word) {
        int answer = 0;
        list = new ArrayList<>();
        arr = {"A", "E", "I", "O", "U"};

        dfs(word, "", 0);
        
        // 선형 탐색
        for(int i = 0; i < list.size(); i++) {
            if(list.get(i).equals(word)) {
                answer = i;
                break;
            }
        }
        
        return answer;
    }

    static void dfs(String word, String str, int depth) {
        list.add(str);
        if(depth == 5) {
            return;
        }
        for(int i = 0; i < arr.length; i++) {
            dfs(word, str + arr[i], depth + 1);
        }
    }
}

결과