Computer Science Knowledge Storage

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

H-Index를 찾기 위해서 정렬이 꼭 필요합니다. 또 i를 0부터 순회하면 len - i는 최대 값이 되므로 다음 코드와 같이 로직을 계산합니다.

소스코드

import java.util.*;

class Solution {
    public int solution(int[] citations) {
        Arrays.sort(citations);

        int len = citations.length;
        for (int i = 0; i < len; i++) {
            if (citations[i] >= len - i) {
                return len - i;
            }
        }
        return 0;
    }
}

코드 설명

• Arrays.sort(citations);
  주어진 citations 배열을 오름차순으로 정렬합니다. 이는 논문의 인용 횟수를 작은 순서부터 큰 순서로 정렬하여 H-Index를 계산하기 쉽게 만듭니다.
• for (int i = 0; i < len; i++) { if (citations[i] >= len - i) { return len - i; } }
  citations 배열을 순회하며 H-Index 조건을 검사합니다.
  
  • citations[i]는 논문의 인용 횟수를 나타냅니다.
  • len - i는 현재 인덱스 기준으로 남은 논문 개수를 나타냅니다.
  • if (citations[i] >= len - i): 논문 i번째의 인용 횟수가 남은 논문 개수 이상일 경우, H-Index 조건을 만족합니다. 즉, 인용 횟수가 적어도 len - i 이상인 논문이 len - i편 존재한다는 의미입니다.
• 루프를 다 돌아도 H-Index 조건을 만족하는 값이 없다면 0을 반환합니다. 이는 모든 논문의 인용 횟수가 H-Index 조건을 만족하지 않을 때입니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

각 자릿수를 토대로 비교하면서 가장 큰 수를 구할 수도 있겠습니다만, 시간 초과가 날 것입니다.
이를 위해 문자열 정렬로 생각하여 문제를 풀었습니다. 예를 들어, a = "3"와 b = "30"일 때 (b + a)는 "303"이고 (a + b)는 "330"입니다. 따라서 "330"이 더 앞에 오도록 구현하였습니다.

소스코드

import java.util.*;

class Solution {
    public String solution(int[] numbers) {
        StringBuilder sb = new StringBuilder();

        String[] strNumbers = Arrays.stream(numbers)
                .mapToObj(String::valueOf)
                .toArray(String[]::new);

        Arrays.sort(strNumbers, (a, b) -> (b + a).compareTo(a + b));

        for (String num : strNumbers) {
            sb.append(num);
        }

        if (sb.toString().charAt(0) == '0') {
            return "0";
        }
        
        return sb.toString();
    }
}

코드 설명

• StringBuilder sb = new StringBuilder();
  문자열을 효율적으로 생성하기 위해 StringBuilder 객체 sb를 생성합니다. 최종 결과 문자열을 생성하는 데 사용됩니다.
• String[] strNumbers = Arrays.stream(numbers).mapToObj(String::valueOf).toArray(String[]::new);
  numbers 배열의 각 요소를 문자열로 변환하여 새로운 String 배열 strNumbers에 저장합니다.
  
  • Arrays.stream(numbers): numbers 배열을 스트림으로 변환합니다.
  • .mapToObj(String::valueOf): 각 정수 요소를 String 객체로 변환합니다.
  • .toArray(String[]::new): 스트림의 결과를 String 배열로 반환합니다.
• Arrays.sort(strNumbers, (a, b) -> (b + a).compareTo(a + b));
  strNumbers 배열을 사용자 정의 비교자로 정렬합니다.
  
  • 정렬 기준을 문자열 (a + b) 와 (b + a)의 비교로 결정합니다.
  • (b + a).compareTo(a + b): 두 연결 결과를 비교하여 내림차순으로 정렬합니다.
• if (sb.toString().charAt(0) == '0') { return "0"; }
  생성된 문자열이 0으로 시작하는 경우, 이는 numbers 배열의 모든 요소가 0일 때입니다. 따라서 "0"을 반환합니다.
• return sb.toString();
  StringBuilder에 추가된 모든 요소를 문자열로 변환하여 반환합니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

배열의 서브 어레이를 구하는 것이 포인트였다고 생각합니다. 이를 위해 자바의 copyOfRange() 함수를 이용합니다.

소스코드

import java.util.*;

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        List<Integer> answerList = new ArrayList<>();
        
        for (int[] command: commands) {
            int i = command[0] - 1;
            int j = command[1];
            int k = command[2] - 1;
            int[] subArray = Arrays.copyOfRange(array, i, j);
            Arrays.sort(subArray);
            answerList.add(subArray[k]);
        }
        
        return answerList.stream().mapToInt(Integer::intValue).toArray();
    }
}

코드 설명

• List<Integer> answerList = new ArrayList<>();
  정수형 요소를 저장할 수 있는 ArrayList 객체 answerList를 생성합니다.
  이 리스트는 각 명령(commands)에 따라 추출된 결과값들을 저장하는 역할을 합니다.
• int[] subArray = Arrays.copyOfRange(array, i, j); Arrays.sort(subArray);
  array의 i부터 j (종료 인덱스는 포함되지 않음)까지의 부분 배열을 subArray에 복사하고, 이를 오름차순으로 정렬합니다.
  
  • copyOfRange(array, i, j)는 array 배열을 i부터 j-1까지 배열을 생성합니다.
• answerList.add(subArray[k]);
  정렬된 subArray에서 k번째 요소를 가져와 answerList에 추가합니다.
• return answerList.stream().mapToInt(Integer::intValue).toArray();
  결과 값을 int[] 배열로 변환 후 반환합니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

최댓값과 최솟값을 효율적으로 관리 및 구하기 위해 최소 힙과 최대 힙을 두개 선언하고 연산에 맞게 관리합니다.

소스코드

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        PriorityQueue<Integer> max = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> min = new PriorityQueue<>();
        
        for (String operation : operations) {
            String[] split = operation.split(" ");
            String command = split[0];
            int number = Integer.parseInt(split[1]);

            switch (command) {
                case "I":
                    min.add(number);
                    max.add(number);
                    break;
                case "D":
                    if (number == 1 && !max.isEmpty()) {
                        int maxNum = max.poll();
                        min.remove(maxNum);
                    } else if (number == -1 && !min.isEmpty()) {
                        int minNum = min.poll();
                        max.remove(minNum);
                    }
                    break;
            }
        }
        
        int[] answer = {0, 0};
        if (!min.isEmpty() && !max.isEmpty()) {
            answer[0] = max.poll();
            answer[1] = min.poll();
        }
        
        return answer;
    }
}

코드 설명

• PriorityQueue<Integer> max = new PriorityQueue<>(Collections.reverseOrder());
  PriorityQueue<Integer> min = new PriorityQueue<>();
  최대 힙 max와 최소 힙 min을 초기화합니다. 이는 최소 값 및 최대 값을 빠르게 가져오거나 삭제하기 위해 사용됩니다.

• for (String operation : operations)
  operations 배열의 각 명령어를 순차적으로 탐색합니다. 각 명령어는 삽입 또는 삭제 작업을 나타냅니다.
  • String[] split = operation.split(" ");
    명령어를 공백으로 나누어 split 배열에 저장합니다. 첫 번째 요소는 명령어(I 또는 D), 두 번째 요소는 숫자를 나타냅니다.
  • String command = split[0];
    명령어(I 또는 D)를 command에 저장합니다.
  • int number = Integer.parseInt(split[1]);
    명령어의 숫자 값을 정수로 변환하여 number에 저장합니다.
  • switch (command)
    명령어(command)에 따라 조건문을 통해 동작을 결정합니다.
    • case "I":
      number를 min과 max 두 큐 모두에 추가합니다.
    • case "D":
      • if (number == 1 && !max.isEmpty())
        number가 1이면 최대값 삭제 명령어입니다. max에서 최대값을 poll()로 제거하고, min에서도 동일한 값을 remove()로 삭제합니다.
      • else if (number == -1 && !min.isEmpty())
        number가 -1이면 최소값 삭제 명령어입니다. min에서 최소값을 poll()로 제거하고, max에서도 동일한 값을 remove()로 삭제합니다.
  • int[] answer = {0, 0};
    • 결과를 담을 배열 answer를 선언하고 초기화합니다.
  • if (!min.isEmpty() && !max.isEmpty())
    • min과 max가 모두 비어 있지 않으면, answer[0]에 max의 최대값, answer[1]에 min의 최소값을 할당합니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

가장 최소의 처리량 평균 시간을 구하는 문제였습니다. 요청시간이 빠른 순대로 정렬을 하면 짧은 작업시간을 가지는 일들에 대해서는 너무 오래 기다리게 되고, 짧은 작업시간 순대로 정렬을 하면 요청이 먼저 온 작업을 처리를 하지 못하게 됩니다. 

따라서 현재 시간에 따라 처리 가능한 작업을 구하고 그 중에서 요청시간이 짧은 것을 먼저 처리합니다.

소스코드

import java.util.*;

class Solution {
    
    static class Job implements Comparable<Job> {
        int requestTime, workingTime;
        
        public Job(int requestTime, int workingTime) {
            this.requestTime = requestTime;
            this.workingTime = workingTime;
        }
        
        @Override
        public int compareTo(Job j) {
            if (this.requestTime == j.requestTime) {
                return this.workingTime - j.workingTime;
            }
            return this.requestTime - j.requestTime;
        }
    }
    
    public int solution(int[][] jobs) {
        PriorityQueue<Job> disk = new PriorityQueue<>();
        int len = jobs.length;
        
        for(int[] job: jobs) {
            disk.add(new Job(job[0], job[1]));
        }
        
        int time = 0; // 현재 시간
        int ans = 0; // 처리량 평균 구하기
        List<Job> execList = new ArrayList<>();
        
        while (!disk.isEmpty() || !execList.isEmpty()) {
            // 현재 시간에 요청된 작업을 모두 execList에 추가
            while (!disk.isEmpty() && time >= disk.peek().requestTime) {
                execList.add(disk.poll());
            }

            // 작업을 소요 시간 기준으로 정렬
            if (!execList.isEmpty()) {
                Collections.sort(execList, Comparator.comparingInt(job -> job.workingTime));
                Job exec = execList.remove(0);
                if (time < exec.requestTime) {
                    time = exec.requestTime;
                }
                time += exec.workingTime;
                ans += time - exec.requestTime;
            } else if (!disk.isEmpty()) {
                time = disk.peek().requestTime;
            }
        }
        
        return ans / len;
    }
}

코드 설명

Job 클래스

• Job 클래스는 Comparable 인터페이스를 구현하며, 작업의 요청 시간(requestTime)과 소요 시간(workingTime)을 필드로 가지고 compareTo 메서드는 Job 객체를 요청 시간 순서로 정렬합니다. 요청 시간이 동일할 경우, 소요 시간 기준으로 정렬하도록 조건을 설정할 수 있습니다.

• PriorityQueue<Job> disk = new PriorityQueue<>();
  작업 요청 시간 기준으로 정렬되는 우선순위 큐를 초기화합니다. Job 객체를 담아 요청 시간이 빠른 순서대로 작업을 처리할 수 있습니다.
• while문 내부 변수 사용부분
  • time은 현재 시각을 나타내며, ans는 작업 완료까지 걸린 총 시간을 누적합니다.
  • execList는 현재 처리 가능한 작업 목록입니다.
• while (!disk.isEmpty() || !execList.isEmpty()) { ... }
  • disk 큐의 작업 중 현재 time에 요청된 작업을 execList로 이동합니다.
  • execList에 작업이 있으면 소요 시간 기준으로 정렬하고, 가장 짧은 작업을 선택하여 실행합니다.
  • time이 해당 작업의 요청 시간보다 작으면, time을 그 요청 시간으로 맞춥니다.
  • time을 해당 작업의 소요 시간만큼 증가시키고, 요청부터 종료까지 걸린 시간(time - requestTime)을 ans에 더합니다.
  • 만약 execList가 비어 있고 disk에 작업이 남아 있다면, time을 다음 작업의 요청 시간으로 설정하여 작업을 진행할 수 있게 합니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

최솟값을 찾기 위해 정렬을 사용해도 되지만 가장 효율적인 자료 구조 Heap을 이용하여 스코빌 지수의 최솟값을 찾도록 코드를 구현하였습니다.

소스코드

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> scovilles = new PriorityQueue<>();
        
        for (int level: scoville) {
            scovilles.add(level);
        }
        
        int mix = -1;
        int ans = 0;
        while (scovilles.peek() < K) {
            if (scovilles.size() < 2) {
                return -1;
            }
            int first = scovilles.poll();
            int second = scovilles.poll();
            mix = first + second * 2;
            scovilles.add(mix);
            ans++;
        }
        
        return ans;
    }
}

코드 설명

• PriorityQueue<Integer> scovilles = new PriorityQueue<>();
  스코빌 지수를 저장하는 Heap을 생성합니다. 해당 힙은 최소 힙으로 구현합니다.
• 섞은 음식의 스코빌 지수
  • while 루프는 큐의 최솟값(scovilles.peek())이 K 미만인 동안 반복됩니다.
  • 이때 큐의 크기가 2 미만이 되면, 더 이상 결합할 수 없으므로 -1을 반환하여 목표를 달성할 수 없음을 나타냅니다.
  • 최솟값 두 개를 꺼내어(poll() 메서드 사용) 결합하여 새로운 스코빌 지수(first + second * 2)를 계산합니다.
  • 새로 만든 스코빌 지수를 큐에 다시 추가하고, 결합 횟수 ans를 증가시킵니다.
• 섞은 횟수를 반환합니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
접은 글을 통해 먼저 답변을 해보시고 제가 정리한 답을 확인해보시기 바라겠습니다!!

면접 리스트

NAT 네트워크를 사용했을때의 사이드 이펙트는 없는가?

왜 라우팅 알고리즘은 모든 라우터에서 실행되어야 하는가?

라우터에서의 라우팅과 포워딩의 차이를 설명해주세요.

loopback address는 무엇인가? 또 어떻게 쓰일 수 있는가

default gateway는 무슨 역할을 하는가?

만약 라우팅 테이블에 다음 목적지에 대한 맵핑정보가 없다면 라우터는 어떻게 동작하는가?

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
접은 글을 통해 먼저 답변을 해보시고 제가 정리한 답을 확인해보시기 바라겠습니다!!

면접 리스트

여러개의 프로세스가 존재할 때 트랜스포트 레이어의 동작을 설명해보세요

소켓 생성과 삭제에서 발생하는 오버헤드를 줄이는 방법은 무엇이 있을까요?

N+1번의 세그먼트에 대한 ACK가 도착하고 N에 대한 ACK는 도착하지 않았을 때 TCP는 어떻게 동작하는가?

네트워크 레이어의 목적은 무엇일까요?

왜 트랜스포트 레이어에 checksum이 있는데 네트워크 레이어에도 체크섬이 있는가?