[12일 차] 알고리즘 (Basic4)

---

25/02/11 (화)

국민취업지원제도 상담을 받고와서 1시간 30분 지각을 했습니다.

드디어 상담 3회가 끝났습니다.

앞으로는 지각, 결석할 일이 없겠네요.

상담 끝나고 맥날 먹고싶은데 맥모닝 시간이고, KFC는 안열고, 중국집도 안열고, 김밥천국은 안먹고싶고..

그냥 버스타고 왔습니다. 매우 배고프네요..

---

 

1.  교재 강의

1.1. Ch07 큐

• 상담때문에 못들었습니다

 

1.1. Ch08 해시

1) 해시의 특성을 활용하는 분야

• 비밀번호 관리
• 데이터베이스 인덱싱 : 데이터베이스에 저장된 데이터를 효율적으로 검색할 때
• 블록체인

 

1.2. Ch09 트리

1) 트리

 

2) 이진 트리

package basic.Ch12_Tree;

import java.util.ArrayDeque;
import java.util.Queue;

public class BinaryTreeSearch {

    // 완전이진트리(complete binary tree) vs 포화이진트리(perfect  binary tree)
	/*
	 				1
	 		2			   3
	  4        5      6         7
   8    9   10  11  12  13    14   15
	 */

    // 이진 트리를 배열로
    static int[] tree = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }; // 0 dummy
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        bfs(1);
        System.out.println(sb);

        sb.setLength(0);

        dfs(1);
        System.out.println(sb);

    }

    static void bfs(int idx) {
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(idx);

        while( ! queue.isEmpty() ) {

            int curIdx = queue.poll();
            sb.append(tree[curIdx]).append(" ");

            // 꺼낸 노드의 자식 노드 방문
            int lcIdx = curIdx*2;
            int rcIdx = curIdx*2 + 1;

            // range check
            if( lcIdx < tree.length ) queue.offer(lcIdx);
            if( rcIdx < tree.length ) queue.offer(rcIdx);
        }
    }

    static void dfs(int idx) {
        // 기저조건
        if( idx >= tree.length ) return;

        sb.append(tree[idx]).append(" ");

        // 현재 노드의 자식 노드 방문
        // 왼쪽
        dfs(idx*2);
        // 오른쪽
        dfs(idx*2 + 1);
    }
}

 

2. 실습

1) 카드 뭉치 (큐)

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

class Solution {
    public String solution(String[] cards1, String[] cards2, String[] goal) {
        Queue<String> cardsDeque1 = new ArrayDeque<>(Arrays.asList(cards1));
        Queue<String> cardsDeque2 = new ArrayDeque<>(Arrays.asList(cards2));
        Queue<String> goalDeque = new ArrayDeque<>(Arrays.asList(goal)); //완성할 기준
        
        while(!goalDeque.isEmpty()){
            if(!cardsDeque1.isEmpty() && cardsDeque1.peek().equals(goalDeque.peek())) { //card1에서 가능한지
                cardsDeque1.poll();
                goalDeque.poll();
            }else if(!cardsDeque2.isEmpty() && cardsDeque2.peek().equals(goalDeque.peek())) {
                cardsDeque2.poll();
                goalDeque.poll();
            }else {
                break;
            }
        }
        return goalDeque.isEmpty() ? "Yes" : "No";
        
    }
}

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

 

2) 오픈 채팅방 (해시)

import java.util.ArrayList;
import java.util.HashMap;

class Solution {
    public String[] solution(String[] record) {
        HashMap<String, String> msg = new HashMap<>();
        msg.put("Enter", "님이 들어왔습니다.");
        msg.put("Leave", "님이 나갔습니다.");
        
        HashMap<String, String> uid = new HashMap<>();
        
        for(String s : record) {
            String[] cmd = s.split(" ");
            if(cmd.length == 3){
                uid.put(cmd[1], cmd[2]);
            }
        }
        
        ArrayList<String> answer = new ArrayList<>();
        
        for (String s : record) {
            String[] cmd = s.split(" ");
            
            if(msg.containsKey(cmd[0])) {
                answer.add(uid.get(cmd[1]) + msg.get(cmd[0]));
            }
        }
        return answer.toArray(new String[0]);
    }
}

• 유저 아이디가 유일한 식별자이다.
• 닉네임이 변경되는 건 "Enter" 와 "Change" 이다.
• 최종 출력은 "Change" 가 제외된 "Enter" 와 "Leave" 에 대해서만 처리된다.

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

 

3) 랜선 자르기 (이진 트리)

package basic;


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class S2_1654_Lan {
    static int K, N;
    static long left, right, mid;
    static int[] input;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        K = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        input = new int[K];

        for (int i = 0; i < K; i++) {
            input[i] = Integer.parseInt(br.readLine());
        }

        // 풀이
        // N 길이 1 ~ 가장 큰 값

        Arrays.sort(input);

        left = 1; // 길이 최소
        right = input[K-1]; // 길이 최대

        while( left <= right ) {
            long count = 0;

            // 중간값으로 계산
            mid = (left + right ) / 2;

            // 모든 K 개에 대해서 mid 로 잘라 본다.
            for (int i = 0; i < K; i++) {
                count += ( input[i] / mid ); // 나눈 몫 0, 1.7 = 1, 2.3 = 2
            }

            if( count >= N ) { // N 개 보다 더 많이 만드는 게 아니고 가장 큰 N 개
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }

        System.out.println(right);
//      System.out.println(left - 1);
    }
}

 

4.  마무리

1) 더 공부할 것

• 버퍼리더
• 토크나이저
• 전부 다..