BangBang's Devlogs

https://programmers.co.kr/learn/courses/30/lessons/43164#

DFS로 구현함

해결 방안

1. DFS를 이용하여 전체 여행 경로의 경우를 구하며 한가지의 경로를 String형의 route에 누적한 뒤 한가지 경로가 다 누적되면 routes에 추가함
=> 나중에 정렬을 쉽게 이용하기 위하여 String 값으로 저장

2. 목적지가 2가지 이상일 경우 알파벳 순이 되어야하므로 sort 정렬을 이용하여 routes를 정렬함

3. 정렬된 routes.get(0)이 답이 되고 String 값으로 저장하였으므로 answer의 String[] 형식에 맞게 파싱하여 저장해줌

코드

import java.util.*;
// 여행 경로
class Solution {
    public static String[] answer;
    public static String route;
    public static List<String> routes;
    public static boolean[] used;
    
    public static void dfs(String[][] tickets, String departure, String destination, int index){
        route += (destination + " ");
        
        if(index == tickets.length){
        	routes.add(route);
            //System.out.println(route);
            return;
        }

        // 도착지가 출발지가 되고 출발지인 모든 경우 DFS
        String start = destination;
        String nextDeparture;
        String nextDestination;
        for(int i=0; i<tickets.length; i++){
            nextDeparture = tickets[i][0];
            nextDestination = tickets[i][1];

            if(start.equals(nextDeparture) && used[i] == false){
                used[i] = true;
                dfs(tickets, nextDeparture, nextDestination, index+1);
                used[i] = false;
                // 전 단계로 초기화
                route = route.substring(0, route.length()-4);
            }
        }
            
        
    }
    
    public String[] solution(String[][] tickets) {
        System.out.println(tickets.length);
        answer = new String[tickets.length + 1];
        routes = new ArrayList<>();
        used = new boolean[tickets.length];
        
        for(int i=0; i<used.length; i++){
            used[i] = false;
        }
        
        String start = "ICN";
        String departure;
        String destination;
        for(int i=0; i<tickets.length; i++){
            departure = tickets[i][0];
            destination = tickets[i][1];
            
            // 첫 스타트가 ICN인 모든 경우 DFS 해서 routes에 저장
            if(start.equals(departure)){
                used[i] = true;
                route = departure + " ";
                dfs(tickets, departure, destination, 1);
                // dfs가 끝나고 나면 티켓은 다시 사용 안한 것으로 초기화
                used[i] = false;
            }
        }
        
        // 모든 경로 저장하고 String 오름차순
        Collections.sort(routes);
        
        //System.out.println("answer = " + routes.get(0));

        answer = routes.get(0).split(" ");
        
        return answer;
    }
}

https://programmers.co.kr/learn/courses/30/lessons/43162?language=java

문제 이해

문제의 예시를 보면 왼쪽의 그림은 네트워크가 2개인 경우이고 오른쪽의 그림은 네트워크가 1개인 경우임

즉, n개의 컴퓨터들이 있고 연결되어있는 컴퓨터들이 각각의 네트워크임

따라서 DFS를 통해 연결되어있는 컴퓨터들끼리 네트워크를 구성하므로 네트워크의 갯수를 구해주는 문제임 

해결 방안

1. solution() 에서 전체 컴퓨터들의 방문 여부를 따져주고 방문되지 않은 컴퓨터의 경우 dfs()를 통해 연결된 컴퓨터들을 방문됬다고 표시되면 하나의 네트워크가 구성된다. 하나의 네트워크가 구성되면 answer 값을 증가해줌 

2. dfs() 에서는 해당 방문 컴퓨터를 방문했다고 체크해주고 인접 컴퓨터를 돎
이 때 인접 컴퓨터 여부는 computers에 저장되있는 값을 이용함(1이면 인접 컴퓨터)
인접한 컴퓨터이면서 방문한적 없으면 dfs()를 해줌

코드

// 네트워크
class Solution {
    public static int answer = 0;
    public static boolean[] visited;
    
    public static void dfs(int start, int[][] computers){
        visited[start] = true;
        
        // 인접 노드 돌기
        for(int i=0; i<computers[start].length; i++){
            // 자기는 제외
            if(i==start)
                continue;
            // 인접한 노드 아니여도 제외
            if(computers[start][i] == 0)
                continue;
            // 인접한 노드 
            else{
                // 방문한 적 없으면 dfs
                if(visited[i] == false)
                    dfs(i, computers);
            }
        }
    }
    
    // n: vertex , computers: edge
    public int solution(int n, int[][] computers) {
        
        visited = new boolean[n];
        for(int i=0; i<visited.length; i++){
            visited[i] = false;
        }
        
        // i는 start
        for(int i=0; i<visited.length; i++){
            // 방문한 적이 없으면 dfs
            if(visited[i] == false){
                dfs(i, computers);
                answer++;
            }
        }
        
        return answer;
    }
}

https://programmers.co.kr/learn/courses/30/lessons/43165?language=java

해결 방안

1. number 배열의 숫자를 계속 빼거나 더하는 두 가지 경우로 나눠져서 DFS를 이용하여 풀었음

2. DFS index가 numbers.length 까지 오게 되면 numbers에 쌓인 값들을 다 더해 sum을 구하고 그 sum이 target과 같으면 answer를 ++ 해줌

코드

// 타겟 넘버
class Solution {
    public static int answer = 0;
    
    public static void dfs(int[] numbers, int target, int index){
        if(index == numbers.length){
            int sum = 0;
            
            for(int i=0; i<numbers.length; i++){
                sum += numbers[i];
            }
            if(sum == target)
                answer++;
        }
        // 더하거나 빼거나 두 경우
        else{
            numbers[index] *= 1;
            dfs(numbers, target, index+1);
            
            numbers[index] *= -1;
            dfs(numbers, target, index+1);
        }
    }
    
    public int solution(int[] numbers, int target) {
        
        dfs(numbers, target, 0);
        
        return answer;
    }
}

https://programmers.co.kr/learn/courses/30/lessons/43238?language=java

이분탐색을 응용하여 문제를 구현하였음

이분탐색 알고리즘 코드

int BinarySearch(int arr[], int target) {
    int start = 0;
    int end = arr.length - 1;
    int mid;

    while(start <= end) {
        mid = (start + end) / 2;

        if (arr[mid] == target)
            return mid;
        else if (arr[mid] > target)
            end = mid - 1;
        else
            start = mid + 1;
    }
    return -1;
}

해결 방안 제시에 앞서 이분 탐색을 이용하여 알고리즘을 구현할 때 위와 같은 코드를 이해하고 있으며 이 코드를 응용하여 구현하는 것이 좋음

해결 방안

1. 무엇(start, mid, end)을 이분 탐색할 것이고 어떤 걸(위의 BinarySearch 코드의 target) 비교하여 다음 탐색 구간을 정할지 먼저 찾음
=> 이분 탐색할 것: 심사를 받는데 걸리는 시간(mid)
=> 비교대상(target) : n(입국 심사를 기다리는 사람)

2. 심사를 받는데 최소로 걸리는 시간(answer)을 구하므로 심사를 받는데 걸리는 시간(mid)을 이분 탐색함

3. Input에서 비교 대상으로 n(입국 심사를 기다리는 사람)명이 주어지므로 n명을 target으로 정해 다음 탐색 구간을 정함

4. n과 비교하기위해 주어진 mid 시간동안 검사할 수 있는 사람 수(sum)을 구하는 알고리즘이 포함되어야함

5. answer를 구하기 위해 최소 시간을 찾아내야함

이분 탐색 알고리즘 코드와 해결 방안을 조합하여 구현하면 아래와 같은 코드가 될 수 있음

코드

import java.util.*;

// 입국심사
class Solution {
    public long solution(int n, int[] times) {
        // 모든 사람이 심사를 받는데 걸리는 시간의 최솟값
        long answer = Long.MAX_VALUE;
        
        Arrays.sort(times);
        
        long start, mid, end;
        start = 0;
        end = Long.MAX_VALUE;
        long sum;
        // 모든 사람이 심사 받는데 걸리는 시간 이분 탐색
        // mid : 심사를 받는데 주어진 시간
        // sum : 주어진 시간(mid)동안 심사를 받을 수 있는 사람 수 
        while(start <= end){
            
            mid = (start + end) / 2;
            
            sum = 0;
            // 주어진 시간동안 몇명 검사 할 수 있는지 누적합
            for(int i=0; i<times.length; i++){
                sum += mid / times[i];
                
                if(sum >= n)
                    break;
            }
            
            // 비교 대상(사람 수)
            // 검사 다 못할 때(시간 부족)
            if(n > sum){
                start = mid + 1;
            }
            // 검사 다 했을 때 (시간이 남음)
            // 최소 시간 찾아야함
            else{
                end = mid - 1;
                answer = Math.min(answer, mid);
            }
        }
        
        return answer;
    }
}

https://programmers.co.kr/learn/courses/30/lessons/42746?language=java

Comparator 인터페이스에 대한 지식이 있어야 문제를 쉽게 접근 가능할 수 있을 것이라고 생각함
정렬을 위한 인터페이스로 Comparable과 Comparator가 있는데 Comparable 인터페이스는 보통 객체의 기본적이고 고정된 정렬을 위해 사용하며 Comparator 인터페이스는 기본 정렬 기준과 다르게 정렬하고 싶을 때 사용함

해결 방안

1. numbers 1차원 int 배열 크기만큼 sNumbers 1차원 String 배열을 만들고 int 값들을 String 값들로 저장해줌

2. 위의 코드 처럼 sNumbers 배열을 정렬해주는데 정수들을 붙여서 만들었을 때 크게 만들 수 있도록 내림차순으로 정렬해줌
=> 나중에 다 이어 붙일 것이므로 내림차순 정렬 

3. sNumbers 배열들을 순서대로 다 이어 붙여줌

4. numbers 배열에 {0,0,0} 과 같이 0 값들만 가진 배열이 있을 수 있으므로 sNumbers 배열의 값들을 전부 이어 붙인 answer이 0으로 시작하면 "0"을 저장해줌

코드

import java.util.*;
// 가장 큰 수
class Solution {
    public String solution(int[] numbers) {
        String answer = "";
        
        String[] sNumbers = new String[numbers.length];
        
        for(int i=0; i<numbers.length; i++){
            sNumbers[i] = numbers[i] + "";
        }
        
        Arrays.sort(sNumbers, new Comparator<String>(){   
            @Override
            public int compare(String n1, String n2){
                // 더해서 큰 값 만드는 내림 차순
                return (n2+n1).compareTo(n1+n2);
            }
        });
        
        for(int i=0; i<sNumbers.length; i++){
            answer += sNumbers[i];
        }
        
        // "000" 과 같이 0이 여러번인 경우 제외
        if(answer.startsWith("0"))
            answer = "0";
        
        return answer;
    }
}

https://programmers.co.kr/learn/courses/30/lessons/43237?language=java

이분탐색을 응용하여 문제를 구현하였음

이분탐색 알고리즘 코드

int BinarySearch(int arr[], int target) {
    int start = 0;
    int end = arr.length - 1;
    int mid;

    while(start <= end) {
        mid = (start + end) / 2;

        if (arr[mid] == target)
            return mid;
        else if (arr[mid] > target)
            end = mid - 1;
        else
            start = mid + 1;
    }
    return -1;
}

해결 방안 제시에 앞서 이분 탐색을 이용하여 알고리즘을 구현할 때 위와 같은 코드를 이해하고 있으며 이 코드를 응용하여 구현하는 것이 좋음

해결 방안

1. 무엇(start, mid, end)을 이분 탐색할 것이고 어떤 걸(위의 BinarySearch 코드의 target) 비교하여 다음 탐색 구간을 정할지 먼저 찾음
=> 이분 탐색할 것: 예산의 상한액(mid) 
=> 비교대상(target) : M(주어진 총 예산)

2. 예산의 최대 상한액(answer)을 구하므로 예산의 상한액(mid)을 이분 탐색함

3. Input에서 비교 대상으로 M(주어진 총 예산)이 주어지므로 M을 target으로 정해 다음 탐색 구간을 정함

4. M과 비교하기위해 상한액을 적용한 budgets 배열들의 합(sum)을 구하는 알고리즘이 포함되어야함

5. answer를 구하기 위해 최대 상한액을 찾아내야함

이분 탐색 알고리즘 코드와 해결 방안을 조합하여 구현하면 아래와 같은 코드가 될 수 있음

코드

import java.util.*;
// 예산
class Solution {
    // budgets: 지방에서 요청한 예산 / M: 총 예산
    public int solution(int[] budgets, int M) {
        int answer = 0;
        long sum = 0;
        
        Arrays.sort(budgets);
        
        for(int budget : budgets){
            sum += budget;
        }
        
        // 요청하는 예산들의 합 <= 총 예산
        if(sum <= M){
            // 상한액은 가장 큰 값
            answer = budgets[budgets.length-1];
        }
        // 요청하는 예산들의 합 > 총 예산
        else{
            
            int start, mid, end;
            sum = 0;
            // 예산의 크기
            start = 0; 
            mid = 0;
            end = budgets[budgets.length-1]; 
            
            // 이진 탐색
            while(start <= end){
                
                mid = (start + end) / 2;
                
                sum = 0;    
                // sum 구하기
                for(int i=0; i<budgets.length; i++){
                    if(budgets[i] < mid){
                        sum += budgets[i];
                    }
                    else{
                        sum += mid;
                    }
                }
                
                // 비교대상
                if(sum > M){
                    end = mid - 1;
                }
                else{
                    start = mid + 1;
                    answer = Math.max(answer, mid);
                }
                
            }
        }
        
        return answer;
    }
}

https://programmers.co.kr/learn/courses/30/lessons/42841

해결 방안

1. 전체 경우는 (000~999)라고 생각하였으며 그 중 서로 다른 3자리 숫자 이므로 (123~987)로 범위를 줄일 수 있었음
또한 같은 숫자와 0이 들어간 숫자가 나온 경우 continue 해줘서 가능한 전체 숫자를 정해줌 (위와 같이 전체 경우가 주어짐)

2. 전체 경우의 수를 돌면서 baseball 이차원 배열에 담긴 전체 수와 비교하여 strike 수와 ball 수가 모두 같으면 가능한 답이 되므로 answer++ 해줌
=> 도중 flag를 두어 strike 수와 ball 수가 틀린 경우 break를 해주고 flag에 따라 answer++를 해줌

코드

import java.util.*;

// 숫자 야구

class Solution {
    public int solution(int[][] baseball) {
        // 세자리 수 가능한 답의 갯수
        int answer = 0;
        
        int[] answerNum = new int[3];
        int[] baseballNum = new int[3];
        int strike, ball;
        boolean flag;
        
        // 세자리수 전체 경우 돌면서 baseball 전체 행이랑 비교
        // 전체 경우: 1~9 3개의 임의 숫자(서로다른 3자리 숫자)(123~987)
        for(int i=123; i<=987; i++){
            // 각 자리 수
            answerNum[0] = i/100;
            answerNum[1] = (i%100)/10;
            answerNum[2] = i%10;
            
            // 0 나오면 제외
            if(answerNum[0] == 0 || answerNum[1] == 0 || answerNum[2] == 0)
                continue;
            
            // 같은 숫자 나온 경우 제외
            if(answerNum[0] == answerNum[1] || answerNum[1] == answerNum[2] || answerNum[0] == answerNum[2])
                continue;
            
            flag = true;
            // baseball 한 행씩 비교해서 전체 baseball 행 다 맞으면 answer++
            for(int j=0; j< baseball.length; j++){
                
                strike = 0;
                ball = 0;
                
                // baseball 각 자릿수
                baseballNum[0] = baseball[j][0]/100;
                baseballNum[1] = (baseball[j][0]%100)/10;
                baseballNum[2] = baseball[j][0]%10;
                
                // answerNum과 baseballNum 스트라이크 체크
                for(int k=0; k<3; k++){
                    if(answerNum[k] == baseballNum[k])
                        strike++;
                }
                
                // answerNum과 baseballNum 볼 체크
                for(int k=0; k<3; k++){
                    for(int x=0; x<3; x++){
                        if(k != x){
                            if(answerNum[k] == baseballNum[x])
                                ball++;
                        }
                    }
                }
                
                // baseball에 저장되 있는 스트라이크, 볼 수와 우리가 체크한 strike, ball 수 비교
                if(baseball[j][1] == strike && baseball[j][2] == ball){
                    continue;
                }
                else{
                    flag = false;
                    break;
                }   
            }
            if(flag)
                answer++;
        }
        
        return answer;
    }
}

https://programmers.co.kr/learn/courses/30/lessons/42842

첫 번째 풀이

카펫의 중앙 부분의 가로, 세로 길이를 이용하여 완전 탐색을 이용해 문제를 풀었음

해결 방안

1. 문제에 주어진 input으로 테두리(갈색) 갯수와 중앙(노란색) 갯수를 알 수 있고 이 것을 통해 카페의 전체 total 갯수를 알 수 있다고 생각함 

2. 전체 갯수는 (yellow 부분의 가로+2) * (yellow 부분의 세로+2)와 같다고 생각함
=> 테두리(갈색)가 한 줄 이므로 전체 가로 길이 = 왼쪽, 오른쪽 테두리(yellow 부분의 가로+2), 전체 세로 길이 = 위, 아래 테두리(yellow 부분의 세로+2)

3. yellow 갯수도 (yellow 부분의 가로) * (yellow 부분의 세로) 와 같음

4. 두 가지 조건(2,3)에 맞는 yellow의 가로,세로 길이를 찾기 위해 이중 반복문을 이용하여 가로 길이에 따른 세로 길이를 +1씩 해주면서 완전 탐색함

5. 답을 찾는데 걸리는 시간을 줄이기 위해 세로 길이를 늘려주면서 (카펫의 가로 길이 >= 세로 길이) 조건을 만족하지 않을때 break 함

코드

// 카펫
// 중앙은 노란색, 테두리 1줄이 갈색인 카펫
// 카펫 가로길이 >= 세로길이
class Solution {
    public int[] solution(int brown, int yellow) {
        // 카펫 가로, 세로 크기
        int[] answer = new int[2];
        
        int total = brown + yellow;
        
        // yellow
        int yWidth = 0;
        int yHeight = 0;
        
        // 전체 갯수 = (옐로 부분 가로 + 2) * (옐로 부분 세로 + 2)
        while(total != (yWidth+2) * (yHeight+2)){
            yWidth++;
            yHeight = 0;

            // yellow 갯수 = 옐로 부분 가로 * 옐로 부분 세로 
            while(yellow != yWidth * yHeight){
            	yHeight++ ;              
                // 세로 길이가 가로길이보다 길면 break
                if(yHeight >= yWidth) {
                	break;                	
                }
            }   
        }
        
        // yellow의 약수들 다 구한다음
        answer[0] = 2 + yWidth;
        answer[1] = 2 + yHeight;

        return answer;
    }
}

두 번째 풀이

해결 방안

1. 전체 크기를 total에 저장해주고 x(가로의 크기)를 total부터 1까지 줄여나가는 반복문을 이용하였다.
이때 total이 x(가로)로 나눠지면 y(세로)를 구해주고 구해진 x(가로), y(세로)를 이용하여 brown이 될 부분을 구해서 실제 brown 값과 비교해서 값이 같으면 그때 x(가로), y(세로) 값이 정답이므로 break해준다.

코드

// 카펫
// 중앙 노란색 테두리 1줄은 갈색
// 노란색 갈색 갯수 기억
// 카펫의 가로 길이는 세로 길이와 같거나 세로 길이보다 김
class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = {0,0};
        int x = 0; // 가로
        int y = 0; // 세로
        int total = brown + yellow;
        
        int tempBrown;
        for(int i=total; i>0; i--){
            x = i;
            
            // total이 x로 나눠지면 y 구함
            if(total % x == 0){
                y = total/x;
                
                tempBrown = (2*x + 2*y) -4;
                if(tempBrown == brown)
                    break;
            }
            else{
                continue;
            }
        }
        
        answer[0] = x;
        answer[1] = y;
        return answer;
    }
}