해시 셋, 맵 문제 풀어보기(스터디)

제이 용·2025년 11월 15일

알고리즘 풀기(스터디)

목록 보기

1/2

문제(해시 셋)

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

예제 입력 1 
5
6 3 2 10 -10
8
10 9 -5 2 3 4 5 -10

예제 출력 1 
1 0 0 1 1 0 0 1

문제 이해

상근이가 가지고 있는 숫자 카드의 개수 N
숫자 카드에 적혀있는 정수
M(1 ≤ M ≤ 500,000)
상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수
출력값은 0과 1로만

필요 지식

HashSet

중복을 자동 제거해주며, 값의 존재 여부 검사에 최적화된 자료구조이다.

참고 : https://st-lab.tistory.com/240

왜 빠른가?

특정 값의 위치를 계산해 바로 접근
리스트처럼 처음부터 끝까지 검색하지 않는다는 것.

어떤 상황에서 쓰면 좋은가?

“값이 있니? 없니?” 같은 포함 여부 확인
중복 제거가 필요한 상황
빠른 검색이 중요한 경우

사용법 요약

add(value) : 값 넣기
contains(value) : 포함 여부 확인
remove(value) : 값 제거

다른 배열 메서드와 비슷하다.

풀어보기

구상

1. 숫자 N을 입력 받는다.
2. 정수를 N개만큼 입력한다.
3. 숫자 M을 입력 받는다.
4. 포함여부 확인할 숫자를 M개 만큼 입력한다.
5. M개 만큼 있으면 1, 없으면 0이 출력된다.

필요코드

버퍼리더
해쉬셋 생성
입력값 출력을 위한 스트링빌더
반복문, 조건문
sout

- 버퍼리더
- 해쉬셋 생성
- 스트링빌더

1. 숫자 N을 입력 받는다.

2. 정수를 N개만큼 입력한다.

- N개만큼 정수를 배열에 추가(반복문) [배열A]
- 추가된만큼 해시 셋 배열에 추가

3. 숫자 M을 입력 받는다.

4. 포함여부 확인할 숫자를 M개 만큼 입력한다.

- M개만큼 정수를 배열에 추가(반복문) [배열B]
- 해시 셋 배열에 [배열B]에 있는 정수들을 M개만큼 포함여부 확인

5. M개 만큼 있으면 1, 없으면 0이 출력된다.(조건문)

- 스트링빌더로 한번에 출력

코드작성

package Sutdy;

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

public class Beak10815_Hash {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        HashSet<Integer> cards = new HashSet<>();
        StringBuilder sb = new StringBuilder();

        // 1. 숫자 N을 입력 받는다.
        int n = Integer.parseInt(br.readLine());

        // 2) 정수를 N개만큼 입력한다.
        String[] cardsNum = br.readLine().split(" ");


        // N개만큼 정수를 해시 배열에 추가(반복문) [형변환 필요]
        for (int i = 0; i < n; i++) {
            int value = Integer.parseInt(cardsNum[i]);
            myCards.add(value);
        }

        // 숫자 M을 입력 받는다.
        int m = Integer.parseInt(br.readLine());

        // 3) 포함여부 확인할 숫자를 M개 만큼 입력한다.
        String[] targets = br.readLine().split(" ");


        // - M개만큼 정수를 배열에 추가(반복문) (형변환 필요)
        for (int i = 0; i < m; i++) {
            int target = Integer.parseInt(targets[i]);

            // 해시 셋 배열에 [배열B]에 있는 정수들을 M개만큼 포함여부 확인
            // 5. M개 만큼 있으면 1, 없으면 0이 출력된다.(조건문)
            if (myCards.contains(target)) {
                sb.append(1).append(" ");
            } else {
                sb.append(0).append(" ");
            }
        }
        //스트링빌더로 한번에 출력 
        System.out.println(sb);
    }
}

문제(해시 맵)

생략..

입력

첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 물어봐도 괜찮아. 나는 언제든지 질문에 답해줄 준비가 되어있어.

둘째 줄부터 N개의 줄에 포켓몬의 번호가 1번인 포켓몬부터 N번에 해당하는 포켓몬까지 한 줄에 하나씩 입력으로 들어와. 포켓몬의 이름은 모두 영어로만 이루어져있고, 또, 음... 첫 글자만 대문자이고, 나머지 문자는 소문자로만 이루어져 있어. 아참! 일부 포켓몬은 마지막 문자만 대문자일 수도 있어. 포켓몬 이름의 최대 길이는 20, 최소 길이는 2야. 그 다음 줄부터 총 M개의 줄에 내가 맞춰야하는 문제가 입력으로 들어와. 문제가 알파벳으로만 들어오면 포켓몬 번호를 말해야 하고, 숫자로만 들어오면, 포켓몬 번호에 해당하는 문자를 출력해야해. 입력으로 들어오는 숫자는 반드시 1보다 크거나 같고, N보다 작거나 같고, 입력으로 들어오는 문자는 반드시 도감에 있는 포켓몬의 이름만 주어져. 그럼 화이팅!!!

출력

첫째 줄부터 차례대로 M개의 줄에 각각의 문제에 대한 답을 말해줬으면 좋겠어!!!. 입력으로 숫자가 들어왔다면 그 숫자에 해당하는 포켓몬의 이름을, 문자가 들어왔으면 그 포켓몬의 이름에 해당하는 번호를 출력하면 돼. 그럼 땡큐~

입력 예제1
26 5
Bulbasaur
Ivysaur
Venusaur
Charmander
Charmeleon
Charizard
Squirtle
Wartortle
Blastoise
Caterpie
Metapod
Butterfree
Weedle
Kakuna
Beedrill
Pidgey
Pidgeotto
Pidgeot
Rattata
Raticate
Spearow
Fearow
Ekans
Arbok
Pikachu
Raichu
25
Raichu
3
Pidgey
Kakuna

출력 예제1
Pikachu
26
Venusaur
16
14

문제 이해

포켓몬의 갯수N, 문제의 갯수M
입력값이 문자와, 숫자 두가지
숫자를 입력하면 포켓몬이, 포켓몬을 입력하면 포켓몬 번호가 출력
출력값은 M과 동일한 갯수

필요 지식

HashMep

Map은 키(Key)와 값(Value)을 한 쌍으로 저장해놓고, 키를 이용해서 값을 빠르게 찾는 자료구조이다.

Key → Value 형태로 저장한다

Key는 중복될 수 없다

Key로 값을 빠르게 찾을 수 있다

왜 빠른가?

특정 키 값의 위치를 계산해 바로 접근
리스트처럼 처음부터 끝까지 검색하지 않는다는 것.

어떤 상황에서 쓰면 좋은가?

두 가지 방향으로 검색해야 하는 문제
빠른 검색이 중요한 경우

사용법 요약

선언법

Map<"키 타입", "값 타입"> map = new HashMap<>();

put(key, value) : 저장
get(key) : 가져오기
containsKey(key) : 존재 여부
remove(key) : 삭제
size() : 저장 개수
keySet() : 전체 key 반복

다른 배열 메서드와 비슷하다.

Character.isDigit()

괄호 안에 들어가는 문자가 숫자인지 검사하는 함수
숫자면 true, 문자면 false
쓴 이유는 문자면 문자밖에 없고, 숫자면 숫자밖에 없기 때문에 채택

풀어보기

구상

1. 총 포켓몬 개수 N, 질문 개수 M
2. 찾기 위한 Map 준비
3. N개의 포켓몬 정보 입력
4. M개의 질문 처리
5. M개의 질문 이름 또는 숫자 출력

필요코드

버퍼리더
해쉬맵 생성
입력값 출력을 위한 스트링빌더
반복문, 조건문
sout

- 버퍼리더
- 해쉬셋 생성
- 스트링빌더

1. 총 포켓몬 개수 N, 질문 개수 M

2. 두 방향으로 찾기 위한 Map 준비

- 번호 -> 이름
- 이름 -> 번호

3. N개의 포켓몬 정보 입력(반복문)

- 번호 -> 이름
- 이름 -> 번호

4. M개의 질문 처리(반복문)
- M개만큼 질문 입력
- 숫자인지 이름인지 구분(조건문)

5. M개의 질문 이름 또는 숫자 출력
- 스트링빌더로 한번에 출력

코드작성

package Sutdy;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Beak1620_HashMap {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        // 1. 총 포켓몬 개수 N, 질문 개수 M
        String[] firstLine = br.readLine().split(" ");
        int n = Integer.parseInt(firstLine[0]);
        int m = Integer.parseInt(firstLine[1]);

        // 2. 두 방향으로 찾기 위한 Map 준비
        Map<Integer, String> findMon = new HashMap<>(); // 번호 -> 이름
        Map<String, Integer> findNum = new HashMap<>(); // 이름 -> 번호

        // 3. N개의 포켓몬 정보 입력
        //    i는 번호 그 자체가 됨 (1부터 시작)
        for (int i = 1; i <= n; i++) {
            String name = br.readLine();
            findMon.put(i, name);   // 번호로 이름 찾기
            findNum.put(name, i);   // 이름으로 번호 찾기
        }


        // 4. M개의 질문 처리
        for (int i = 0; i < m; i++) {
            String question = br.readLine();

            // Character.isDigit()로 첫글자 판단
            if (Character.isDigit(question.charAt(0))) {
                // 숫자면 문자열을 int로 바꿔서 이름 조회
                int number = Integer.parseInt(question);
                sb.append(findMon.get(number)).append("\n");
            } else {
                // 이름이면 번호 조회
                sb.append(findNum.get(question)).append("\n");
            }
        }
        // 5. M개의 질문 이름 또는 숫자 출력
        System.out.print(sb);
    }
}

Map을 두개나 쓴 이유

Map 하나만으로는 양방향(키→값, 값→키) 조회가 불가능했다.
Map은 오직 Key → Value 방향만 지원한다
Map 구조가 원래 단방향

Map 내부 저장 방식은 해시 테이블이기 때문에
key 기준으로만 빠르게 찾을 수 있게 만들어져 있다.

value는 그냥 “데이터”일 뿐이고
value로 직접 검색할 수 있도록 인덱스가 만들어져 있지 않다.

제이 용

메롱

다음 포스트

해시 셋, 맵 문제 풀어보기(스터디)

알고리즘 풀기(스터디)

문제(해시 셋)

입력

출력

문제 이해

필요 지식

HashSet

왜 빠른가?

어떤 상황에서 쓰면 좋은가?

사용법 요약

풀어보기

구상

필요코드

코드작성

문제(해시 맵)

입력

출력

문제 이해

필요 지식

HashMep

왜 빠른가?

어떤 상황에서 쓰면 좋은가?

사용법 요약

Character.isDigit()

풀어보기

구상

필요코드

코드작성

Map을 두개나 쓴 이유

백준 14916, 1092번(스터디)

0개의 댓글