프로그래머스 자바 :: 완전탐색

 

 

최소직사각형

 

 

 

 

 

내 풀이

 

창의력 문제 같은 느낌..!

 

둘 중 긴 것을 x, 짧은 것을 y로 둔다그렇게 가로 세로를 정하고 그 중에서 가장 큰 것을 찾는다.

 

class Solution {
    public int solution(int[][] sizes) {
        int answer = 0;       
      
        int x = 0;
        int xMax = 0;
        int y = 0;
        int yMax = 0;

        for (int i = 0; i < sizes.length; i++) {
          x = Math.max(sizes[i][0], sizes[i][1]);
          y = Math.min(sizes[i][0], sizes[i][1]);
          xMax = Math.max(xMax, x);
          yMax = Math.max(yMax, y);
        }

        answer = xMax * yMax;
        
        
        return answer;
    }
}

 

---

 

 

모의고사

 

 

 

 

 

 

 

내 풀이

 

순서대로 반복되게 하고 싶을 때 i % one.length 사용하자

List를 Array로 변경하는 경우가 많아서 람다식 외워두면 편리할 듯!

import java.util.*;

class Solution {
    public int[] solution(int[] answers) {
        int[] answer = {};
        
        int[] one = { 1, 2, 3, 4, 5 };
        int[] two = { 2, 1, 2, 3, 2, 4, 2, 5 };
        int[] three = { 3, 3, 1, 1, 2, 2, 4, 4, 5, 5 };
        int[] check = { 0, 0, 0 };
        
        for (int i = 0; i < answers.length; i++){

            if ( answers[i] == one[i % one.length] ){
                check[0]++;
            }
            if ( answers[i] == two[i % two.length] ){
                check[1]++;
            }
            if ( answers[i] == three[i % three.length] ){
                check[2]++;
            }
        }
        

        int max = Math.max(check[0], Math.max(check[1],check[2]));

        List<Integer> list = new ArrayList<>();
        
        for(int i = 0; i < check.length; i++){
            if ( max == check[i] ){
                list.add(i + 1);
            }
        }
        
        return list.stream().mapToInt(Integer::intValue).toArray();
    }
}

 

---

 

소수찾기

 

 

 

 

 

 

 

 

 

내 풀이

 

이건 유튜브 풀이 도움 받아서 풀었다.

나중에 다시 풀면 좋을 듯!!!

 

 

import java.util.*;

class Solution {
    public int solution(String numbers) {
        Solution solution = new Solution();
        return solution.start(numbers);
    }
    
    HashSet<Integer> set = new HashSet<>();

    public int start(String numbers){
        int answer = 0;
        // 1. 모든 조합의 숫자 만들기
        recursive("", numbers);
        
        // 2. 소수 확인
        Iterator<Integer> it = set.iterator();
        while(it.hasNext()){
            int number = it.next();

            if (isOk(number)){

                answer++;
            }
        }
        return answer;
    }

    public void recursive(String comb, String others){
        if(!comb.equals("")){
            set.add(Integer.parseInt(comb));
        }
        
        for (int i = 0; i < others.length(); i++){
            recursive(comb + others.charAt(i), others.substring(0, i) + others.substring(i+1));
        }
    }

    public boolean isOk(int number){
        if(number == 0 || number == 1){
            return false;
        }

        int sqrt = (int)Math.sqrt(number);

        for (int i = 2; i <= sqrt; i++){
            if(number % i == 0){
                return false;
            }
        }
        return true;
    }
}

 

 

---

 

카펫

 

 

 

 

내 풀이

 

이게 왜 완전탐색인지 모르겠는데

되게 금방 풀었다.

 

import java.util.*;

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        
        for(int i = 2; i < brown; i++){
            if((brown + yellow) % i == 0){
                int width = (brown + yellow) / i;
                if((i-2)*(y-2) == yellow){
                    answer[0] = width;
                    answer[1] = i; // i는 height
                    break;
                }
            }
        }
        return answer;
    }
}

 

 

 

---

 

 

피로도

백트래킹 - 나무위키

 

 

[프로그래머스] 피로도 - JAVA [자바]

 

내 풀이

 

dfs 너무 어렵다..

열심히 풀어보고 익숙해져야지!!

 

 

import java.util.*;

public class Solution3 {

    public static int answer;

    public static boolean[] visited;

    public static void main(String[] args) {

   

        int k = 80;

        int[][] dungeons = {{80,20},{50,40},{30,10}};

   

        //dfs

        visited = new boolean[dungeons.length];

        dfs(0, k, dungeons);

        System.out.println(answer);

    }

    public static void dfs(int depth, int fatigue, int[][] dungeons){

        for(int i = 0; i < dungeons.length; i++){

            

            System.out.println("     "+Arrays.toString(visited));

            if(!visited[i] && dungeons[i][0] <= fatigue){

                visited[i] = true; // 방문처리

                dfs(depth + 1, fatigue - dungeons[i][1], dungeons); // 재귀

                visited[i] = false; // 방문 초기화

            }

        }

        System.out.println("depth : "+depth);

        answer = Math.max(answer, depth);

    }

}

 

import java.util.*;

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

        return answer;
    }
    
      public static void dfs(int depth, int fatigue, int[][] dungeons){

        for(int i = 0; i < dungeons.length; i++){
    
            if(!visited[i] && dungeons[i][0] <= fatigue){
                visited[i] = true; // 방문처리
                dfs(depth + 1, fatigue - dungeons[i][1], dungeons); // 재귀
                visited[i] = false; // 방문 초기화
            }
        }
        
        answer = Math.max(answer, depth);
    }
    
}

---

 

 

전력망을 둘로 나누기

 

 

 

 

[프로그래머스/자바] 전력망을 둘로 나누기 - bfs

 

 

 

---

모음사전

 

 

 

 

 

내 풀이

 

아직 완전히 이해하진 못했다

DFS 방식이 익숙하지 않고 for문과 같이 사용하니 더 어렵다.

문제 많이 풀면서 익숙해져야지!

 

import java.util.*;

class Solution {
    
    private static final char[] CHARS = "AEIOU".toCharArray();
    
    public int solution(String word) {
        List<String> words = new ArrayList<>();
        generate("", words);
        return words.indexOf(word);
    }
    
    private void generate(String word, List<String> words){
        words.add(word);
        
        if(word.length() == 5) return;
        
        for (char c : CHARS){
            generate(word + c, words);
        }
    }
}