해시

HashMap 기본 문법 정리:

// 1. 선언과 생성
Map<String, Integer> map = new HashMap<>();

// 2. 데이터 추가/수정
map.put("key", 10);          // 키-값 저장
map.put("key", 20);          // 같은 키면 값 덮어쓰기

// 3. 데이터 조회
map.get("key");              // 값 반환 (없으면 null)
map.getOrDefault("key", 0);  // 값 반환 (없으면 기본값 0)

// 4. 존재 확인
map.containsKey("key");      // 키 존재 여부 (true/false)
map.containsValue(10);       // 값 존재 여부 (true/false)

// 5. 크기와 비어있는지 확인
map.size();                  // 요소 개수
map.isEmpty();               // 비어있는지 (true/false)

// 6. 순회하기
for (String key : map.keySet()) {        // 키들만 순회
    System.out.println(key);
}

for (Integer value : map.values()) {     // 값들만 순회
    System.out.println(value);
}

// 7. 삭제
map.remove("key");           // 키-값 쌍 삭제
map.clear();                 // 모든 요소 삭제

 

 

완주하지 못한 선수 - 정렬 + 투 포인터 접근법

문제 해결 아이디어

• 두 배열을 정렬 후 같은 인덱스끼리 비교
• 처음으로 다른 값이 나오는 순간, 그게 완주하지 못한 선수!

핵심 로직

1. 정렬: participant와 completion 모두 오름차순 정렬
2. 투 포인터: 두 배열을 동시에 순회하며 비교
3. 차이 발견: 값이 다르면 participant의 해당 값이 정답

코드

import java.util.Arrays;

class Solution {
    public String solution(String[] participant, String[] completion) {
        Arrays.sort(participant);
        Arrays.sort(completion);
        
        int i = 0, j = 0;
        while (i < participant.length && j < completion.length) {
            if (participant[i].equals(completion[j])) {
                i++; j++;
            } else {
                return participant[i];
            }
        }
        return participant[i];
    }
}

 

 

전화번호 목록 - 해시 접근법

문제 해결 아이디어

• 각 전화번호를 쪼개서 접두어들을 만들고, 그 접두어들이 전체 목록에 있는지 확인
• HashSet을 사용해서 빠르게 찾기!

핵심 로직

1. HashSet 생성: 모든 전화번호를 HashSet에 저장
2. 접두어 생성: 각 번호를 1글자, 2글자, 3글자... 로 자르기
3. 접두어 검색: 잘라낸 접두어가 HashSet에 있으면 접두어 관계 발견!

import java.util.HashSet;

class Solution {
    public boolean solution(String[] phone_book) {
        // 1. 모든 전화번호를 HashSet에 저장
        HashSet<String> set = new HashSet<>();
        for (String phone : phone_book) {
            set.add(phone);
        }
        
        // 2. 각 전화번호의 접두어들이 set에 있는지 확인
        for (String phone : phone_book) {
            for (int i = 1; i < phone.length(); i++) {
                String prefix = phone.substring(0, i);
                if (set.contains(prefix)) {
                    return false; // 접두어 발견!
                }
            }
        }
        
        return true; // 접두어 없음
    }
}

시간복잡도

• O(n × m): n = 전화번호 개수, m = 평균 전화번호 길이

 

의상

문제 해결 아이디어

1. 해시를 초기화 해준다.
2. 2차원 배열에서 첫번째와 두번째에 어떤 타입이 들어가야하는지 정해준다.
3. for문으로 돌려서 있는 옷 종류를 넣어준다. 물론 안입는 것도 존재하니까 type마다 + 1개씩
4. 그리고 type마다 나온 개수를 곱하고 -1을 해준다.
5. 결과를 리턴한다.

코드

import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        
        Map<String, Integer> map = new HashMap<>();
        
        for (String[] item : clothes) {
            String type = item[1];
            map.put(type, map.getOrDefault(type, 0) + 1);
        }
        
        int result = 1;
        for (int count : map.values()) {
            result *= (count + 1);
        }
        
        return result - 1;
    
    }
}

 

 

 

        for (String[] item : clothes) {
            String type = item[1];
            map.put(type, map.getOrDefault(type, 0) + 1);
        }

• String[] item : clothes의 각 행 (한 벌의 옷 정보)
• item[1] : 옷 종류 추출 (item[0]은 옷 이름)
• map.getOrDefault(type, 0) + 1 : 해당 종류 개수 +1 (없으면 0에서 시작)

 

 

        int result = 1;
        for (int count : map.values()) {
            result *= (count + 1);
        }

• map.values() : 맵의 모든 값들 (각 종류별 개수들)
• (count + 1) : 안 입는 경우 포함
• result *= : 모든 경우의 수 곱하기

 

 

        return result - 1;

• 아무것도 안 입는 경우 1개 제외하고 반환

 

베스트앨범

문제 분석

베스트앨범 문제의 핵심 규칙:

1. 장르별 총 재생횟수가 많은 장르부터 앨범에 수록
2. 각 장르 내에서는 재생횟수가 많은 순서로 수록
3. 각 장르에서 최대 2곡까지만 수록
4. 재생횟수가 같으면 고유번호가 낮은 순서

문제 해결 아이디어

1. 장르별 총 재생횟수 계산
2. 장르를 총 재생횟수 순으로 정렬
3. 모든 곡 정보를 객체로 저장 (확장성 고려)
4. 각 장르별로 곡들 필터링 및 정렬
5. 정렬된 장르 순서대로 최대 2곡씩 선택
6. 결과 배열로 변환

코드

import java.util.*;

class Solution {
    
    // 곡 정보를 담는 클래스 (확장성을 위한 설계)
    class Song {
        String genre;  // 장르명
        int id;        // 고유번호 (인덱스)
        int plays;     // 재생횟수
        
        // 생성자
        Song(String genre, int id, int plays) {
            this.genre = genre;
            this.id = id;
            this.plays = plays;
        }
    }
    
    public int[] solution(String[] genres, int[] plays) {
        
        // 1단계: 장르별 총 재생횟수 계산
        Map<String, Integer> playCount = new HashMap<>();
        for (int i = 0; i < genres.length; i++) {
            String genre = genres[i];      // 현재 곡의 장르
            int play = plays[i];           // 현재 곡의 재생횟수
            // 해당 장르의 총 재생횟수에 현재 곡의 재생횟수 누적
            playCount.put(genre, playCount.getOrDefault(genre, 0) + play);
        }
        
        // 2단계: 장르를 총 재생횟수 순으로 정렬
        List<String> sortedGenres = new ArrayList<>(playCount.keySet());
        // 람다식으로 내림차순 정렬 (총 재생횟수 많은 장르부터)
        sortedGenres.sort((a, b) -> playCount.get(b) - playCount.get(a));
        
        // 3단계: 모든 곡 정보를 Song 객체로 저장
        List<Song> allSongs = new ArrayList<>();
        for (int i = 0; i < genres.length; i++) {
            // i가 곧 고유번호, genres[i]는 장르, plays[i]는 재생횟수
            allSongs.add(new Song(genres[i], i, plays[i]));
        }
        
        // 최종 결과를 저장할 리스트
        List<Integer> result = new ArrayList<>();
        
        // 4단계: 정렬된 장르 순서대로 처리
        for (String genre : sortedGenres) {
            
            // 현재 장르의 곡들만 필터링
            List<Song> genreSongs = new ArrayList<>();
            for (Song song : allSongs) {
                if (song.genre.equals(genre)) {
                    genreSongs.add(song);
                }
            }
            
            // 현재 장르의 곡들을 재생횟수 순으로 정렬
            genreSongs.sort((song1, song2) -> {
                // 재생횟수가 다르면 재생횟수 내림차순
                if (song1.plays != song2.plays) {
                    return song2.plays - song1.plays;
                }
                // 재생횟수가 같으면 고유번호 오름차순
                return song1.id - song2.id;
            });
            
            // 최대 2곡까지만 결과에 추가
            for (int i = 0; i < Math.min(2, genreSongs.size()); i++) {
                result.add(genreSongs.get(i).id);  // 고유번호만 추가
            }
        }
        
        // List<Integer>를 int[] 배열로 변환하여 반환
        return result.stream().mapToInt(i -> i).toArray();
    }
}