Java 알고리즘 모든 아나그램 찾기

오늘은 해쉬맵과 윈도우 미러링을 이용하여 주어진 단어 안에서 모든 아나그램을 찾는 문제를 풀어보려 합니다😄

 

DFS 부분집합

 

개요

문제 내용

 

문제 예시

 

이번 문제의 핵심은 저번 포스팅과 마찬가지로 해쉬맵을 사용하는 방법과 윈도우 미러링 방식을 사용하여 시간복잡도를 해결하는 것이 관건일 것 같네요😀

 

Setting📙

public class AllAnagram {
    public static void main(String[] args) {
        AllAnagram T = new AllAnagram();
        Scanner sc = new Scanner(System.in);
        String a = sc.next();
        String b = sc.next();
        System.out.println(T.solution(a,b));
    }
}

입력값으로는 두 단어가 주어집니다. 첫 번째로 들어오는 a 단어 안에서 두 번째로 들어오는 b 단어와 아나그램이 되는 부분 문자열의 개수를 구해야 하는 문제입니다. 세팅에서는 해당 두 단어를 solution 함수에 넘겨주는 역할을 합니다.

 

Solution📘

public class AllAnagram {
// main...
    public int solution(String a, String b) {
        int answer = 0;
        HashMap<Character, Integer> am = new HashMap<>();
        HashMap<Character, Integer> bm = new HashMap<>();

        for(char x : b.toCharArray()) {
            bm.put(x, bm.getOrDefault(x,0) + 1);
        }
        int L = b.length() - 1;
        for(int i = 0; i < L; ++i) {
            am.put(a.charAt(i), am.getOrDefault(a.charAt(i),0) + 1);
        }

        int lt = 0;
        for(int rt=L; rt < a.length(); ++rt) {
            am.put(a.charAt(rt), am.getOrDefault(a.charAt(rt), 0) + 1);
            if(am.equals(bm)) {
                answer++;
            }
            am.put(a.charAt(lt), am.get(a.charAt(lt)) -1);
            if(am.get(a.charAt(lt)) == 0) {
                am.remove(a.charAt(lt));
            }
            lt++;
        }
        return answer;
    }
}

첫 줄에 answer 변수는 아나그램이 되는 부분 문자열의 개수를 뜻하고 초기값으로 0을 세팅하였습니다. 이후에, 두 개의 해쉬맵을 선언합니다. 키 값으로는 알파벳을, 밸류 값으로는 개수이기 때문에 Integer로 선언하였습니다.

 

두 개를 선언하는 이유는 해쉬 맵에서 기본적으로 제공하는 equals 함수를 사용하여 부분 문자열이 아나그램인지 확인하기 위함입니다.

 

첫 번째로, 찾는 대상인 b의 단어를 forEach문을 이용하여 bm map에 담아줍니다. 여기서 toCharArray()는 Stiring을 char 배열로 만들어주는 방법입니다. 예시 문제로 b의 단어는 abc로 들어왔기 때문에, bm은 a:1, b:1, c:1의 형태로 구성됩니다.

 

이후에는 윈도우 미러링 방식을 사용하기 위해 초기 세팅을 진행합니다. 윈도우 미러링 방식은 거울을 한 칸씩 밀면서 가는 방식과 유사한데, 만약 예시와 같이 3글자의 단어를 찾는 경우면, 2글자를 미리 넣어놓고 오른쪽 출발점 rt와 왼쪽 출발점 lt를 둡니다.

 

출발점이 2개로 rt와 lt를 한 칸씩 이동하면서 로직을 구성하기 때문에, 시간복잡도 상 반복문을 한번만 돌면 된다는 이점이 있습니다.

 

본론으로 넘어와 b.length() - 1을 L이라는 변수에 담아주고, L 이전까지만 반복문을 돌면서 a의 단어를 am map에 담아줍니다. (L은 2이고 0부터 시작하기 때문에 0,1 즉 2개만 담습니다)

 

getOrDefault는 해당 map에서 없는 key라면 뒤의 인자인 0으로 세팅하고 +1을 해줍니다. 만약에 key가 있다면 해당 key의 value 값을 가져오고 +1을 해줍니다.

---

    int lt = 0;
    for(int rt=L; rt < a.length(); ++rt) {
      am.put(a.charAt(rt), am.getOrDefault(a.charAt(rt), 0) + 1);
      if(am.equals(bm)) {
         answer++;
      }
      am.put(a.charAt(lt), am.get(a.charAt(lt)) -1);
      if(am.get(a.charAt(lt)) == 0) {
         am.remove(a.charAt(lt));
      }
      lt++;
    }
return answer;

위에서 설명했듯이, rt를 한칸 이동하면서 lt가 뒤따라오는 형식으로 코드가 구성됩니다.

 

반복문을 이용하여 rt는 L부터 a 단어의 끝까지 이동하는데, 2개의 알파벳만 들어간 am에 다음 알파벳을 넣어주고, 이전에 만들어준 bm과 일치하는지 equals() 함수를 이용하여 비교합니다. 만약 일치하다면 answer 값을 증가시킵니다.

 

이후에 lt값을 하나 빼줍니다. 여기서 주의할 점은 만약 a 키 값의 벨류가 하나 빠져서 0으로 된다면 해당 키는 remove()를 이용하여 삭제해야 합니다. equals() 함수는 0의 벨류도 같은지 확인하기 때문에 꼭 빼주셔야 합니다.

 

이후에 lt를 증가시키면 로직은 끝이 납니다😊

 

Result📗

테스트 결과

 

---

👨‍👩‍👦‍👦 오픈채팅방 운영

취업을 준비하는 예비 개발자분들을 위한 질문&답변할 수 있는 공간을 만들었습니다. 취업과 이직을 하기 위해서 어떤 걸 중점적으로 준비해야 하는지부터 포트폴리오&이력서 작성법 등 다양한 질문들을 받고 답변을 드립니다. 참여하셔서 다양한 정보 얻고 가시면 좋을 것 같네요😁

 

참여코드 : 456456

https://open.kakao.com/o/gVHZP8dg

비전공 개발자 취업 준비방(질문&답변)

 

---

👨‍💻 전자책 출간

아울러 제가  🌟비전공자에서 2년만에 보안 전문 중견기업으로 이직 한 방법들을 정리한 전자책을 출간 하게 되었습니다. 어떤 걸 공부해야 하는지, 이직을 위해서 무엇을 준비해야 하는지, 제가 받았던 기술 면접 리스트 등 다양한 목차로 구성되어 있습니다. 또한, 구매 시 1:1 채팅을 이용하여 포트폴리오 첨삭을 도와드리고 있습니다. 🐕전자책으로 얻은 모든 수익은 유기견 센터 '팅*벨 입양센터'에 후원될 예정입니다. 관심 있으신 분들은 아래 링크를 참고해주세요😁

https://kmong.com/gig/480954

비전공개발자 2년만에 중견기업 들어간 방법 | 14000원부터 시작 가능한 총 평점 0점의 전자책, 취

---

 

마치며

지금까지 모든 아나그램을 찾는 문제를 풀어보았습니다😊