아찌방 하우스

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

풀이 - 나의 생각

선분을 하나씩 제거하면서 BFS로 방문 후 나눠진 전력망의 크기를 비교했습니다.

코드

import java.util.*;

class Solution {
    static List<Integer>[] list;
    static boolean[] visited;
    
    public int solution(int n, int[][] wires) {
        int start = 0, end = 0, A = 0, B = 0, diff = 0, min = Integer.MAX_VALUE;
        list = new ArrayList[n+1];
        
        for(int i = 0; i <= n; i++){
            list[i] = new ArrayList<>();
        }
        
        for(int i = 0; i < wires.length; i++){
            start = wires[i][0];
            end = wires[i][1];    
            list[start].add(end);
            list[end].add(start);
        }
        
        for(int i = 0; i <  wires.length; i++){
            start = wires[i][0];
            end = wires[i][1];
            visited = new boolean[n+1];
            
            A = check(start, end);
            B = n - A;
            diff = Math.abs(B - A);
            if(diff == 0) return 0;
            min = Math.min(min, diff);
        }
        
        
        return min;
    }
    
    public int check(int start, int exclude){
        int cnt = 0;        
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(start);
        visited[start] = true;
        
        while(!q.isEmpty()){
            int now = q.poll();
            cnt++;
            for(Integer next : list[now]){
                if(visited[next] || exclude == next) continue;
                visited[next] = true;
                q.offer(next);
            }
        }
        
        return cnt;
    }
}

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

풀이 - 나의 생각

코드

import java.util.*;
class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int answer = 0;
        long sum1 = 0, sum2 = 0;
        Queue<Integer> q1 = new LinkedList<>();
        Queue<Integer> q2 = new LinkedList<>();
        
        for(int i = 0; i < queue1.length; i++){
            sum1 += queue1[i];
            sum2 += queue2[i];
            q1.offer(queue1[i]);
            q2.offer(queue2[i]);
        }
        
        int tmp = 0;
        while(answer < queue1.length*3){
            if(sum1 > sum2){
                tmp = q1.poll();
                q2.offer(tmp);
                sum1 -= tmp;
                sum2 += tmp;
            }else if(sum1 < sum2){
                tmp = q2.poll();
                q1.offer(tmp);
                sum2 -= tmp;
                sum1 += tmp;
            }else{
                return answer;
            }
            answer++;
        }
        return -1;
    }
}

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

풀이 - 나의 생각

처음에는

조합을 사용해야 하나 했지만

주어지는 number의 길이가 2자리 이상, 1,000,000자리 이하이기 때문에

다른 방법을 생각해야 했습니다.

코드

Stack 활용 ver

import java.util.Stack;
class Solution {
    public String solution(String number, int k) {
        char[] result = new char[number.length() - k];
        Stack<Character> stack = new Stack<>();

        for (int i=0; i<number.length(); i++) {
            char c = number.charAt(i);
            while (!stack.isEmpty() && stack.peek() < c && k-- > 0) {
                stack.pop();
            }
            stack.push(c);
        }
        for (int i=0; i<result.length; i++) {
            result[i] = stack.get(i);
        }
        return new String(result);
    }
}

범위 탐색 ver

class Solution {
    public String solution(String number, int k) {
        String answer = "";
        int start = 0, end = k, maxIndex = 0, max = 0, flag = 0;
        String[] nums = number.split("");
        flag = nums.length - k;
        while(answer.length() < flag){
            max = -1;
            for(int i = start; i <= end; i++){
                int num = Integer.parseInt(nums[i]);
                if(max < num){
                    max = num;
                    maxIndex = i;
                    if(num == 9) break;
                }
            }
            
            k -= (maxIndex - start);
            if(k == 0){
                answer+=number.substring(maxIndex, number.length());
                break;
            }
            start = maxIndex+1;
            answer+=nums[maxIndex];
            end++;
        }
        
        return answer;
    }
}

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

풀이 - 나의 생각

큐를 트럭과 다리를 담당하도록

2개를 선언했다.

1. Truck Queue

우선 Queue에 truck을 다 집어 넣는다.

2. Bridge Queue

우선 Queue에 다리 길이 만큼 0을 다 집어 넣는다.

이때 0은 truck이 올라가 있지 않다는 것을 의미한다.

3. 반복문 돌리기

while문으로 Bridge Queue가 비어 있지 않는 경우 반복문을 돌린다.

다리에 올라가 있는 트럭의 무게를 체크하면서

다음 트럭을 올려도 되는지, 안 되는지 파악한다.

코드

import java.util.*;
class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int time = 0;
        int current_weight = 0;

        Queue<Integer> bridge = new LinkedList<>();
        Queue<Integer> trucks = new LinkedList<>();

        for(int truck : truck_weights){
            trucks.offer(truck);
        }

        for(int i = 0; i < bridge_length; i++){
            bridge.offer(0);
        }
        
        while(!bridge.isEmpty()){
            int passed_truck = bridge.poll();
            current_weight -= passed_truck;
            
            if(!trucks.isEmpty()){
                int next_truck = trucks.peek();
                
                if(current_weight + next_truck <= weight){
                    bridge.offer(trucks.poll());
                    current_weight += next_truck;
                }else{
                    bridge.offer(0);
                }
            }
            
            time++;
        }
        
        return time;
    }
}

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

풀이 - 나의 생각

순열을 사용해서 numbers로 만들 수 있는 모든 조합을 찾아가면서

Set에 저장(중복 제거를 위해)

그 후 소수의 갯수를 체크하면 된다.

코드

import java.util.*;
import java.util.stream.Collectors;

class Solution {
    static boolean[] visited;
    static String[] nums;
    static Set<Integer> set;
    
    public int solution(String numbers) {
        set = new HashSet<>();
        visited = new boolean[numbers.length()];
        nums = numbers.split("");
        makeNum(0, "");
        
        return set.stream()
                .filter(this::isPrime)
                .collect(Collectors.toList())
                .size();
    }
    
    public static void makeNum(int cnt, String stNum){
        if(!stNum.isEmpty()) {
            set.add(Integer.parseInt(stNum));
        }
        
        for(int i =0; i < nums.length; i++){
            if(visited[i]) continue;
            visited[i] = true;
            makeNum(cnt+1, stNum+nums[i]);
            visited[i] = false;
        }
    }
    
    public boolean isPrime(int num){
        if(num < 2) return false;
        for(int i = 2; i <= Math.sqrt(num); i++){
            if(num%i == 0) return false;
        }
        
        return true;
    }
}

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

풀이 - 나의 생각

제목이 거창하지만

결국에는 분할 정복입니다.

분할 정복은

조건에 부합하지 않을 경우 탐색 범위를 줄여가면서

조건을 부합하는 경우를 찾아가는 겁니다.

그렇기 때문에

우선 위의 그림처럼

처음에 2차원 배열을 값들을 한 번 살펴봅니다.

그랬을때 모든 값이 같으면 그 값으로 압축하면 끝

하지만 다른 값이 있으면 4등분하고 다시 검색하는 겁니다.

저 같은 경우

메소드를 하나 만들어 살펴볼 범위와 좌표 값을 넘깁니다.

그러면 그 좌표의 값을 기준으로 두고

넘겨 받은 범위를 둘러봅니다.

모든 값이 같다면 끝

아니라면 분할해서 다시 분석하도록 요청합니다.

위의 그림을 보면 처음에는 배열의 크기 8만큼을(Size = 8)

arr[0][0]부터(x = 0, y = 0) 탐색을 합니다.

그런데 arr[1][0] == 0 이기에 분할 후 탐색을 해야합니다.

그렇기에 size 를 절반으로 나눈후(4를 나누는게 아닙니다.)

적절한 탐색 위치를 지정해주면 됩니다.

그 적절한 탐색 위치는

x, x + size, y, y + size를 적적히 조합하면 구할 수 있습니다

코드

import java.util.*;

class Solution {
    static int[][] map;
    static int[] answer;
    public int[] solution(int[][] arr) {
        answer = new int[2];
        map = Arrays.copyOf(arr, arr.length);
        divide(arr.length, 0, 0);
        return answer;
    }
    
    public static void divide(int size, int x, int y){
        int num = map[x][y];
        boolean flag = true;
        for(int i = x; i < x+size; i++){
            for(int j = y; j < y+size; j++){
                if(num != map[i][j]){
                    flag = false;
                    break;
                }
            }
        }
        if(flag){
            answer[num]++;
        }else{
            size/=2;
            divide(size, x, y);
            divide(size, x+size, y);
            divide(size, x, y+size);
            divide(size, x+size, y+size);
        }
    }
}

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

풀이 - 나의 생각

처음에는

주어진 숫자(numbers[i])에 +1(이하 B)을 하고

XOR 연산을 한 후

Long.bitCount 를 통해 1의 갯수의 차이를 구한다.

이 차이가 2이하일 경우 answer[i]에 값을 저장한다.

아닐 시 B에 +1을 한다.

위를 반복했다.

결과적으로 시간 초과가 발생했다.

아무래도 숫자가 커질 수록 (주어진 범위가 10의 15승이다)

비트 1개의 차이를 찾는게 오래 걸리는 것이라고 판단했다.

그래서 단순하게 생각했다.

그냥 2진법을 생각하면

맨 오른쪽부터 1, 2, 4, 8, 16, ........ 2의 n배 수를 나타낸다.

그러면 그 숫자들을 더한다.

더해서 나온 수와 numbers[i] 값을 XOR 연산 후

1의 개수를 세어본다.

그게 2 이하면 정답이라는 것이다.

코드

class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = new long[numbers.length];
        long a = 0, plus = 1;
        long tmp = 0;
        for(int i = 0; i <numbers.length; i++){
            a = numbers[i];
            plus = 1;
            String num = Long.toBinaryString(a);
            for(int j = 0; j < num.length(); j++){
                tmp = Long.bitCount(a ^ (a + plus));
                if(tmp <= 2) {
                    answer[i] = a + plus;
                    break;
                }
                plus *= 2;
            }
        }
        return answer;
    }
}

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

풀이 - 나의 생각

원래 레일에는 1번 택배부터 n번 택배까지 순서대로 올라와 있다.

하지만 목적지에 따라

기사가 원하는 순서대로 바꾸기위해서

보조 컨테이너 벨트를(이하 보조 벨트) 사용할 수 있다.

이 보조 벨트에서 짐을 내리는 순서는

올려놓은 순서의 역순으로만 내릴 수 있다.

즉, 4번을 먼저 싣기위해

1, 2, 3 번을 보조 벨트에 올리면

3, 2, 1 순으로 꺼낼 수 있다.

이건 뭐다?

First In, Last Out => Stack 이다.

그래서 이 위의 설명처럼

order[i] 가 원래 짐과 순서가 다르면

그 순서를 맞추기 위해

원하는 짐의 순서(order[i])까지

스택에 넣어주면 된다.

그 후에

스택의 최상위 값(stack.peek())가 원하는 짐이 맞는지 체크만 해주면 된다.

코드

import java.util.*;
class Solution {
    public int solution(int[] order) {
        int answer = 0;
        int len = order.length;
        int box = order[0], num = 0;
        Stack<Integer> subRail = new Stack<>();
                
        for(int i = 0; i < len; i++){
            box = order[i];
            while(num+1 <= box){
                subRail.push(num+1);
                num++;
            }
            
            if(subRail.peek() == box){
                subRail.pop();
                answer++;
            }else break;
        }
        return answer;
    }
}