[Java] 1919번. 애너그램 만들기

문제 링크 

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

---

*최종 코드는 1차 코드가 아닌 아래쪽 최종 코드를 참고해주시기 바랍니다.

 

문제 분석

이 문제는 쉽게 말하자면 각 문자열이 겹치지 않는 알파벳의 개수를 묻는 것이다.

aabbcc와 bbxxyy에서 bb를 제외한 나머지는 모두 겹치지 않기 때문에

애너그램을 만들기 위해서는 bb를 제외한, aa,cc,xx,yy를 제거해야 한다.

 

내가 생각한 방식은 다음과 같다.

1. 두개의 문자열을 입력받는다.

2. 앞 문자열을 순회하면서 알파벳 배열에 해당하는 알파벳을 +한다.

3. 뒷 문자열을 순회하면서 알파벳 배열에 해당하는 알파벳을 -한다.

이렇게 하면 두개의 배열을 만들 필요 없이 26 크기를 가진 배열 하나로 계산이 가능하다.

 

그리고 마지막으로 배열의 각 요소를 절대값을 해서 더하면

애너그램을 만들기 위해서 빼야하는 문자의 개수를 구할 수 있다.

 

여기서 하나의 생각이 떠올랐다.

위 코드를 보면 배열에 저장하기 위해

앞 문자열의 길이(n)만큼 반복하고

뒷 문자열의 길이(m)만큼 반복하고

result를 구하기 위해 26만큼의 반복을 한다.

 

여기서 반복을 조금 줄일 수 있는 방법은 없을까?

바로 짧은 문자열의 길이만큼은 +와 -를 동시에 실행하고

남은 문자열 길이만큼만 더 실행해주면

 

n+m+26만큼의 반복에서

m이 더 긴문자열이라고 가정했을 때,

m+26만큼의 반복으로 줄일 수 있었다.

 

반복하는 횟수는 줄일 수 있지만, 실제로 연산의 횟수는 줄어들지 않는다.

하지만, 반복문을 줄이고 두 문자열을 동시에 처리하면

CPU의 캐시 메모리를 더 효율적으로 사용할 수 있고, CPU 캐시 미스를 줄일 수 있다.

 

또한, CPU가 반복문을 최적화하여 루프 언롤링과 같은 최적화 기법이 더 효과적으로 적용 될 수 있다.

 

이 둘을 모두 구현해보도록 하겠다.

 

 

---

1차 코드(앞, 뒤 문자열 따로 저장)

import java.io.*;

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

        String str1 = reader.readLine();
        String str2 = reader.readLine();

        int arr[] = new int[26];

        for(int i=0; i<str1.length();i++){
            arr[str1.charAt(i)-'a']++;
        }
        for(int i=0; i<str2.length();i++){
            arr[str2.charAt(i)-'a']--;
        }

        int result=0;
        for(int i=0; i<arr.length; i++){
            result += Math.abs(arr[i]);
        }

        writer.write(String.valueOf(result));
        writer.flush();
        reader.close();
        writer.close();
    }
}

 

---

2차 코드(짧은 문자열까지 함께 저장)

import java.io.*;

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

        String str1 = reader.readLine();
        String str2 = reader.readLine();

        int arr[] = new int[26];

        int minLength = Math.min(str1.length(), str2.length());

        for (int i = 0; i < minLength; i++) {
            arr[str1.charAt(i) - 'a']++;
            arr[str2.charAt(i) - 'a']--;
        }

        for(int i=minLength; i<str1.length();i++) {
            arr[str1.charAt(i) - 'a']++;
        }

        for(int i=minLength; i<str2.length();i++) {
            arr[str2.charAt(i) - 'a']--;
        }

        int result = 0;
        for (int i = 0 ; i < arr.length; i++) {
            result += Math.abs(arr[i]);
        }

        writer.write(String.valueOf(result));
        writer.flush();
        reader.close();
        writer.close();
    }
}