https://hobbyatelier.tistory.com/94

이전 게시글에서는 Map 자료구조에 대해서 썼었다.

이번에는 Map 인터페이스를 구현한 대표적인 3가지 구현체에 대해 써보겠다.

1. 자바에서 제공하는 주요 Map 구현체들

1. HashMap
   • 가장 일반적으로 쓰이는 Map.
   • 키 순서를 보장하지 않음.
   • null 키와 null 값을 허용.
2. LinkedHashMap
   • HashMap의 확장.
   • 입력 순서를 유지함.
   • 순회 순서가 예측 가능.
3. TreeMap
   • 정렬된 Map.
   • 키의 자연 순서나 Comparator를 기준으로 정렬.
   • 성능은 HashMap보다 느리지만 정렬이 필요할 때 유용.

2. 자주 쓰는 Map 3종 비교

3.언제 어떤 걸 써야 할까?

• HashMap
  → 기본 Map으로 거의 모든 경우에 사용 가능. 성능도 좋고 가장 많이 쓰임.
  → 단, 순서에 대한 보장이 전혀 없다는 걸 기억.
• LinkedHashMap
  → 반복 순서가 중요할 때 (예: 캐시 구현, 최근 입력 순서대로 출력 등).
  → 입력 순서를 그대로 유지하므로 디버깅할 때도 보기 편함.
• TreeMap
  → 키를 정렬된 상태로 유지해야 할 때.
  → ex) 사전식 정렬, 범위 검색 (subMap, tailMap 등) 기능이 유용함.

4. Map의 대표적인 3가지 구현체 사용법

HashMap, LinkedHashMap, TreeMap은 모두 Map 인터페이스를 구현하고 있어서 기본적인 함수들은 거의 동일함.

하지만 TreeMap은 정렬과 탐색 관련된 기능이 추가로 좀 더 있고, LinkedHashMap은 순서 유지와 관련된 특징이 있다.

5. 공통적으로 제공되는 주요 Map 인터페이스 메서드

(HashMap, LinkedHashMap, TreeMap 모두 사용 가능)

메서드 설명

6. LinkedHashMap 특유의 메서드

메서드 설명

7. TreeMap 특유의 메서드

(NavigableMap, SortedMap 인터페이스도 구현함)

메서드 설명

8. 구현 예시 :

1) HashMap 

Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);
System.out.println(map.get("apple"));  // 1
System.out.println(map.containsKey("banana"));  // true

2) TreeMap

TreeMap<String, Integer> treeMap = new TreeMap<>();
treeMap.put("c", 3);
treeMap.put("a", 1);
treeMap.put("b", 2);
System.out.println(treeMap.firstKey());  // a가 순서상 가장 앞임 a,b,c ...
System.out.println(treeMap.subMap("a", "c"));  // {a=1, b=2}

3) LinkedHashMap

 - 입력 순서 유지

import java.util.LinkedHashMap;
import java.util.Map;

public class LinkedHashMapExample {
    public static void main(String[] args) {
        Map<String, Integer> linkedMap = new LinkedHashMap<>();

        linkedMap.put("apple", 10);
        linkedMap.put("banana", 20);
        linkedMap.put("cherry", 30);

        for (Map.Entry<String, Integer> entry : linkedMap.entrySet()) {
            System.out.println(entry.getKey() + " = " + entry.getValue());
        }
    }
}


// 출력 결과 
apple = 10
banana = 20
cherry = 30

- 접근 순서 유지

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUExample {
    public static void main(String[] args) {
        // accessOrder = true → 최근 사용된 순서대로 정렬
        Map<String, String> lruMap = new LinkedHashMap<>(16, 0.75f, true);

        lruMap.put("A", "Apple");
        lruMap.put("B", "Banana");
        lruMap.put("C", "Cherry");

        // "A"에 접근
        lruMap.get("A");

        for (Map.Entry<String, String> entry : lruMap.entrySet()) {
            System.out.println(entry.getKey() + " = " + entry.getValue());
        }
    }
}

// 출력 결과
B = Banana
C = Cherry
A = Apple  // A에 접근했기 때문에 가장 마지막에 출력됨.

Map은 키-값(key-value) 쌍으로 데이터를 저장하는 자료구조입니다. 간단히 말하면, 특정 키를 이용해 원하는 값을 빠르게 찾을 수 있게 해주는 구조이다.

1. 기본 개념

• 인터페이스 이름: java.util.Map
• 대표적인 구현체:
  • HashMap (가장 많이 사용됨)
  • TreeMap (정렬된 순서 유지)
  • LinkedHashMap (입력 순서 유지)
  • ConcurrentHashMap (동시성 지원)

2. 주요 특징

• Key는 중복될 수 없음 (Set처럼 유일해야 함)
• Value는 중복 가능
• 빠른 검색, 삽입, 삭제를 위해 주로 사용

3. 사용 예시 (HashMap 기준)

import java.util.HashMap;
import java.util.Map;

public class MapExample {
    public static void main(String[] args) {
        Map<String, Integer> scoreMap = new HashMap<>();

        // 값 추가
        scoreMap.put("Alice", 90);
        scoreMap.put("Bob", 85);
        scoreMap.put("Charlie", 95);

        // 값 가져오기
        System.out.println(scoreMap.get("Alice")); // 90

        // 값 수정
        scoreMap.put("Bob", 88);

        // 키 존재 여부 확인
        System.out.println(scoreMap.containsKey("Charlie")); // true

        // 전체 순회
        for (String key : scoreMap.keySet()) {
            System.out.println(key + ": " + scoreMap.get(key));
        }

        // 제거
        scoreMap.remove("Alice");
    }
}

4. 메서드 요약

메서드 설명

문제 :

문자열 s가 '(', ')', '{', '}', '[', ']' 문자만 포함하고 있을 때, 이 문자열이 유효한지 판단하세요.

문자열이 유효하려면 다음 조건을 모두 만족해야 합니다:

• 열린 괄호는 동일한 종류의 닫는 괄호로 닫혀야 합니다.
• 열린 괄호는 올바른 순서로 닫혀야 합니다.
• 모든 닫는 괄호는 대응되는 동일한 종류의 열린 괄호를 가져야 합니다.

예시:

예시 1:

입력: s = "()"
출력: true

예시 2:

입력: s = "()[]{}"
출력: true

예시 3:

입력: s = "(]"
출력: false

예시 4:

입력: s = "([])"
출력: true

제약 사항:

• 1 ≤ s.length ≤ 10⁴
• s는 오직 괄호 문자 '()[]{}' 로만 구성됩니다.

구현 :

이 문제의 힌트를 보았을 때,

1. 문자 스택을 쓰고

2. (, {, [ 등 열린 괄호를 만나면 스택에 넣고

3. ), }, ] 닫힌 괄호를 만나면 스택에서 매칭되는 열린괄호가 있으면 pop하라고 했다.

class Solution {
    public boolean isValid(String s) {
		// 스택 준비
        Stack<Character> stack = new Stack<>();
        // 매칭되는 괄호를 찾기 위해 HashMap 준비
        Map<Character, Character> mapping = new HashMap<>();
        mapping.put(')', '(');
        mapping.put('}', '{');
        mapping.put(']', '[');
		
        // String s를 문자 배열로 전환하여 하나씩 
        for (char c : s.toCharArray()) {
        	// 열린 괄호가 들어오면 stack에 푸시
            if (mapping.containsValue(c)) {
                stack.push(c);
            // 닫힌 괄호가 들어오면 실행
            } else if (mapping.containsKey(c)) {
            	// 스택이 비어 있거나 가장 마지막에 들어온 값을 pop해서 비교
                if (stack.isEmpty() || mapping.get(c) != stack.pop()) {
                	// 매칭되는 괄호가 아니면 false 리턴
                    return false;
                }
            }
        }

        return stack.isEmpty();  

    }
}

문제 :

N(1<= N <= 100,000,000,000)가 주어졌을때,

1,2,3,4,...N까지 binary값을 구해서

그 binary값이 팰린드롬인 수의 핪을 구하라.

테스트케이스 :

입력 : 1

출력 : 1

1은

바이너리 값이 1이므로 팰린드롬

입력 : 3

출력 : 4

3은

1 의 바이너리 값이 1 이므로 팰린드롬 O

2 의 바이너리 값은 10 이므로 팰린드롬 X
3 의 바이너리 값은 11 이므로 팰린드롬 O

1과 3의 합은 4

입력 : 5

출력 : 25

1 = 1                                        O

2 = 10                                      X                             

3 = 11                                      O

4 = 100                                     X

5 = 101                                     O

6 = 110                                       X

7 = 111                                       O

8 = 1000                                     X

9 = 1001                                     O

풀이 :

import java.util.Random;

public class LongBinary {
    public static void main(String[] args) {
        long start = System.nanoTime();
        Random random = new Random();
        // 1~100,000,000,000
        long n = random.longs(1,100000000000).findFirst().getAsLong();
        System.out.println(n);
        long sum = 0;
        
        for(long i=1; i<=n; i++){
        // 1부터 N까지 순차적으로 
            System.out.println("1. check this number : " +i);
            if(checkPalindrome(i)){
            //팰린드롬이면 더하기
                sum += i;
            } else {
                continue;
            }
        }
        long end = System.nanoTime();
        System.out.println("실행시간 : " + (end-start)/1000000 + "ms");
        System.out.println(sum);
    }

    private static boolean checkPalindrome(long i) {
    // 전달 받은 i의 값을 binary 문자열로 변환
        String binary = Long.toBinaryString(i);
        System.out.println("2. this is binary : "+binary);
        
        int left =0, right = binary.length()-1;
        // 좌측과 우측의 값을 비교해서 다르면 false
        // 같으면 true;
        while(left<right){
            if(binary.charAt(left) != binary.charAt(right)){
                return false;
            }
            left++;
            right--;
        }
        System.out.println("("+i+") is palindrome!!!");
        return true;
    }
}

문제 :

1~X까지의 거듭제곱 수열이 있고,

이 거듭제곱 수열이

1,4,8,9,16 .... 각 제곱의 크기만큼 나열 되어있다.

N(1<= N <= 1000) 이란 수가 주어졌을 때

N번째 거듭제곱이 무엇인지 구하라

테스트케이스 :

입력 : 1

출력 : 1

입력 : 3

출력 : 8

입력 : 5

출력 : 16

import java.util.*;

public class FindPower { 
    public static void main(String[] args) {
        long start = System.nanoTime();
        Random random = new Random();
        int n = random.nextInt(10000)+1; // 1부터 10,000까지 랜덤한 수
        System.out.println(n);
        long sum = 0;
        
        // 중복 없이 순서대로 저장할 수 있는 TreeSet
        TreeSet<Integer> ts = new TreeSet<Integer>();

        for(int i=1; i<=n; i++){
            for(int j=2; j<=n; j++){
                double a = (double)Math.pow(i,j);
                ts.add((int) a);
            }
        }
        
        // TreeSet을 리스트로 바꿔서 N번째 인덱스 출력 준비
        
        List<Integer> sorted = new ArrayList<>(ts);
        long end= System.nanoTime();
        System.out.println("실행 시간: " + (end - start)/1000000 + "ms");
        
        // 인덱스는 0부터 시작이므로 N-1
        System.out.println(sorted.get(n-1));
    }
}

4 3

7

3 4

-7

우선 문제 자체는 쉬운 편이다. 

두 정수를 A 와 B를 입력 받은 후 (A+B) * (A-B)를 출력하면 되는 부분이다.

정수 A,B는 ( 1 ≤ A, B ≤ 100,000)다.

처음에 제약 조건을 잘 못 보고 풀어서 30점만 맞았었는데

나는 이게 제한시간 2초에 걸려서 그런건가? 하면서 열심히 똥꼬쇼를 했다... -_-

그냥 int를 long으로 바꿔 int로는 감당할 수 없는 출력값을 계산할 수 있도록하면 되는거였다.

import java.io.*;
public class WeirdOperator {
    public static void main(String[] args) throws IOException{
    	// 입출력 준비
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        // 정수 A,B 준비
        String[] str = bf.readLine().split(" ");
        // (A + B) × (A - B) 를 해준다.
        long k = (Long.parseLong(str[0])+Long.parseLong(str[1]))
        		* (Long.parseLong(str[0])-Long.parseLong(str[1]));
        // 출력
        bw.write(String.valueOf(k));
        bw.flush();
        bw.close();
    }
}