[2월 2주차] 표현 가능한 이진트리 2023 KAKAO BLIND RECRUITMENT

[eunbc]

필수 문제

표현 가능한 이진트리

코드 💻

자율 문제

문제1

코드 💻

문제2

코드 💻

[park0jae]

필수 문제

표현 가능한 이진트리

코드 💻

자율 문제

백준 - 오리

코드 💻

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    private static final char[] DUCK = {'q','u','a','c','k'};
    static char[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        arr = br.readLine().toCharArray();
        solve();

    }

    private static void solve() {
        if(arr.length % 5 != 0) {
            System.out.println(-1);
            return;
        }

        int len = arr.length;
        int cnt = 0;

        while(len != 0) {
            int duckIdx = 0;
            int idx = 0;
            boolean check = false;
            int[] tmp = new int[5];

            while(idx < arr.length) {
                if(arr[idx] == DUCK[duckIdx]) {
                    tmp[duckIdx++] = idx;
                    if(duckIdx == 5) {
                        check = true;
                        len -= 5;
                        duckIdx = 0;
                        for(int i=0; i<5; i++) {
                            arr[tmp[i]] = 'O';
                        }
                    }
                }
                idx++;
            }
            if(check) cnt++;
            else break;
        }
        System.out.println(len == 0 ? cnt : -1);
    }
}

프로그래머스 - 귤 고르기

코드 💻

import java.util.*;

class Solution {
    public int solution(int k, int[] tangerine) {
        int answer = 0;
        
        Arrays.sort(tangerine);
        
        Map<Integer, Integer> map = new HashMap<>();
        
        for(int i=0; i<tangerine.length; i++){
            map.put(tangerine[i], map.getOrDefault(tangerine[i], 0) + 1);
        }
        List<Integer> keySet = new ArrayList<>(map.keySet());
        
        keySet.sort((o1,o2) -> map.get(o2).compareTo(map.get(o1)));
        
        for(int i : keySet){
            k -= map.get(i);
            answer++;
            if(k <= 0) break;
        }
        
        return answer; 
    }
    
}

[eunbc]

필수 문제

표현 가능한 이진트리

코드 💻

- ?? 문제를 이해 못함...

자율 문제

백준 - 동전1

코드 💻

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main { 

    static int n,k;
    static int[] coin;
    static int[] dp = new int[10001];
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();

        coin = new int[n];
        for(int i=0; i<n; i++) {
            coin[i] = sc.nextInt();
        }

        // dp[i] => 동전을 사용해서 i원을 만드는 경우의 수
        dp[0] = 1;
        for(int i=0; i<n; i++) {
            for(int j=coin[i]; j<=k; j++) {
                dp[j] = dp[j] + dp[j-coin[i]];
            }
        }

        System.out.println(dp[k]);
    }


}

백준 - 삼각그래프

코드 💻

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main { 
    static int N;
    static long[][] graph;
    static long[][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int now = 0;

        while(true) {
            N = Integer.parseInt(br.readLine());
            if(N==0) return;
    
            graph = new long[N][3];
            dp = new long[N][3];

            for(int i=0; i<N; i++) {
                st = new StringTokenizer(br.readLine());
                for(int j=0; j<3; j++) {
                    graph[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            // 0행
            dp[0][0] = Integer.MAX_VALUE;
            dp[0][1] = graph[0][1];
            dp[0][2] = dp[0][1] + graph[0][2];

            // 1행~
            for(int i=1; i<N; i++) {
                // 0
                dp[i][0] = Math.min(dp[i-1][0], dp[i-1][1]) + graph[i][0];

                // 1
                dp[i][1] = Math.min(Math.min(Math.min(dp[i-1][0], dp[i-1][1]), dp[i-1][2]), dp[i][0]) + graph[i][1];

                // 2
                dp[i][2] = Math.min(Math.min(dp[i-1][1], dp[i-1][2]), dp[i][1]) + graph[i][2];
            }

            System.out.println(++now+ ". " + dp[N-1][1]);
        }
    }


}

[byulcode]

필수 문제

표현 가능한 이진트리

코드 💻

class Solution {
	public int[] solution(long[] numbers) {
		int[] answer = new int[numbers.length];
		for (int i = 0; i < numbers.length; i++) {
			String binary = convertToBinary(numbers[i]);
			boolean flag = check(binary, 0, binary.length()-1);

			if (flag) {
				answer[i] = 1;
			} else {
				answer[i] = 0;
			}
		}
		return answer;
	}

	// 포화이진트리 생성 메서드
	public String convertToBinary(long num) {
		String binary = Long.toBinaryString(num);
		int h = 0;
		int nodes = 1;

		while (nodes < binary.length()) {
			h++;
			nodes += (int)Math.pow(2, h);
		}
		return "0".repeat(nodes - binary.length()) + binary;
	}

	public boolean check(String binary, int start, int end) {
		if (start == end) return true; // 리프노드에서 호출한 경우
		int root = (start + end) / 2;

		if (binary.charAt(root) == '0') {
			for (int i = start; i < root; i++) {
				if (binary.charAt(i) == '1')
					return false;
			}
			for (int i = root + 1; i <= end; i++) {
				if (binary.charAt(i) == '1')
					return false;
			}
		}
		return check(binary, start, root - 1) && check(binary, root + 1, end);
 	}
}

자율 문제

유기농 배추

코드 💻

class Solution {
	public int[] solution(long[] numbers) {
		int[] answer = new int[numbers.length];
		for (int i = 0; i < numbers.length; i++) {
			String binary = convertToBinary(numbers[i]);
			boolean flag = check(binary, 0, binary.length()-1);

			if (flag) {
				answer[i] = 1;
			} else {
				answer[i] = 0;
			}
		}
		return answer;
	}

	// 포화이진트리 생성 메서드
	public String convertToBinary(long num) {
		String binary = Long.toBinaryString(num);
		int h = 0;
		int nodes = 1;

		while (nodes < binary.length()) {
			h++;
			nodes += (int)Math.pow(2, h);
		}
		return "0".repeat(nodes - binary.length()) + binary;
	}

	public boolean check(String binary, int start, int end) {
		if (start == end) return true; // 리프노드에서 호출한 경우
		int root = (start + end) / 2;

		if (binary.charAt(root) == '0') {
			for (int i = start; i < root; i++) {
				if (binary.charAt(i) == '1')
					return false;
			}
			for (int i = root + 1; i <= end; i++) {
				if (binary.charAt(i) == '1')
					return false;
			}
		}
		return check(binary, start, root - 1) && check(binary, root + 1, end);
 	}
}

• bfs

문제2

코드 💻