[백준](2024)애너그램 만들기(설명/코드/정답)

 

문제 링크 : https://www.acmicpc.net/problem/1919

 

 

난이도		알고리즘
	브론즈2	구현, 문자열

 

 

1. 요구 사항 이해

시간, 메모리 제한 : 2초 / 128MB

 

두 단어의 문자를 재배치하여 같은 문자로 이루어진 단어로 만들기 위해 얼마나 많은 문자를 제거해야 하는지 계산.

소문자, ( 1 <= 각 단어의 길이 <=1000 )

 

 

2. 설계/검증 

26개의 알파벳마다 등장 횟수 기록할 배열

 

시간 복잡도	최악의 경우	공간 복잡도
O(N)	2000	O(N)

 

 

함수화

String word1
String word2

getAlphabetCount(String w){
	알파벳 배열 생성
    for(){
    	각 알파벳 등장 횟수를 배열에 추가
    }
}

calculateDifference(int[] c1, int[] c2){
	두 배열의 차
}

 

 

 

 

3. 정상 코드

import java.util.*;

public class Main {

    // 각 알파벳 등장 횟수를 계산하는 메서드
    private static int[] getAlphabetCount(String w){
        int[] count = new int[26]; // 소문자 알파벳 26개에 대한 배열 선언
        for (int i = 0; i < w.length(); i++)
            count[w.charAt(i) - 'a']++; // 각 문자의 등장 횟수를 배열에 기록
        return count;
    }

    private static int calculateDifference(int[] c1, int[] c2) {
        int result = 0;
        for (int i = 0; i < 26; i++)
            // 각 알파벳에 대한 차이의 절댓값을 더함
            result += Math.abs(c1[i] - c2[i]);
        return result;
    }


    public static void main(String[] args){

        // 사용자로부터 두 개의 단어 입력 받기
        Scanner sc = new Scanner(System.in);
        String word1 = sc.next();
        String word2 = sc.next();

        // 각 단어의 알파벳 등장 횟수 계산
        int[] count_w1 = getAlphabetCount(word1);
        int[] count_w2 = getAlphabetCount(word2);

        sc.close();

        // 두 단어 간 알파벳 등장 횟수의 차이를 계산 후 출력
        int result = calculateDifference(count_w1, count_w2);
        System.out.println(result);

    }
}

 

 

4. 처리 과정 추적 코드

import java.util.*;

public class Main {

    // 각 알파벳 등장 횟수를 계산하는 메서드
    private static int[] getAlphabetCount(String w){
        int[] count = new int[26]; // 소문자 알파벳 26개에 대한 배열 선언
        System.out.printf("\n------------------------\n");
        System.out.println("알파벳 카운트 배열 초기화: " + Arrays.toString(count));
        for (int i = 0; i < w.length(); i++) {
            char currentChar = w.charAt(i);
            count[currentChar - 'a']++; // 각 문자의 등장 횟수를 배열에 기록
            System.out.println("현재 처리하는 문자: " + currentChar);
            System.out.println("알파벳 카운트 배열: " + Arrays.toString(count));
        }
        return count;
    }

    private static int calculateDifference(int[] c1, int[] c2) {
        int result = 0;
        for (int i = 0; i < 26; i++) {
            // 각 알파벳에 대한 차이의 절댓값을 더함
            result += Math.abs(c1[i] - c2[i]);
        }
        return result;
    }

    public static void main(String[] args){

        // 사용자로부터 두 개의 단어 입력 받기
        Scanner sc = new Scanner(System.in);
        String word1 = sc.next();
        String word2 = sc.next();

        // 각 단어의 알파벳 등장 횟수 계산
        int[] count_w1 = getAlphabetCount(word1);
        int[] count_w2 = getAlphabetCount(word2);

        sc.close();

        System.out.printf("\n------------------------\n");
        System.out.println("알파벳 카운트 배열 (word1): " + Arrays.toString(count_w1));
        System.out.println("알파벳 카운트 배열 (word2): " + Arrays.toString(count_w2));

        // 두 단어 간 알파벳 등장 횟수의 차이를 계산 후 출력
        int result = calculateDifference(count_w1, count_w2);
        System.out.println("애너그램 만들기에 필요한 연산 수: " + result);

    }
}