[자바] 백준 6566 - 애너그램 그룹 (java)

 문제 : boj6566

---

 

필요 알고리즘 개념

• 해시를 사용한 집합과 맵
  
  • 해시를 잘 이해하고 있어야 풀 수 있는 문제이다.
• 정렬
  
  • 정렬 역시 잘 이해하고 있어야 풀 수 있는 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  상당히 복잡한 문제이다. 구현도 복잡하고 실수할 여지도 많으니 주의해서 풀어야 한다. 차근차근 로직을 정리하면서 구현을 해야 실수를 줄이면서 구현할 수 있다. 이정도 구현을 문제없이 짤 수 있는 정도면 사실 정렬이나 해시로 문제될 일은 잘 없을 것 같다. 개인적으론 실버급에서 이정도 구현력(?)이 필요한 경우를 못봤으므로, 골드 중하위급이라 생각된다.

 

 

1. 입력으로 들어온 문자열들에 대해 '같은 단어는 한 번만 출력'해야 한다. 반면에 그룹의 크기를 구할 때는 동일한 문자라도 세줘야 한다. 즉, 입력으로 "aaaa"가 5번 들어왔다면 출력은 "Group of size 5: aaaa ."와 같이 이루어져야 한다. 왜 이것부터 쓰냐면 난 이것때문에 엄청 틀렸다 ㅠㅠ 문제 예시에 동일한거 하나만 좀 넣어주지.. ㅂㄷㅂㄷ

  아무튼 난 이걸 처리하기 위해 별도로 InputString 이라는 클래스를 만들었다. 거기엔 String이 있고, 동일한 String이 들어온 횟수인 cnt가 있다. 

class InputString implements Comparable<InputString> {
    String s;
    int cnt;
    public InputString(String s) {
        this.s = s;
        this.cnt = 1;
    }

    @Override
    public int compareTo(InputString o) {
        return this.s.compareTo(o.s);
    }
}

 

 

 

2. 중요한 정렬 요소는, 우선 단어를 사전순으로 출력해야 한다는 점과 각 그룹별로 가장 사전순으로 앞서는 단어가 중요하다는 점이다. 이걸 위해 내 경우엔 우선 위에서 설명한 InputString을 입력받으면서 생성해두고, 일단 정렬한 후 이후 로직을 진행했다. 미리 입력값들을 중복처리하고, 정렬도 해뒀으므로 이후 로직이 비교적 간단해진다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
ArrayList<InputString> input = new ArrayList<>();
HashMap<String, InputString> dupChk = new HashMap<>();	// 동일한 문자 체크용도
while (true) {
    String cur = br.readLine();
    if (cur == null) break;	// EOF 까지 입력받는다.
    if (dupChk.containsKey(cur)) {	// 중복문자라면 cnt만 증가시킨다.
        dupChk.get(cur).cnt++;
        continue;
    }
    InputString tmp = new InputString(cur);
    dupChk.put(cur, tmp);
    input.add(tmp);
}
Collections.sort(input);	// 미리 입력된 문자를 사전순으로 정렬해둔다. 정렬은 InputString에 Comparable을 implements에서 정의했다.

 

 

3. 동일한 애너그램 그룹을 찾을 수 있어야 한다. 이건 해시를 재정의해서 동일한 애너그램 그룹을 찾을 수 있도록 정의해두면 이후 해시맵을 통해 찾을 수 있다. 내 경우엔 애너그램 그룹을 'Word'라는 클래스로 정의했다. 그리고 각 문자열에 대해 예를들어 "abccd"는 "a1b1c2d1e0f0...z0"과 같이 문자의 순서와 관계없이 동일한 애너그램을 찾을 수 있는 문자열로 변경을 해 동일한 애너그램 그룹임을 판단했다. int['z'-'a'+1] 형태의 배열로도 해시코드만 정의해주면 동일하게 동작 가능하다(이하 생성자 참고). 그리고 해시맵을 사용하기 위해 해시를 재정의해주고, 문제의 '그룹은 크기가 감소하는 순으로, 크기가 같을 때는 각 그룹에서 가장 사전 순으로 앞서는 단어의 사전 순으로 출력' 조건을 맞추기 위한 정렬 규칙도 재정의해준다.

class Word implements Comparable<Word> {
    private static final int LEN = 'z'-'a'+1;
    int[] cnt;
    ArrayList<InputString> list;
    int size = 0;
    String checker;

    public Word(InputString inputString) {
        String s = inputString.s;
        cnt = new int[LEN];
        for (int i = 0; i < s.length(); i++) {
            cnt[s.charAt(i)-'a']++;
        }
        StringBuilder tmp = new StringBuilder();
        for (int i = 0; i < LEN; i++) {
            tmp.append((char)(i+'a')).append(cnt[i]);
        }
        checker = tmp.toString();	// inputString이 "aabbc"라면 checker는 "a2b2c1d0...z0"
    }

    public void add(InputString inputString) {	// 해당 애너그램 그룹에 문자열 추가
        this.size += inputString.cnt;
        this.list.add(inputString);
    }

    @Override
    public int hashCode() {	// checker를 기준으로 해시코드를 재정의한다.
        return checker.hashCode();
    }

    @Override
    public boolean equals(Object obj) {	// 해시를 사용하기 위해선 equals도 재정의해야한다.
        return this.checker.equals(((Word)obj).checker);
    }

    @Override
    public int compareTo(Word o) {	// 정렬 기준이다. 그룹 사이즈 내림차순인데 그룹 사이즈가 동일하다면 첫 문자를 기준으로 오름차순 정렬한다.
        if (this.size == o.size)
            return this.list.get(0).s.compareTo(o.list.get(0).s);
        return o.size - this.size;
    }
}

 

 

4. 그럼 이제 '2' 에서 받아둔 InputString을 애너그램 그룹으로 변경하자.

HashMap<Word, Integer> hm = new HashMap<>();
ArrayList<Word> list = new ArrayList<>();
for (int i = 0; i < input.size(); i++) {	// input은 InputString 리스트이다. 즉 중복처리되고 정렬되어 있는 입력값들임.
    Word word = new Word(input.get(i));	// Word로 변경하면서 애너그램 checker를 생성한다.

    if (!hm.containsKey(word)) {	// 현재 존재하지 않는 애너그램 그룹일 경우
        word.list = new ArrayList<>();	// 현재 Word가 애너그램 그룹의 메인이 된다.
        word.add(input.get(i));	// 자기 자신을 자기 자신한테 추가한거다. 이 부분은 헷갈릴 수 있다.
        hm.put(word, list.size());	// list.size()는 애너그램 그룹의 idx 번호에 해당한다.
        list.add(word);	// 정렬 후 출력을 위해 list에 추가한다.
    } else {	// 현재 존재하는 애너그램 그룹일 경우
        Word rootWord = list.get(hm.get(word));	// 애너그램 그룹의 메인을 찾아서
        rootWord.add(input.get(i));	// 해당 애너그램 그룹에 현재 보고있는걸 추가한다.
    }
}

Collections.sort(list);	// '3'에서 재정의해둔 정렬 방식에 따라 정렬한다.

 

 

5. 이미 '2'에서 순서대로 정렬해두었고, '4'에서 정렬된 순서대로 InputString을 애너그램 그룹으로 만들었다. 그리고 '4'에서 애너그램 그룹 정렬도 끝났다. 따라서 이젠 뭐 신경쓸거 없이 list에서 최대 5개만큼 출력해주면 된다.

StringBuilder answer = new StringBuilder();
for (int i = 0; i < Math.min(5, list.size()); i++) {
    Word cur = list.get(i);
    answer.append(String.format("Group of size %d: ", cur.size));
    for (InputString inputString : cur.list) {
        answer.append(inputString.s).append(' ');
    }
    answer.append('.').append('\n');
}
System.out.print(answer);

 

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;

class Word implements Comparable<Word> {
    private static final int LEN = 'z'-'a'+1;
    int[] cnt;
    ArrayList<InputString> list;
    int size = 0;
    String checker;

    public Word(InputString inputString) {
        String s = inputString.s;
        cnt = new int[LEN];
        for (int i = 0; i < s.length(); i++) {
            cnt[s.charAt(i)-'a']++;
        }
        StringBuilder tmp = new StringBuilder();
        for (int i = 0; i < LEN; i++) {
            tmp.append((char)(i+'a')).append(cnt[i]);
        }
        checker = tmp.toString();
    }

    public void add(InputString inputString) {
        this.size += inputString.cnt;
        this.list.add(inputString);
    }

    @Override
    public int hashCode() {
        return checker.hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        return this.checker.equals(((Word)obj).checker);
    }

    @Override
    public int compareTo(Word o) {
        if (this.size == o.size)
            return this.list.get(0).s.compareTo(o.list.get(0).s);
        return o.size - this.size;
    }
}

class InputString implements Comparable<InputString> {
    String s;
    int cnt;
    public InputString(String s) {
        this.s = s;
        this.cnt = 1;
    }

    @Override
    public int compareTo(InputString o) {
        return this.s.compareTo(o.s);
    }
}

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ArrayList<InputString> input = new ArrayList<>();
        HashMap<String, InputString> dupChk = new HashMap<>();
        while (true) {
            String cur = br.readLine();
            if (cur == null || cur.isEmpty()) break;
            if (dupChk.containsKey(cur)) {
                dupChk.get(cur).cnt++;
                continue;
            }
            InputString tmp = new InputString(cur);
            dupChk.put(cur, tmp);
            input.add(tmp);
        }
        Collections.sort(input);

        HashMap<Word, Integer> hm = new HashMap<>();
        ArrayList<Word> list = new ArrayList<>();
        for (int i = 0; i < input.size(); i++) {
            Word word = new Word(input.get(i));

            if (!hm.containsKey(word)) {
                word.list = new ArrayList<>();
                word.add(input.get(i));
                hm.put(word, list.size());
                list.add(word);
            } else {
                Word rootWord = list.get(hm.get(word));
                rootWord.add(input.get(i));
            }
        }

        Collections.sort(list);
        StringBuilder answer = new StringBuilder();
        for (int i = 0; i < Math.min(5, list.size()); i++) {
            Word cur = list.get(i);
            answer.append(String.format("Group of size %d: ", cur.size));
            for (InputString inputString : cur.list) {
                answer.append(inputString.s).append(' ');
            }
            answer.append('.').append('\n');
        }
        System.out.print(answer);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}