Computer Science Knowledge Storage

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

포인트

연속적으로 나타나는 숫자를 파악하기 위해 list나 배열에 index를 통해 확인할 수 있지만
LIFO구조의 Stack이라는 자료구조를 통해 더 효율적으로 문제를 풀 수 있다.

소스코드

import java.util.*;

public class Solution {
    
    public int[] solution(int[] arr) {
        Stack<Integer> ans = new Stack<>();
        
        for (int num: arr) {
            if (ans.isEmpty() || ans.peek() != num) {
                ans.add(num);
            } 
        }
        
        return ans.stream().mapToInt(Integer::intValue).toArray();
        
    }
}

코드 설명

• Stack<Integer> ans = new Stack<>();
  • Integer 타입을 저장하는 스택을 선언한다.
• if (ans.isEmpty() || ans.peek() != num)
  • 스택이 비어있거나 마지막으로 넣은 값과 연속적이지 않으면 스택에 값을 넣는다.
• return ans.stream().mapToInt(Integer::intValue).toArray();
  • int[] 배열로 반환한다.

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

포인트

두번의 정렬을 이용합니다. 장르 별로 정렬을 이용하고, 장르 내에 앨범 별로 정렬을 이용합니다. 

소스코드

import java.util.*;

class Solution {
    static class Album implements Comparable<Album>{
        int idx, playCnt;

        public Album(int idx, int playCnt) {
            this.idx = idx;
            this.playCnt = playCnt;
        }

        @Override
        public int compareTo(Album album) {
            if(this.playCnt == album.playCnt) {
                return this.idx - album.idx;
            } else {
                return album.playCnt - this.playCnt;
            }
        }
    }

    public int[] solution(String[] genres, int[] plays) {
        int len = genres.length;
        Map<String, Integer> genreRank = new HashMap<>();
        Map<String, List<Album>> albumRank = new HashMap<>();

        // 데이터 초기화
        for (int i = 0; i < len; i++) {
            genreRank.put(genres[i], genreRank.getOrDefault(genres[i], 0) + plays[i]);
            albumRank.putIfAbsent(genres[i], new ArrayList<>());
            albumRank.get(genres[i]).add(new Album(i, plays[i]));
        }

        // 장르별 총 재생 횟수에 따라 장르 정렬
        List<String> sortedGenres = new ArrayList<>(genreRank.keySet());
        sortedGenres.sort((a, b) -> genreRank.get(b) - genreRank.get(a));

        List<Integer> ans = new ArrayList<>();

        // 각 장르 내에서 앨범 정렬 및 상위 2곡 선택
        for (String genre : sortedGenres) {
            List<Album> genreAlbum = albumRank.get(genre);
            Collections.sort(genreAlbum);
            for (int i = 0; i < Math.min(2, genreAlbum.size()); i++) {
                ans.add(genreAlbum.get(i).idx);
            }
        }

        // 결과를 배열로 반환
        return ans.stream().mapToInt(Integer::intValue).toArray();
    }
}

코드 설명

static class Album implements Comparable<Album> {
    int idx, playCnt;

    public Album(int idx, int playCnt) {
        this.idx = idx;
        this.playCnt = playCnt;
    }

    @Override
    public int compareTo(Album album) {
        if(this.playCnt == album.playCnt) {
            return this.idx - album.idx;
        } else {
            return album.playCnt - this.playCnt;
        }
    }
}

• Album 클래스:
  • 각 앨범(노래)의 인덱스(idx)와 재생 횟수(playCnt)를 나타냅니다.
  • compareTo 메서드는 재생 횟수를 기준으로 내림차순 정렬하며, 재생 횟수가 같으면 인덱스 기준으로 오름차순 정렬합니다.
• solution 메서드:
  • genreRank 해시맵: 각 장르별 총 재생 횟수를 저장합니다.
  • albumRank 해시맵: 각 장르별로 Album 객체 리스트를 저장합니다.
  • for 루프를 사용해 genreRank와 albumRank를 초기화합니다.
    • 각 노래를 해당 장르의 총 재생 횟수에 추가하고, Album 객체를 장르 리스트에 추가합니다.
  • genreRank의 키(장르)를 재생 횟수에 따라 내림차순으로 정렬하여 sortedGenres 리스트를 만듭니다.
    sortedGenres.sort((a, b) -> genreRank.get(b) - genreRank.get(a));

// 각 장르 내에서 앨범 정렬 및 상위 2곡 선택
for (String genre : sortedGenres) {
    List<Album> genreAlbum = albumRank.get(genre);
    Collections.sort(genreAlbum);
    for (int i = 0; i < Math.min(2, genreAlbum.size()); i++) {
        ans.add(genreAlbum.get(i).idx);
    }
}

• 장르 내 노래 정렬 및 선택:
  • 각 장르의 노래 리스트(genreAlbum)를 Collections.sort를 통해 정렬합니다.
  • 상위 2개의 노래 인덱스를 결과 리스트 ans에 추가합니다.
• int[] 타입으로 반환해야하니 ans 리스트를 배열로 변환해 반환합니다.
  return ans.stream().mapToInt(Integer::intValue).toArray();

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

포인트

확률에서 사용했던 조합을 이용하였습니다. 각 종류별로 nC1을 하고 모든 의상을 안입는 경우를 제외하여 경우의 수를 구하였습니다.

의상 소스코드

import java.util.*;

class Solution {
    
    public int solution(String[][] clothes) {
        int len = clothes.length;
        Map<String, Integer> matches = new HashMap<>();
        
        for(int i = 0; i < len; i++) {
            String item = clothes[i][0];
            String kind = clothes[i][1];
            matches.put(kind, matches.getOrDefault(kind, 0) + 1);
        }
        int answer = 1;
        
        for(String key: matches.keySet()) {
            answer *= matches.get(key) + 1;
        }

        return answer - 1;
        
    }
}

코드 설명

• matches 해시맵: 각 옷의 종류별 개수를 저장합니다.
  • clothes[i][0]은 옷의 이름, clothes[i][1]은 옷의 종류입니다.
  • 해시맵에 옷의 종류를 키로, 해당 종류의 옷의 수를 값으로 저장합니다.
• 모든 옷의 조합 계산:
  • answer는 초기값으로 1로 설정됩니다.
  • 각 옷의 종류마다 (해당 종류의 옷 수 + 1)를 answer에 곱해줍니다.
  • +1은 해당 종류의 옷을 입지 않는 경우를 포함하기 위해 사용됩니다.
• 결과 반환:
  • answer - 1은 아무 옷도 입지 않는 경우를 제외한 옷의 조합 수를 반환합니다.

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

포인트

트라이 노드를 사용해서 문제를 풀었습니다. String에서 한자를 노드의 value로 생각하셔 문자가 같으면 자식 노드로 진입하면서 접두어가 같은지 확인합니다. 같지 않으면 접두어가 같지 않습니다.

이전에 문제를 풀었을 때 O(N^2)의 코드로 풀어서 좋은 방법이 없을까 하다가 트라이 노드로 문제를 풀었습니다. 하지만 코딩 테스트를 진행할 때에는 적합한 풀이는 아니라고 생각합니다.

폰켓몬 소스코드

import java.util.*;

class Solution {
    
    static class PhoneBook {
        // 트라이 노드 클래스 정의
        static class TrieNode {
            Map<Character, TrieNode> children = new HashMap<>();
            boolean isEndOfNumber;
        }

        // 루트 노드
        private TrieNode root = new TrieNode();

        // 번호를 트라이에 삽입
        private boolean insert(String number) {
            TrieNode current = root;
            for (char c : number.toCharArray()) {
                current.children.putIfAbsent(c, new TrieNode());
                current = current.children.get(c);

                // 번호의 중간에서 이미 끝인 경우 접두어 조건 위반
                if (current.isEndOfNumber) {
                    return false;
                }
            }

            // 번호가 완전히 끝난 경우를 표시
            current.isEndOfNumber = true;

            // 현재 노드에 자식이 있는 경우 접두어 조건 위반
            return current.children.isEmpty();
        }

        public boolean isConsistent(String[] phoneBook) {
            for (String number : phoneBook) {
                if (!insert(number)) {
                    return false;
                }
            }
            return true;
        }
    }
    
    public boolean solution(String[] phone_book) {
        PhoneBook phoneBookChecker = new PhoneBook();
        return phoneBookChecker.isConsistent(phone_book);
    }
}

코드 설명

• TrieNode 클래스: 각 문자를 자식으로 연결하는 트라이 노드입니다.
• insert 메서드: 전화번호를 트라이에 삽입하고 접두어 조건을 위반하는지 확인합니다. 중간에 이미 끝인 번호가 있거나 새로 추가된 번호의 마지막 노드에 자식이 있으면 false를 반환하여 접두어 조건 위반을 나타냅니다.
• isConsistent 메서드: 전화번호 목록의 각 번호를 insert 메서드로 확인하여 접두어 관계가 있는 경우 false를 반환합니다.

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

포인트

participant와 completion에서 언급된 선수가 짝수이면 완주한 선수이고 홀수이면 완주하지 못한 선수입니다.

완주하지 못한 선수 소스코드

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        Set<String> runners = new HashSet<>();
        
        for (String runner: participant) {
            if (!runners.contains(runner)) {
                runners.add(runner);
            } else {
                runners.remove(runner);
            }
        }
        
        for (String runner: completion) {
            if (runners.contains(runner)) {
                runners.remove(runner);
            } else {
                runners.add(runner);
            }
        }
        
        for (String ans: runners) {
            return ans;
        }
        return null;
    }
}

코드 설명

• Set<String> runners = new HashSet<>();
  참가자와 완주자를 저장할 집합 runners를 생성합니다.
• for (String runner: participant)
  참가자 배열을 순회하며:
  • 이미 집합에 있는 참가자이면 집합에서 제거합니다 (완주 처리).
  • 그렇지 않으면 집합에 추가합니다.
• for (String runner: completion)
  완주자 배열을 순회하며:
  • 집합에 있는 참가자이면 제거합니다. (완주)
  • 집합에 없는 참가자이면 집합에 추가합니다. (완주하지 못한 참가자)
• for (String ans: runners) { return ans; }
  남은 하나의 이름이 완주하지 못한 참가자이므로 반환합니다.

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

포인트

Map을 사용하여 푸는 문제였습니다. 폰켓몬의 종류와 폰켓몬의 갯수를 확인하는 것이 포인트였다고 생각합니다.

N/2 마리를 선택할 때 폰켓몬의 종류보다 N/2가 더 크면 폰켓몬의 종류를 리턴하고 반대면 N/2를 리턴하면 됩니다.

폰켓몬 소스코드

import java.util.*;

class Solution {
    
    public int solution(int[] nums) {
        Map<Integer, Integer> ponkets = new HashMap<>();
        for (int num: nums) {
            ponkets.put(num, ponkets.getOrDefault(num, 0) + 1);
        }
        
        int halfN = nums.length / 2;
        if (halfN <= ponkets.size()) {
            return halfN;
        } else {
            return ponkets.size();
        }
    }
}

코드 설명

• Map<Integer, Integer> ponkets = new HashMap<>();
  정수형 num을 키로 하고, 각 숫자가 몇 번 등장하는지를 값으로 하는 해시맵 ponkets를 생성합니다.
• for (int num: nums) { ponkets.put(num, ponkets.getOrDefault(num, 0) + 1); }
  nums 배열을 순회하면서 각 숫자가 ponkets 맵에 이미 존재하는지 확인합니다.
  • 존재하면 해당 숫자의 값에 +1을 합니다.
  • 존재하지 않으면 기본값 0에서 +1을 하여 새로운 키-값 쌍으로 추가합니다.
• int halfN = nums.length / 2;
  nums 배열의 길이를 반으로 나눈 halfN을 계산하여 가질 수 있는 폰켓몬 수의 최대치를 나타냅니다.
• if (halfN <= ponkets.size()) { return halfN; } else { return ponkets.size(); }
  고유한 폰켓몬의 종류 수(ponkets.size())와 halfN을 비교합니다.
  • halfN이 고유한 폰켓몬의 종류 수보다 작거나 같으면 halfN을 반환합니다 (최대 가질 수 있는 폰켓몬 수).
  • 그렇지 않으면 고유한 폰켓몬의 종류 수를 반환합니다.