[백준/BOJ][Java][1919] 애너그램 만들기

2023.08.21 - [Java] - Java String 이해

Java String 이해

---

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

1919번: 애너그램 만들기

• 문제 : 두 단어를 애너그램으로 만들기 위해 제거해야하는 문자의 최소 개수
• 애너그램 : 단어의 구성(알파벳과 그 개수)이 완전히 같은 언어

1. A : “aabbcc” B:”xxyybb”의 답은 왜 8일까?
   1. A의 {a, a, c, c} 가 B에 없으니 지워야만 함
   2. B의 {x, x, y, y}가 A에 없으니 지워야만 함
2. 없애야만 하는 문자: 공통 문자를 제외한 전부

내가 푼 틀린 풀이

• 각 문자열끼리 단어가 포함되어있는지 확인하고, 문자열끼리의 총합에서 중복되는 것만 빼면 되는 줄 알았는데, 당연히 틀렸다.
• 애너그램이라는게 개수도 봐야하기 때문에 예시 dared, bread로 테스트해보면 안되는 걸 알 수 있다.
• xxaayy, aabbcc로 테스트할땐 되서 제출했더니..

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String a = sc.next();
        String b = sc.next();

        // 단지 '포함'하는지만 체크할 경우, 문자 개수 차이를 파악 못한다
        // 예시 dared, bread
        int answer = 0;
        for (int i = 0; i < a.length(); i++) {
            if (b.contains(String.valueOf(a.charAt(i)))) {
                answer ++;
            }
        }

        for (int i = 0; i < b.length(); i++) {
            if (a.contains(String.valueOf(b.charAt(i)))) {
                answer ++;
            }
        }
        System.out.print(b.length() + a.length() - (answer));
        }
    }

 

다시 푼 풀이

• 캐릭터의 개수를 셀 수 있는 알파벳 사이즈만큼 배열을 만들어준 뒤, a와 b에 문자열이 포함되어있을 경우 해당 인덱스 부분을 +,- 연산해줬다
• 그리고 알파벳 개수 배열에 있는 숫자를 절대값으로 다 더해줬다

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String a = sc.next();
        String b = sc.next();

        int[] charCount = new int[26]; // 알파벳 개수만큼 배열 생성

        for (char c : a.toCharArray()) {
            charCount[c - 'a']++; // 문자 등장 횟수 카운트
        }

        for (char c : b.toCharArray()) {
            charCount[c - 'a']--; // 문자 등장 횟수 감소
        }

        int answer = 0;
        for (int count : charCount) {
            answer += Math.abs(count); // 문자열 간 차이의 합 구하기
        }

        System.out.println(answer);
    }
}

 

메모리	시간	언어	코드 길이
17548KB	204ms	Java 11	712B

강의 풀이 1

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String a = sc.next();
        String b = sc.next();

        int[] countA = new int[26]; // dared; [1, 0, 0, 2 ..]
        int[] countB = new int[26];
        for (int i = 0; i < a.length() ; i++) {
            countA[a.charAt(i) - 'a']++;
        }
        for (int i = 0; i < b.length(); i++) {
            countB[b.charAt(i) - 'a']++;
        }
        
        int ans = 0;
        for (int i = 0; i < 26 ; i++) {
            if (countA[i] > countB[i])
                ans += countA[i] - countB[i];
            else if (countB[i] > countA[i])
                ans += countB[i] - countA[i];
        }
        System.out.println(ans);
    }
}

메모리	시간	언어	코드 길이
17600KB	208ms	Java 11	788B

강의 풀이 2

import java.util.Scanner;

public class Main {
    // 어떤 문자열에 대해 count배열을 만들고 있음 : 똑같은 기능이 반복이 되고 있을 경우, 함수로 빼라
    // 함수로 빼서 코딩을 할 경우 간단하게 만들 수 있고, 함수 디자인하는거에 익숙해져야 구현문제를 풀때 어려움이 없을 것이다
    public static int[] getAlphabetCount(String str) {
        int[] count = new int[26];
        for (int i = 0; i < str.length() ; i++) {
            count[str.charAt(i) - 'a']++;
        }
        return count;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String a = sc.next();
        String b = sc.next();

        int[] countA = getAlphabetCount(a);
        int[] countB = getAlphabetCount(b);

        int ans = 0;
        for (int i = 0; i < 26 ; i++)
            // a카운트와 b카운트 중에 뭐가 더 큰지를 비교하고 빼주는 이유는
            // 단순히 그냥 빼게되면 음수가 나올 수 있기 때문에 대소비교를 해주는 것인데
            // 절대값 이용하면 분기 처리 안해도 된다
            ans += Math.abs(countA[i] - countB[i]);
        System.out.println(ans);
    }
}

메모리	시간	언어	코드 길이
17528KB	204ms	Java 11	658B