[BOJ] 14단계 집합과 맵

집합(Set), 맵(Map)

특정 원소가 속해 있는지 빠르게 찾거나, 각 원소에 대응되는 원소를 빠르게 찾는 자료구조

 

1

10815

숫자 카드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        
        Set<String> set = new HashSet<>();
        for(int i = 0; i < N; i++) {
            set.add(tokenizer.nextToken());
        }
        
        int M = Integer.parseInt(reader.readLine());
        tokenizer = new StringTokenizer(reader.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < M; i++) {
            if(set.contains(tokenizer.nextToken())) {
                sb.append(1).append(" ");
            } else {
                sb.append(0).append(" ");
            }
        }
        System.out.println(sb);
    }
}

*같은 로직을 List로 적용하면 시간 초과 발생 (대신 메모리는 더 적게 사용)

*Contains: List -> O(n), Set&Map -> O(1) (트리 구조는 O(log n))

 

2

14425

문자열 집합

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        int N = Integer.parseInt(tokenizer.nextToken());
        int M = Integer.parseInt(tokenizer.nextToken());

        Set<String> set = new HashSet<>();
        for(int i = 0; i < N; i++) {
            set.add(reader.readLine());
        }
        
        int cnt = 0;
        for(int i = 0; i < M; i++) {
            if(set.contains(reader.readLine())){
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}

 

3

7785

회사에 있는 사람

빠른 탐색(contains) -> 정렬(sort)

 

1. TreeSet

add, remove 시 정렬된 상태로 데이터 유지. 생성자에 Comparator 지정 가능

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());

        Set<String> company = new TreeSet<>(Collections.reverseOrder());
        for(int i = 0; i < n; i++) {
            String[] split = reader.readLine().split(" ");
            if(split[1].equals("enter")) {
                company.add(split[0]);
            } else if(split[1].equals("leave")) {
                company.remove(split[0]);
            }
        }
        
        for(String employee: company) {
            System.out.println(employee);
        }
    }
}

 

2. HashSet -> ArrayList

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());

        Set<String> companySet = new HashSet<>();
        for(int i = 0; i < n; i++) {
            String[] split = reader.readLine().split(" ");
            if(split[1].equals("enter")) {
                companySet.add(split[0]);
            } else if(split[1].equals("leave")) {
                companySet.remove(split[0]);
            }
        }

        List<String> companyList = new ArrayList<>(companySet);
        companyList.sort(Collections.reverseOrder());
        for(String employee: companyList) {
            System.out.println(employee);
        }
    }
}

 

4

1620

나는야 포켓몬 마스터 이다솜

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] split = reader.readLine().split(" ");
        int N = Integer.parseInt(split[0]);
        int M = Integer.parseInt(split[1]);
        Map<String, String> pokedex = new HashMap<>();
        for(int i = 1; i <= N; i++) {
            String num = String.valueOf(i);
            String poketmon = reader.readLine();
            pokedex.put(num, poketmon);
            pokedex.put(poketmon, num);
        }
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < M; i++) {
            sb.append(pokedex.get(reader.readLine())).append("\n");
        }
        System.out.print(sb);
    }
}

*양방향으로 데이터를 Map에 추가하여 어떤 키로 접근해도 O(1)로 접근할 수 있도록 한다.

 

5

10816

숫자 카드 2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

        Map<String, Integer> cardCount = new HashMap<>();
        for(int i = 0; i < N; i++) {
            String cardNum = tokenizer.nextToken();
            if(cardCount.containsKey(cardNum)) {
                cardCount.put(cardNum, cardCount.get(cardNum) + 1);
            } else {
                cardCount.put(cardNum, 1);
            }
        }
        
        int M = Integer.parseInt(reader.readLine());
        tokenizer = new StringTokenizer(reader.readLine());

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < M; i++) {
            String cardNum = tokenizer.nextToken();
            if(cardCount.containsKey(cardNum)) {
                sb.append(cardCount.get(cardNum));
            } else {
                sb.append(0);
            }
            sb.append(" ");
        }
        System.out.print(sb);
    }
}

*숫자 카드의 범위가 -10,000,000 ~ 10,000,000 이므로 일반 카운팅 정렬 사용 불가

*해시맵 또는 이진 탐색을 사용해야 함

 

6

1764

듣보잡

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        int N = Integer.parseInt(tokenizer.nextToken());
        int M = Integer.parseInt(tokenizer.nextToken());

        Set<String> set = new HashSet<>();
        for(int i = 0; i < N; i++) {
            set.add(reader.readLine());
        }
        
        List<String> list = new ArrayList<>();
        for(int i = 0; i < M; i++) {
            String s = reader.readLine();
            if(set.contains(s)) {
                list.add(s);
            }
        }
        Collections.sort(list);
        System.out.println(list.size());
        for(int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
    }
}

*원소 포함 여부 -> Set, 정렬 -> List

 

7

1269

대칭 차집합

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        int A = Integer.parseInt(tokenizer.nextToken());
        int B = Integer.parseInt(tokenizer.nextToken());

        tokenizer = new StringTokenizer(reader.readLine());
        Set<String> diffAB = new HashSet<>();
        for(int i = 0; i < A; i++) {
            diffAB.add(tokenizer.nextToken());
        }

        tokenizer = new StringTokenizer(reader.readLine());
        Set<String> diffBA = new HashSet<>();
        for(int i = 0; i < B; i++) {
            String element = tokenizer.nextToken();
            if(diffAB.contains(element)) {
                //집합 A에서 A,B 공통 원소 제거
                diffAB.remove(element);
            } else {
                //집합 B에만 있는 원소 추가
                diffBA.add(element);
            }
        }
        System.out.println(diffAB.size() + diffBA.size());
    }
}

 

8

11478

서로 다른 부분 문자열의 개수

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String str = reader.readLine();
        Set<String> substrings = new HashSet<>();
        for(int i = 0; i < str.length(); i++) {
            for(int j = i + 1; j <= str.length(); j++) {
                substrings.add(str.substring(i, j));
            }
        }
        System.out.println(substrings.size());
    }
}

*String.substring(i, j): index i번째 부터 j-1번째 문자열 반환