[Java]백준_1919 : 애너그램 만들기

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

 

 

 

 

 

문제 분석

입력받는 문자열을 각각 s1과 s2라고 하자.

s1과 s2의 겹치는 문자가 있다면, 그것들을 제외한 나머지 문자의 갯수만 세어주면 된다. 

 

 

 

소스 코드 (⭕)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

        char[] arr1 = br.readLine().toCharArray();
        char[] arr2 = br.readLine().toCharArray();

        int cnt = 0;
        for (int i = 0; i < arr1.length; i++) {
            for (int j = 0; j < arr2.length; j++) {
                if (arr1[i] == arr2[j]) {
                    arr2[j] = '@';
                    cnt++;
                    break;
                }
            }
        }
        System.out.println(arr1.length - cnt + arr2.length - cnt);
    }
}

 

코드 분석

1. 입력 받은 String 문자열을 char 형태로 바꾸어서 각 배열 arr1, arr2에 넣어준다.

 

2. 이중 반복문을 이용한 전체 탐색을 하여 arr1과 arr2의 동일한 문자는 몇 개인지 세어준다.

 

3. 겹치는 문자를 제외한 나머지 문자들은 전부 삭제해야 하므로, arr1-cnt와 arr2-cnt의 합을 출력한다.

 

 

 

소스 코드 (⭕) - 리팩터링

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

        char[] arr1 = br.readLine().toCharArray();
        char[] arr2 = br.readLine().toCharArray();

        int[] cntArr = new int[26];
        for (char c : arr1) {
            cntArr[c - 'a']++;
        }
        for (char c : arr2) {
            cntArr[c - 'a']--;
        }

        int sum = 0;
        for (int cnt : cntArr) {
            sum += Math.abs(cnt);
        }

        System.out.println(sum);
    }
}

이중 반복문을 돌리는게 너무 비효율적인 것 같아서 더 나은 방법이 있나 찾아봤더니 훨씬 좋은 코드가 있었다.

arr1에만 있는 알파벳 개수는 +1이 되고, arr2에만 있는 알파벳 개수는 -1이 된다.

알파벳 등장 횟수가 동일한 알파벳 위치 값은 0이 된다.

최종적으로, 알파벳 위치의 값들의 절댓값을 누적합 시켜주면 정답이 된다.

 

 

리팩터링을 통해 최적화된 것을 볼 수 있다.

 

 

end

각각 알파벳의 등장 횟수를 구할 때는 arr[c - 'a']++ 형태의 방법을 꼭 이용해보자. 그리고 +와 -를 이용한 절댓값으로 정답을 구하는 풀이가 너무 매력적이라 계속 보게 된다. ㅠㅠ 간단한데 머리 띵 하게 되는 풀이,,