๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

[HashMap] 2. ์•„๋‚˜๊ทธ๋žจ

์‹œํ๋ฆฌํ‹ฐ์ง€ํ˜ธ 2023. 12. 31.
2. ์•„๋‚˜๊ทธ๋žจ(ํ•ด์‰ฌ)
 

์„ค๋ช…

Anagram์ด๋ž€ ๋‘ ๋ฌธ์ž์—ด์ด ์•ŒํŒŒ๋ฒณ์˜ ๋‚˜์—ด ์ˆœ์„œ๋ฅผ ๋‹ค๋ฅด์ง€๋งŒ ๊ทธ ๊ตฌ์„ฑ์ด ์ผ์น˜ํ•˜๋ฉด ๋‘ ๋‹จ์–ด๋Š” ์•„๋‚˜๊ทธ๋žจ์ด๋ผ๊ณ  ํ•ฉ๋‹ˆ๋‹ค.

์˜ˆ๋ฅผ ๋“ค๋ฉด AbaAeCe ์™€ baeeACA ๋Š” ์•ŒํŒŒ๋ฒณ์„ ๋‚˜์—ด ์ˆœ์„œ๋Š” ๋‹ค๋ฅด์ง€๋งŒ ๊ทธ ๊ตฌ์„ฑ์„ ์‚ดํŽด๋ณด๋ฉด A(2), a(1), b(1), C(1), e(2)๋กœ

์•ŒํŒŒ๋ฒณ๊ณผ ๊ทธ ๊ฐœ์ˆ˜๊ฐ€ ๋ชจ๋‘ ์ผ์น˜ํ•ฉ๋‹ˆ๋‹ค. ์ฆ‰ ์–ด๋А ํ•œ ๋‹จ์–ด๋ฅผ ์žฌ ๋ฐฐ์—ดํ•˜๋ฉด ์ƒ๋Œ€ํŽธ ๋‹จ์–ด๊ฐ€ ๋  ์ˆ˜ ์žˆ๋Š” ๊ฒƒ์„ ์•„๋‚˜๊ทธ๋žจ์ด๋ผ ํ•ฉ๋‹ˆ๋‹ค.

๊ธธ์ด๊ฐ€ ๊ฐ™์€ ๋‘ ๊ฐœ์˜ ๋‹จ์–ด๊ฐ€ ์ฃผ์–ด์ง€๋ฉด ๋‘ ๋‹จ์–ด๊ฐ€ ์•„๋‚˜๊ทธ๋žจ์ธ์ง€ ํŒ๋ณ„ํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์„ธ์š”. ์•„๋‚˜๊ทธ๋žจ ํŒ๋ณ„์‹œ ๋Œ€์†Œ๋ฌธ์ž๊ฐ€ ๊ตฌ๋ถ„๋ฉ๋‹ˆ๋‹ค.

์ž…๋ ฅ

์ฒซ ์ค„์— ์ฒซ ๋ฒˆ์งธ ๋‹จ์–ด๊ฐ€ ์ž…๋ ฅ๋˜๊ณ , ๋‘ ๋ฒˆ์งธ ์ค„์— ๋‘ ๋ฒˆ์งธ ๋‹จ์–ด๊ฐ€ ์ž…๋ ฅ๋ฉ๋‹ˆ๋‹ค.

๋‹จ์–ด์˜ ๊ธธ์ด๋Š” 100์„ ๋„˜์ง€ ์•Š์Šต๋‹ˆ๋‹ค.

์ถœ๋ ฅ

๋‘ ๋‹จ์–ด๊ฐ€ ์•„๋‚˜๊ทธ๋žจ์ด๋ฉด “YES"๋ฅผ ์ถœ๋ ฅํ•˜๊ณ , ์•„๋‹ˆ๋ฉด ”NO"๋ฅผ ์ถœ๋ ฅํ•ฉ๋‹ˆ๋‹ค.

์˜ˆ์‹œ ์ž…๋ ฅ 1 

AbaAeCe
baeeACA

์˜ˆ์‹œ ์ถœ๋ ฅ 1

YES

์˜ˆ์‹œ ์ž…๋ ฅ 2 

abaCC
Caaab

์˜ˆ์‹œ ์ถœ๋ ฅ 2

NO

 

 

<<ํ’€์ด>>

 

-๋‚˜์˜ ํ’€์ด-

 

์‹œ๊ฐ„ ๋ณต์žก๋„ : O(N)

 

์ผ๋‹จ ใ…‹ใ…‹ ๋‚˜์˜ ํ’€์ด๋Š” ํฌ๊ฒŒ ์ด์ƒ์ด ์—†์–ด๋ณด์ธ๋‹ค๋งŒ,,  ์ •๋‹ต์ด ํ‹€๋ ธ๋‹ค!!

์–ด๋””์„œ ์˜ค๋ฅ˜๊ฐ€ ๋‚˜๋Š” ๊ฒƒ์ผ๊นŒ ... 

import java.util.*;

class Main {
    public String solution(String a, String b) {
        HashMap<Character, Integer> map1 = new HashMap<>();
        HashMap<Character, Integer> map2 = new HashMap<>();
        String answer = "";

        for(char x : a.toCharArray()) {
            map1.put(x, map1.getOrDefault(x, 0) + 1);
        }

        for(char x : b.toCharArray()) {
            map2.put(x, map2.getOrDefault(x, 0) + 1);
        }

        for(char k : map1.keySet()) {
            if(!map2.containsKey(k)) answer = "NO";
            else {
                if(map1.get(k) != map2.get(k)) answer = "NO";
                else answer = "YES";
            }
        }

        return answer;
    }


    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        String a = in.next();
        String b = in.next();

        System.out.println(T.solution(a, b));
    }
}

 

์ด ํ’€์ด๋ฅผ ์กฐ๊ธˆ ์ˆ˜์ •ํ•ด๋ณธ ๊ฒฐ๊ณผ

 

import java.util.*;

class Main {
    public String solution(String a, String b) {
        HashMap<Character, Integer> map1 = new HashMap<>();
        HashMap<Character, Integer> map2 = new HashMap<>();
        String answer = "";
        if (a.length() != b.length()) {
            return "NO";
        }


        for(char x : a.toCharArray()) {
            map1.put(x, map1.getOrDefault(x, 0) + 1);
        }

        for(char x : b.toCharArray()) {
            map2.put(x, map2.getOrDefault(x, 0) + 1);
        }

        for(char k : map1.keySet()) {
            if(!map2.containsKey(k)) answer = "NO";
            else {
                if(map1.get(k) != map2.get(k)) {
                    answer = "NO";
                    break;
                }
                else answer = "YES";
            }
        }

        return answer;
    }


    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        String a = in.next();
        String b = in.next();

        System.out.println(T.solution(a, b));
    }
}

ใ…‹ใ…‹ใ…‹ใ…‹ ๋ฐ”๋กœ break๋ฅผ ์ถ”๊ฐ€ํ•˜๋‹ˆ ์ •๋‹ต์„ ๋งž์ท„๋‹ค ใ…‹ใ…‹ใ…‹ใ…‹ใ…‹

 

์•„์•„์•„ !!!!!!! ์ƒ๊ฐํ•ด๋ณด๋‹ˆ break๋ฅผ ์•ˆ ํ•˜๊ฒŒ ๋˜๋ฉด NO๊ฐ€ ๋˜๋”๋ผ๋„ ๋‹ค์‹œ ๋Œ์•„๊ฐ€์„œ ๋น„๊ตํ•˜๊ณ  key ๊ฐ’์˜ value๊ฐ€ ๊ฐ™์•„์ง€๋ฉด YES๋กœ ๋ฐ”๋€Œ๊ธฐ ๋•Œ๋ฌธ์—๋ฌธ์ œ๊ฐ€ ์ƒ๊ธฐ๋Š” ๊ฒƒ์ด๋‹ค ใ…‹ใ…‹ ใ… ใ… ใ… 

 

 

๊ทธ๋ฆฌ๊ณ  ๋˜ ๋‹ค๋ฅธ ํ’€์ด 

import java.util.*;

class Main {
    public String solution(String a, String b) {
        if (a.length() != b.length()) {
            return "NO"; // ๊ธธ์ด๊ฐ€ ๋‹ค๋ฅด๋ฉด ์•„๋‚˜๊ทธ๋žจ์ด ์•„๋‹˜
        }

        HashMap<Character, Integer> map1 = new HashMap<>();
        HashMap<Character, Integer> map2 = new HashMap<>();

        for(char x : a.toCharArray()) {
            map1.put(x, map1.getOrDefault(x, 0) + 1);
        }

        for(char x : b.toCharArray()) {
            map2.put(x, map2.getOrDefault(x, 0) + 1);
        }

        // map1๊ณผ map2๊ฐ€ ๋™์ผํ•œ์ง€ ๊ฒ€์‚ฌ
        if (!map1.equals(map2)) {
            return "NO";
        }

        return "YES";
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        String a = in.next();
        String b = in.next();

        System.out.println(T.solution(a, b));
    }
}

 

๋‘๋‘ฅ!!! ใ…‹ใ…‹ใ…‹ใ…‹ ์ด๊ฒŒ ๋ญ๋žŒ ... equals๋ผ๋Š” ๋ฉ”์†Œ๋“œ๋ฅผ ์—ฌ๊ธฐ์„œ ์ด์šฉํ•  ์ˆ˜ ์žˆ๋‹ค๋‹ˆ !!!

์ด๋ ‡๊ฒŒ ๋˜๋ฉด ํ˜„์žฌ๊นŒ์ง€ equals ๋ฉ”์„œ๋“œ๋ฅผ ์žฌ์ •์˜ ํ•ด์„œ ์‚ฌ์šฉํ•˜๊ณ  ์žˆ๋Š” ๊ฑด String๊ณผ HashMap์ด๋‹ค !!

 

์•„๋งˆ ๋” ์žˆ์„ ๊ฑฐ ๊ฐ™์€๋ฐ ํ•œ ๋ฒˆ ์ฐพ์•„๋ด์•ผ๊ฒ ๋‹ค. 

 

 

-๊ฐ•์‚ฌ๋‹˜ ํ’€์ด-

 

๊ฐ•์‚ฌ๋‹˜์€ ์•„๋‚˜๊ทธ๋žจ์„ ๋งํ•˜์‹œ๋Š”๋ฐ ๋˜ ๋‹ค๋ฅธ ๋ฐฉ์‹์œผ๋กœ ํ’€์—ˆ๋‹ค.

 

import java.util.*;

class Main {
    public String solution(String a, String b) {
        String answer = "YES";
        HashMap<Character, Integer> map = new HashMap<>();
        for(char x : a.toCharArray()) {
            map.put(x, map.getOrDefault(x, 0) + 1);
        }
        for(char x : b.toCharArray()) {
            if(!map.containsKey(x) || map.get(x) == 0) return  "NO";
            map.put(x, map.get(x) - 1);
        }
        return answer;
    }
    
    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        String a = in.next();
        String b = in.next();

        System.out.println(T.solution(a, b));
    }
}

 

์šฐ์„ , HashMap์„ ํ†ตํ•ด map์—๋‹ค๊ฐ€ ํ‚ค์™€ ๊ฐ’์„ ๋„ฃ์€ ๋’ค์—, ๋น„๊ต ๋Œ€์ƒ๊ณผ ๋น„๊ตํ•˜๋ฉด์„œ ๊ฐ’์— -1์„ ํ•œ๋‹ค.

๋งŒ์•ฝ ๋Œ์•„๊ฐ€๋Š” ์ค‘์— ํ‚ค๊ฐ’์ด ์—†๊ฑฐ๋‚˜ ์ด๋ฏธ ๊ฐ’์ด 0์ด๋ผ๋ฉด ๊ฐ™์€ ์ƒํ™ฉ์ด ์•„๋‹ˆ๊ธฐ ๋•Œ๋ฌธ์— return NO๋ฅผ ํ†ตํ•ด ๋น ์ ธ ๋‚˜์˜จ๋‹ค.

๊ทธ๋ƒฅ answer = "NO";๋ฅผ ํ•˜๋ ค๋ฉด ๊ฑฐ๊ธฐ์„œ ๋์ด ๋‚˜๊ฒŒ๋” break๋ฅผ ๊ฑธ์–ด์ค˜์•ผ ํ•œ๋‹ค!!!

 

์•„๋‹ˆ๋ฉด ๊ณ„์† ๋Œ์•„๊ฐ€๊ณ  ๋‹ค์Œ ์ฝ”๋“œ์—์„œ  map์— ํ‚ค ๊ฐ’์ด null ์ƒํƒœ์—์„œ get์„ ํ•˜๊ธฐ ๋•Œ๋ฌธ์— ๋Ÿฐํƒ€์ž„ ์—๋Ÿฌ๊ฐ€ ๋‚˜๊ฒŒ ๋œ๋‹ค.

 

return์˜ ์‚ฌ์šฉ๊ณผ break์˜ ์‚ฌ์šฉ์— ๋Œ€ํ•ด ๋‹ค์‹œ ํ•œ ๋ฒˆ ์ƒ๊ฐํ•ด๋ณด๋Š” ์ข‹์€ ๋ฌธ์ œ์˜€๋‹ค ใ…Žใ…Ž

 

<<์ถ”๊ฐ€ ๊ณต๋ถ€>>

 

return๋ฌธ : ๋ฉ”์„œ๋“œ ์ž์ฒด๋ฅผ ์ข…๋ฃŒ์‹œํ‚จ๋‹ค. ๋ฆฌํ„ด ๊ฐ’์ด void์ผ ๋•Œ ๊ทธ๋ƒฅ return; ์„ ํ•ด์„œ ๋ฉ”์„œ๋“œ๋ฅผ ์ข…๋ฃŒํ•  ์ˆ˜ ์žˆ๋‹ค. 

 

break๋ฌธ : ๋ฐ˜๋ณต๋ฌธ์—์„œ ํƒˆ์ถœ์„ ํ•  ๋•Œ ์ด์šฉํ•œ๋‹ค.

 

continue๋ฌธ : break๋ฌธ ์ฒ˜๋Ÿผ ์™„์ „ํžˆ loop์—์„œ ๋น ์ ธ๋‚˜๊ฐ€์ง€ ์•Š๊ณ  loop ์•ˆ์— ์žˆ๋Š” ๋’ค์˜ ์ฝ”๋“œ๋ฅผ ์ƒ๋žตํ•˜๊ณ  ๋‹ค์‹œ ๋ฐ˜ ๋ณต๋ฌธ์„ ๋Œ๋ฆฐ๋‹ค.

 

๋Œ“๊ธ€