Computer Science Knowledge Storage

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

포인트

갈색 타일과 노란색 타일의 합이 카펫의 전체 넓이를 구할 수 있습니다. 그를 이용해서 소인수를 통해 맞는 가로와 세로 값을 구하고 갈색 타일 수가 일치하는 값을 리턴합니다. 가로가 더 길어야 하므로 i가 큰 값으로 시작합니다.

소스코드

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = {0, 0};
        int area = brown + yellow;
        for (int row = area; row > 1; row--) {
            if (area % row == 0) {
                int col = area / row;
                if ((row * 2 + (col - 2) * 2) == brown) {
                    answer[0] = row;
                    answer[1] = col;
                    return answer;
                }
            }
        }
        return answer;
    }
}

코드 설명

• for (int row = area; row > 1; row--) { if (area % row == 0) { int col = area / row;
  
  • row는 카펫의 가로 길이로, 전체 면적(area)의 약수를 찾기 위해 area부터 2까지 역순으로 탐색합니다.
  • if (area % row == 0) 조건은 row가 area의 약수인지 확인합니다.
    약수인 경우, 대응되는 세로 길이 col을 계산합니다 (col = area / row).
• if ((row * 2 + (col - 2) * 2) == brown) { answer[0] = row; answer[1] = col; return answer; } }
  
  • (row * 2 + (col - 2) * 2) == brown 조건은 주어진 row와 col이 brown 타일 수를 만족하는지 확인합니다.
    • row * 2는 위와 아래 테두리를 포함하는 타일 수입니다.
    • (col - 2) * 2는 양쪽의 세로 테두리를 포함하는 타일 수입니다. 여기서 -2는 모서리 타일이 중복 계산되지 않도록 하는 역할을 합니다.
  • 조건이 만족되면 answer 배열에 row와 col 값을 저장하고 반환합니다.

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

포인트

인덱스를 통해서 해당 인덱스가 소수인 지를 확인하고 조합을 통해서 해당 값이 소수인지 확인하는 알고리즘입니다.

소스코드

import java.util.*;

class Solution {
    boolean[] isPrime;
    Set<Integer> uniqueNumbers = new HashSet<>();
    
    public void initPrimeArray(int max) {
        isPrime = new boolean[max + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = false;
        isPrime[1] = false;
        for (int i = 2; i <= max; i++) {
            if (isPrime[i]) {
                for (int j = i * 2; j <= max; j += i) {
                    isPrime[j] = false;
                }
            }
        }
    }

    public void findCombinations(String prefix, String str) {
        if (!prefix.isEmpty()) {
            int num = Integer.parseInt(prefix);
            if (isPrime[num]) {
                uniqueNumbers.add(num);
            }
        }
        for (int i = 0; i < str.length(); i++) {
            findCombinations(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1));
        }
    }

    public int solution(String numbers) {
        int maxNum = (int) Math.pow(10, numbers.length());
        initPrimeArray(maxNum);

        // 모든 조합을 탐색
        findCombinations("", numbers);

        return uniqueNumbers.size();
    }
}

코드 설명

• 소수 배열 초기화 메소드(initPrimeArray)
  
  • initPrimeArray는 max까지의 숫자에 대해 소수 여부를 판별해 isPrime 배열에 저장합니다.
  • 에라토스테네스의 체 알고리즘을 사용하여 소수 판별을 효율적으로 수행합니다.
  • isPrime[i]가 true이면 i는 소수입니다. false로 변경된 값은 소수가 아닙니다.
• 순열 생성 및 소수 판별 메소드(findCombinations)
  
  • findCombinations는 prefix를 통해 현재까지의 숫자 조합을 나타내며, str은 사용 가능한 숫자입니다.
  • prefix가 비어 있지 않으면, 숫자로 변환하여 소수 여부를 확인합니다.
  • prefix와 str을 활용해 재귀적으로 모든 가능한 조합을 생성합니다.
  • 발견된 소수는 uniqueNumbers에 저장됩니다. => 동일한 값을 넣지 않기 위해 Set 자료구조를 이용합니다.
• solution 메소드
  
  • maxNum은 입력된 숫자 문자열의 길이에 따라 가장 큰 숫자를 계산합니다 (10^length).
  • initPrimeArray를 통해 maxNum까지의 소수 여부를 미리 계산합니다.
  • findCombinations 메서드를 호출해 모든 가능한 숫자 조합을 탐색하고 소수를 찾습니다.
  • uniqueNumbers.size()를 반환하여 발견된 소수의 개수를 출력합니다.

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

포인트

모의고사를 제일 많이 맞춘 사람을 구하는 문제입니다. 각 수포자가 규칙이 있으니 문제 번호에 패턴의 길이만큼의 나머지로 문제를 푸는 방법으로 구현하였습니다.

소스코드

import java.util.*;

class Solution {
    public int[] solution(int[] answers) {
        int[][] omr = {
                {1, 2, 3, 4, 5},
                {2, 1, 2, 3, 2, 4, 2, 5},
                {3, 3, 1, 1, 2, 2, 4, 4, 5, 5}
        };
        
        int[] correctCount = new int[3]; // 정답 수를 저장할 배열
        
        for (int i = 0; i < answers.length; i++) {
            for (int j = 0; j < 3; j++) {
                if (omr[j][i % omr[j].length] == answers[i]) {
                    correctCount[j]++;
                }
            }
        }
        
        // 최대 정답 수 찾기
        int maxCorrect = Arrays.stream(correctCount).max().getAsInt();
        
        // 최대 정답 수와 일치하는 사람을 리스트에 추가
        List<Integer> answer = new ArrayList<>();
        for (int i = 0; i < 3; i++) {
            if (correctCount[i] == maxCorrect) {
                answer.add(i + 1); // 사람 번호는 1부터 시작하므로 i + 1
            }
        }
        
        return answer.stream().mapToInt(Integer::intValue).toArray();
    }
}

코드 설명

• int[][] omr
  
  • omr 배열은 각 수포자가 문제를 푸는 패턴을 저장합니다.
  • 각 수포자는 해당 배열에 정의된 주기를 반복하여 답을 제출합니다.
• int[] correctCount = new int[3];
  correctCount는 각 수포자가 맞힌 문제의 수를 저장하는 배열입니다.
• for (int num: nums) { ponkets.put(num, ponkets.getOrDefault(num, 0) + 1); }
  nums 배열을 순회하면서 각 숫자가 ponkets 맵에 이미 존재하는지 확인합니다.
  • 존재하면 해당 숫자의 값에 +1을 합니다.
  • 존재하지 않으면 기본값 0에서 +1을 하여 새로운 키-값 쌍으로 추가합니다.
• for (int i = 0; i < answers.length; i++) {
    for (int j = 0; j < 3; j++) {
      if (omr[j][i % omr[j].length] == answers[i]) {
        correctCount[j]++; } } }
  
  • 외부 for 루프는 주어진 answers 배열을 순회하면서, 각 문제의 정답을 확인합니다.
  • 내부 for 루프는 각 수포자의 답안 패턴을 현재 문제 번호에 맞게 가져옵니다. i % omr[j].length를 사용하여 패턴의 길이에 맞게 인덱스를 순환시킵니다.
  • 만약 해당 수포자의 답이 실제 answers의 답과 일치한다면, 그 수포자의 correctCount 값을 증가시킵니다.
• int maxCorrect = Arrays.stream(correctCount).max().getAsInt();
  correctCount 배열에서 가장 높은 정답 수를 찾아 maxCorrect에 저장합니다.
• 가장 높은 정답 수를 가진 수포자의 번호를 찾고, answer 리스트에 추가합니다. 사람 번호는 1부터 시작하므로 i + 1을 사용합니다.
• return answer.stream().mapToInt(Integer::intValue).toArray();
  answer 리스트를 정수 배열로 변환하여 반환합니다.

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

포인트

하나의 명함의 최대 값을 가로로 설정하고 각 명함마다의 최대의 가로와 세로를 설정해야 모든 명함이 들어가는 명함 케이스의 최소 크기를 측정할 수 있습니다.

소스코드

class Solution {
    public int solution(int[][] sizes) {
        int row = Integer.MIN_VALUE, col = Integer.MIN_VALUE;
        for(int[] size: sizes) {
            row = Math.max(row, Math.max(size[0], size[1]));
            col = Math.max(col, Math.min(size[0], size[1]));
        }
        
        return row * col;
    }
}

코드 설명

• for(int[] size: sizes) {
  row = Math.max(row, Math.max(size[0], size[1]));
  col = Math.max(col, Math.min(size[0], size[1])); }
  sizes 배열을 순회하면서 각 명함의 크기를 확인합니다.
  
  • Math.max(size[0], size[1])를 사용해 현재 명함의 긴 변을 찾습니다. 이 값을 row와 비교하여 row에 더 큰 값을 저장합니다.
  • Math.min(size[0], size[1])를 사용해 현재 명함의 짧은 변을 찾습니다. 이 값을 col과 비교하여 col에 더 큰 값을 저장합니다.
• return row * col
  가장 큰 row와 col 값의 곱을 반환하여 지갑의 최소 크기를 계산합니다. 이 값은 모든 명함이 들어갈 수 있는 최소 크기의 지갑입니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
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의 최소값을 할당합니다.