정리

📌 Hash 자료구조 비교

자료구조	저장 형태	중복	순서	검색 속도	주요 메서드
HashMap	Key-Value 쌍	Key 중복 불가	보장 안 됨	O(1)	put(), get(), getOrDefault(), containsKey()
HashSet	Value만	중복 불가	보장 안 됨	O(1)	add(), contains(), remove()
ArrayList	Value만	중복 허용	유지	O(N)	add(), get(), contains()

📌 HashMap 핵심 메서드

메서드	설명	예시
put(key, value)	저장/업데이트	map.put("apple", 3)
get(key)	값 가져오기	map.get("apple") → 3
getOrDefault(key, defaultValue)	없으면 기본값 반환	map.getOrDefault("grape", 0) → 0
containsKey(key)	키 존재 여부	map.containsKey("apple") → true
keySet()	모든 키 반환	for(String key : map.keySet())
values()	모든 값 반환	for(int val : map.values())

📌 자주 쓰는 패턴

패턴	코드	용도
개수 세기	map.put(key, map.getOrDefault(key, 0) + 1)	빈도수 계산
존재 확인	if(map.containsKey(key))	키 존재 여부
기본값 처리	map.getOrDefault(key, 0)	null 방지
전체 순회	for(String key : map.keySet())	모든 키-값 탐색

📌 List 정렬

방법	코드	설명
오름차순	Collections.sort(list)	사전순/숫자 오름차순
오름차순	list.sort(null)	Java 8+
내림차순	Collections.sort(list, Collections.reverseOrder())	역순
내림차순	list.sort(Comparator.reverseOrder())	Java 8+

📌 문제별 핵심 포인트

문제	자료구조	핵심 아이디어	시간복잡도
완주하지 못한 선수	HashMap	참가자 +1, 완주자 -1 → 값이 1인 사람 찾기	O(N)
전화번호 목록	HashSet	모든 접두어를 HashSet에서 검색	O(N×L)
의상	HashMap	(종류별 개수+1) 모두 곱하고 -1	O(N)
듣보잡	HashMap	두 리스트 모두 등장 → 값이 2인 이름 찾기	O(N+M)
숫자 카드 2	HashMap	카드 개수 세고 쿼리마다 getOrDefault	O(N+M)

📌 경우의 수 공식 (의상 문제)

종류별 개수: a, b, c
전체 경우의 수 = (a+1) × (b+1) × (c+1) - 1

예) headgear: 2개, eyewear: 1개
→ (2+1) × (1+1) - 1 = 5가지

📌 언제 어떤 자료구조를 쓸까?

상황	사용할 자료구조	이유
개수를 세야 할 때	HashMap	Key-Value로 빈도 저장
빠른 존재 확인	HashSet	O(1) 검색
중복 제거	HashSet	자동으로 중복 제거
순서가 중요할 때	ArrayList	순서 보장
정렬이 필요할 때	ArrayList + sort()	정렬 기능 제공

📌 주의사항

주의점	설명
문자열 비교	== 대신 .equals() 사용
null 체크	getOrDefault() 또는 containsKey() 사용
타입 일치	숫자는 Integer, 문자는 String
정렬 후 출력	문제 요구사항 확인 (사전순 등)

코드

완주하지 못한 선수

import java.util.*;
import java.io.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        HashMap<String, Integer> map = new HashMap<>();
        for(String p : participant) {
            map.put(p, map.getOrDefault(p, 0) + 1); // 있으면 "p"의 값, 없으면 0
        }
        
        for(String c : completion) {
            map.put(c, map.get(c) - 1);    // "c"의 값을 가져와서 -1
        }
        
        for(String key : map.keySet()) {
            if(map.get(key) == 1) {
                return key;
            }
        }
        
        return "";
    }
}

전화번호 목록

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        // boolean answer = true;
        
        HashSet<String> set = new HashSet<>();
        for(String p : phone_book) {
            set.add(p);
        }
        
        for(String p : phone_book) {
            for(int i=0; i<p.length(); i++) {
                String prefix = p.substring(0, i);
                if(set.contains(prefix)) {
                    return false;
                }
            }
        }
        return true;
    }
}

⭐의상

import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        // 1. 의상종류별 개수세기
        HashMap<String, Integer> map = new HashMap<>();
        for(String[] c : clothes) { // 2차원 배열을 한 행씩! ex. ["yellow_hat", "headgear"]
            String type = c[1];
            map.put(type, map.getOrDefault(type, 0) + 1);
        }
        // 결과: {"headgear": 2, "eyewear": 1}
        
        // 2. 경우의 수 계산
        int answer = 1;
        for(int c : map.values()) { // map의 값 하나씩 가져오기
            answer *= (c + 1); // 안입는 경우 추가(+1)
        }
        
        // 3. 모든 종류에서 아무것도 안입는 경우 제외 (-1)
        return answer - 1;
    }
}

1764 듣보잡

package A0study;

import java.io.*;
import java.util.*;

public class p1764_듣보잡 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int M = Integer.parseInt(input[1]);

        HashMap<String, Integer> map = new HashMap<>();
        String name = "";

        // 듣도 못한 사람 +1
        for(int i=0; i<N; i++) {
            name = br.readLine();
            map.put(name, map.getOrDefault(name, 0) + 1);
        }

        // 보도 못한 사람 +1
        for(int i=0; i<M; i++) {
            name = br.readLine();
            map.put(name, map.getOrDefault(name, 0) + 1);
        }

        // 듣보 list
        List<String> list = new ArrayList<>();
        for(String n : map.keySet()) {
            if(map.get(n) == 2) {
                list.add(n);
            }
        }
        
        System.out.println(list.size());

        list.sort(null); // 사전순 정렬 (반대: list.sort(Comparator.reversOrder());
        for(String str : list) {
            System.out.println(str);
        }
    }
}

HashSet 사용

HashSet<String> unheard = new HashSet<>();
HashSet<String> unseen = new HashSet<>();

for(int i=0; i<N; i++) {
    unheard.add(br.readLine());
}

for(int i=0; i<M; i++) {
    unseen.add(br.readLine());
}

// 교집합 구하기
List<String> result = new ArrayList<>();
for(String name : unheard) {
    if(unseen.contains(name)) {
        result.add(name);
    }
}

Collections.sort(result);
System.out.println(result.size());
for(String name : result) {
    System.out.println(name);
}

특징	List	HashSet
중복	허용	불가
순서	유지	보장 안 됨
검색 속도	O(N)	O(1)
인덱스 접근	가능	불가

10816 숫자 카드 2

package A0study;

import java.io.*;
import java.util.*;

public class p10816_숫자카드2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());

        // 상근 카드 map<카드번호, 개수>
        HashMap<Integer, Integer> map = new HashMap<>();
        String[] sCard = br.readLine().split(" ");
        for(int i=0; i<N; i++) {
            int num = Integer.parseInt(sCard[i]);
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        // 랜덤 카드를 상근이가 몇개 가지고 있는지 확인
        int M = Integer.parseInt(br.readLine());
        String[] rCard = br.readLine().split(" ");
        for(int i=0; i<M; i++) {
            int num = Integer.parseInt(rCard[i]);
            sb.append(map.getOrDefault(num, 0)).append(" ");
        }

        System.out.println(sb);
    }
}