[백준 | 1919] 애너그램 만들기 - Java

문제

두 영어 단어가 철자의 순서를 뒤바꾸어 같아질 수 있을 때, 그러한 두 단어를 서로 애너그램 관계에 있다고 한다. 예를 들면 occurs 라는 영어 단어와 succor 는 서로 애너그램 관계에 있는데, occurs의 각 문자들의 순서를 잘 바꾸면 succor이 되기 때문이다.

한 편, dared와 bread는 서로 애너그램 관계에 있지 않다. 하지만 dared에서 맨 앞의 d를 제거하고, bread에서 제일 앞의 b를 제거하면, ared와 read라는 서로 애너그램 관계에 있는 단어가 남게 된다.

두 개의 영어 단어가 주어졌을 때, 두 단어가 서로 애너그램 관계에 있도록 만들기 위해서 제거해야 하는 최소 개수의 문자 수를 구하는 프로그램을 작성하시오. 문자를 제거할 때에는 아무 위치에 있는 문자든지 제거할 수 있다.

 

입력

---

첫째 줄과 둘째 줄에 영어 단어가 소문자로 주어진다. 각각의 길이는 1,000자를 넘지 않으며, 적어도 한 글자로 이루어진 단어가 주어진다.

 

출력

---

첫째 줄에 답을 출력한다.

 

예제 입력

---

내 제출

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String A = br.readLine();
        String B = br.readLine();

        int[] count = new int[26];
        for (char ch : A.toCharArray()) {
            count[ch - 'a']++;
        }

        for (char ch : B.toCharArray()) {
            count[ch - 'a']--;
        }

        int answer = 0;
        for (int i : count) {
            answer += Math.abs(i);

        }

        bw.write(answer + "\n");
        br.close();
        bw.flush();
        bw.close();
    }
}

문제 해결 사고 과정

• 문제 이해: 주어진 두 단어를 애너그램 관계에 있도록 만들기 위해 제거해야 되는 최소 문자의 개수를 구하고 반환 하는 문제라고 이해 하였습니다. 애너그램은 두 단어가 동일한 문자들을 동일한 빈도로 포함하고 있어야 함을 의미합니다.
• 접근 방식: 두 단어의 각 문자의 등장 횟수를 저장하는 배열을 선언하여, 두 배열의 빈도 차이를 계산하는 방식으로 문제를 접근하였습니다.

자료 구조 선택 이유

• 선택한 자료 구조: 배열을 사용하여 문자의 등장 횟수를 저장하였습니다.
• 이유 및 장점: 배열 기반 접근은 메모리 사용이 효율적이며, 포인터를 이동시키는 방식으로 시간 복잡도를 줄일 수 있습니다.

테스트 케이스

• 테스트 케이스 1: 입력  : {"xxy", "xxx"} 출력 : 2 

시간 및 공간 복잡도 분석

• 시간 복잡도: 배열의 인덱스에 접근하는것은 `O(1)`의 시간 복잡도를 가지므로 전체 `O(1)` 입니다.
• 공간 복잡도: 데이터 구조의 크기가 입력의 크기에 상관없이 일정하므로, 공간 복잡도는 O(1) 입니다.