[백준 30389] Suffix [Java]

문제

https://www.acmicpc.net/problem/30389

 

---

풀이

주어지는 N개의 문자열에 대해 모든 부분 접미사 집합을 구하고, 다음 문자열의 접미사 집합과 XOR연산을 하는 문제다.

우선 현재 문자열의 접미사를 구해주는 메서드를 만들자.

입력받은 문자열을 역순으로 한 칸씩 늘려가며 문자열을 결합해서 저장하면 된다.

    private static List<String> getSuffixes(String s) {
        StringBuilder sb = new StringBuilder();
        List<String> suffixes = new ArrayList<>();
        for (int i = s.length() -1; i >= 0; --i) {
            sb.append(s.charAt(i));
            suffixes.add(sb.toString());
        }
        return suffixes;
    }

부분 접미사들을 하나씩 기존 집합에 추가해주었다. 만약 요소 추가에 실패했다면 이미 기존 집합에 존재하는 접미사이기 때문에 제거해주는 방식으로 XOR 연산을 구현했다.

            // Solve
            for (String suffix : getSuffixes(br.readLine())) {
                if (!xorSet.add(suffix)) {
                    xorSet.remove(suffix);
                }
            }
        }

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/easy/30389.java