[Java]자바 HashMap 문제 풀면서 HashMap 이해력 높이기 1편

1. 매우 큰 범위의 배열이 필요할때

 

서로 다른 6개의 숫자가 주어진 뒤 끝에 숫자 k가 주어졌을 때, 숫자 k가 몇 번째로 주어졌는지를 판단하는 프로그램을 작성해보세요. 단, 주어지는 숫자의 범위는 -10^9 ~ 10^9 사이입니다. 예를 들어 [-656, 234, 65756344, 7678678, 123123, 567567567] 에서 k가 65756344라면, 3번째로 주어진 숫자이므로 답은 3이 됩니다.

 

이런 경우 -10^9에서 10^9을 모두 담는 배열을 선언하기에는 메모리가 부족하다

 

하지만 필요한 숫자는 6개밖에 안된다.

 

그래서 이럴때 필요한 자료구조가 HashMap

 

HashMap은 (key,value)형태로 데이터를 저장하며, key의 범위는 정의하기 나름이고,

 

사용되는 메모리 공간이 전체 숫자 범위와는 무관하게 실제 들어간 데이터의 수에만 비례한다.

 

import java.util.Scanner;
import java.util.HashMap;

public class Main {
    
    public static final int MAX_N = 6;
    
    public static int[] arr = new int[MAX_N];
    public static HashMap<Integer, Integer> numToIndex = new HashMap<>();
    
    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        for(int i = 0; i < n; i++){
            
            arr[i] = sc.nextInt();
            numToIndex.put(arr[i], i + 1);
        
        }
        
        int k = sc.nextInt();
        System.out.println(numToIndex.get(k));
    }
}

>>
입력
6
-656 234 65756344 7678678 123123 567567567
65756344

출력
3

 

 

2. 연습문제

 

n개의 숫자로 이루어진 수열 정보가 하나 주어졌을 때, m번에 걸쳐 특정 숫자가 주어지면 해당 숫자가 수열에 몇 개 있는지를 출력하는 프로그램을 작성해보세요.

 

수열의 수를 넣을려고 할때 hashmap에서 containsKey를 이용해 key가 들어가있다면, count에 1을 더해주고

 

key가 없다면 처음으로 hashmap에 들어가므로 count = 1로 해서 넣어준다.

 

그리고 마지막에 m개의 쿼리에 답할때, 없는 숫자가 나올수도 있으므로 containsKey를 이용해 없다면 0을 출력

 

있으면 get()으로 count를 구한 value값을 출력

 

import java.util.Scanner;
import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        // 여기에 코드를 작성해주세요.

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        HashMap<Integer,Integer> hash = new HashMap<>();

        for(int i = 0; i < n; i++){

            int x = sc.nextInt();

            if(hash.containsKey(x) == true){
                
                int c = hash.get(x);
                c += 1;
                hash.put(x,c);
            } else {
                hash.put(x,1);
            }
        }

        for(int j = 0; j < m; j++){

            int x = sc.nextInt();

            if (hash.containsKey(x) == false){
                System.out.print(0 + " ");
            } else {
            System.out.print(hash.get(x) + " ");
            }
        }
    }
}

 

 

3. 문자열을 index처럼

 

서로 다른 6개의 문자열이 주어진 뒤 끝에 문자열 K가 주어졌을 때, 문자열 K가 몇 번째로 주어졌는지를 판단하는 프로그램을 작성해보세요. 예를 들어 ["aba", "banana", "apple", "code", "tree", "foo"] 에서 K가 "banana"라면, 2번째로 주어진 문자열이므로 답은 2가 됩니다.

 

 

문자열을 key로 하고 해당 문자열이 몇번째 나왔는지를 value로 하는 HashMap을 구성하면

 

O(1)에 원하는 문자열이 몇번째 나왔는지 해결가능

 

import java.util.Scanner;
import java.util.HashMap;

public class Main {
    public static final int MAX_N = 6;
    
    public static String[] arr = new String[MAX_N];
    public static HashMap<String, Integer> stringToIndex = new HashMap<>();
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        for(int i = 0; i < n; i++){
            arr[i] = sc.next();
            stringToIndex.put(arr[i], i+1);
        }
        
        String k = sc.next();
        System.out.println(stringToIndex.get(k));
    }
}

>>
입력
6
aba banana apple code tree foo
banana

출력
2

 

 

4. 연습문제

 

알파벳 소문자로 이루어진 문자열들이 중복을 허용하여 입력되었을때, 최대로 등장한 문자열의 등장 횟수를 출력하는 프로그램을 작성해보세요.

 

 

역시 문자열들을 key로 해당 문자열의 등장 횟수를 value로 해서 HashMap을 구성

 

문자열들을 HashMap에 넣을때마다 해당 문자열이 HashMap에 존재하는지 containsKey로 확인해보고

 

존재한다면, value에 1을 더한 상태로 put해주고 없다면, 새로 value = 1로 하고 put해주고

 

그리고 put을 해서 HashMap에 넣을때마다, max_count를 갱신해준다.

 

------------------------------------------------------------------------------------------------------------------------------------

 

공식 해설 풀이를 보면 Math.max(a,b)로 a,b중 최댓값을 구할 수 있다는 것도 체크

 

Math.min(a,b)은 최솟값일거고

 

import java.util.Scanner;
import java.util.HashMap;

public class Main {    
    public static final int MAX_N = 100000;
    
    // 변수 선언
    public static int n;
    public static String[] words = new String[MAX_N];
    public static HashMap<String, Integer> freq = new HashMap<>();
    
    public static int ans; // 가장 많이 나온 횟수를 기록합니다.

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 입력:
        n = sc.nextInt();

        for(int i = 0; i < n; i++)
            words[i] = sc.next();
        
        // 각 문자열이 몇 번씩 나왔는지를
        // hashmap에 기록해줍니다.
        for(int i = 0; i < n; i++) {
            // 처음 나온 문자열이라면 1을 직접 적어줘야 합니다.
            if(!freq.containsKey(words[i]))
                freq.put(words[i], 1);
            // 이미 나와있던 문자열이라면 1을 더해줍니다.
            else
                freq.put(words[i], freq.get(words[i]) + 1);
            
            // 최댓값을 갱신합니다.
            ans = Math.max(ans, freq.get(words[i]));
        }

        System.out.print(ans);
    }
}

 

 

5. 연습문제

 

n개의 문자열이 주어집니다. 각 문자열은 1부터 n까지 주어진 순서대로 각각 하나의 숫자와 대응됩니다.
이 후, 조사할 m개의 숫자 혹은 문자열이 주어졌을 때, 숫자에 대해서는 대응되는 문자열을, 문자열에 대해서는 대응되는 숫자를 출력하는 프로그램을 작성해보세요.

 

이 문제는 처음에 문자열이 주어지고, 쿼리에 대해서는 문자열 혹은 정수가 주어지는데...

 

자바에서는 타입을 지정해야 변수에 저장할 수 있는데..

 

정수가 나올지 문자열이 나올지 알수가 없는데 어떻게 해야할까

 

import java.util.Scanner;
import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        // 여기에 코드를 작성해주세요.
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        HashMap<String, Integer> h = new HashMap<>();
        HashMap<String, String> inverse_h = new HashMap<>();

        for(int i = 1; i < n+1; i++){
            String c = sc.next();

            h.put(c,i);
            inverse_h.put(String.valueOf(i),c);
            
        }

        for(int j = 0; j < m; j++){
            String c = sc.next();

            if(h.containsKey(c) == true){
                System.out.println(h.get(c));
            } else {
                System.out.println(inverse_h.get(c));
            }

        }
    }
}

 

 

일단 정수가 나오면 문자열을 내뱉는 HashMap이랑 문자열이 나오면 정수를 내뱉는 HashMap 2개가 있어야겠는데

 

하나의 HashMap으로는 조금 힘들다

 

지정된 type만 들어가다보니까

 

정수가 나올지 문자열이 나올지 상관없는게

 

sc.next();는 입력을 받으면 문자열로 반환해준다

 

정수를 입력해도 문자열로 반환해준다는 이야기

 

[자바JAVA] Scanner를 이용한 다양한 자료형 값 입력 받기 (tistory.com)

[자바JAVA] Scanner를 이용한 다양한 자료형 값 입력 받기

 

 

따라서 정수를 넣으면 문자열을 내뱉는 HashMap을 key값에 정수를 문자열로 바꿔서 저장해놓으면 될 것 같다

 

String.valueOf()하면 정수를 문자열로 바꿔준다

 

Java에서 정수를 문자열로 변환 (techiedelight.com)

Java에서 정수를 문자열로 변환