[코딩테스트] BOJ 1919 - 에너그램 만들기 (성공)

 

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

 

 

문제

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

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

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

 

 

입력

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

 

 

출력

첫째 줄에 답을 출력한다.

 

 

예제 입력1

aabbcc
xxyybb

 

예제 출력1

8

 

 

풀이

배열 인덱스를 문자열의 문자로 하여 풀어봤다. 

 

코드

internal class BOJ1919_에너그램_만들기
{
    static void Main(string[] args)
    {
        StreamReader sr = new StreamReader(Console.OpenStandardInput());
        StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

        string input1 = sr.ReadLine();
        string input2 = sr.ReadLine();

        int[] arr1 = new int[200];
        int[] arr2 = new int[200];
        foreach(char c in input1) arr1[c]++;
        foreach(char c in input2) arr2[c]++;

        foreach(char c in input1)
        {
            if (arr2[c] != 0)
            {
                arr1[c]--;
                arr2[c]--;
            }
        }

        int result = 0;
        foreach(int num in arr1)
        {
            if (num != 0) result += num;
        }
        foreach (int num in arr2)
        {
            if (num != 0) result += num;
        }
        sw.WriteLine(result);

        sr.Close();
        sw.Close();
    }
}

 

 

다른 풀이

2차원 배열을 사용해서 코드를 줄였고, 문자 - 'a'를 인덱스로 하여 인덱스 번호가 무조건 0부터 25까지 나올 수 있도록 한 코드다. 

다음번에 비슷한 문제가 나왔을 때 나도 이렇게 풀어봐야 겠다. 

 

코드

internal class BOJ1919_에너그램_만들기
{
    static void Main(string[] args)
    {
        int[,] arr = new int[2,26];
        string s1, s2;

        StreamReader sr = new StreamReader(Console.OpenStandardInput());
        StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

        s1 = sr.ReadLine();
        s2 = sr.ReadLine();

        foreach (char c in s1)
            arr[0, c - 'a']++;

        foreach (char c in s2)
            arr[1, c - 'a']++;

        int result = 0;
        for (int i = 0; i < 26; i++)
            result += Math.Abs(arr[0, i] - arr[1, i]);

        sw.WriteLine(result);

        sr.Close();
        sw.Close();
    }
}

 

 

복습1 풀이1 (5/23)

문자열의 문자를 배열의 인덱스로 하여 풀면 될 것 같은데, 어떻게 풀어야 할지 전혀 감이 오지 않는다. 

 

 

복습1 풀이2 

예전에 내가 짰던 코드를 다시 봤다. 

문자열1과 문자열2에서 같은 문자가 아닌 것을 헤아리려면, 일단 문자열1과 문자열2의 문자들 개수를 각각 배열(array1, array2)에 넣고, 배열을 서로 비교해가며 같은 문자인지 아닌지 같은 문자라면 배열에서 문자 개수를 줄여주면 된다. 

 

 

코드 - 정답

using System.Text;
using System.Linq;

public class BOJ1919
{
    static StreamReader sr = new StreamReader(Console.OpenStandardInput());
    static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
    static StringBuilder sb = new StringBuilder();

    static void Main(string[] args)
    {
        // 문자열1과 문자열2에서 같은 문자가 아닌 것들 헤아리기. 

        //
        string input1 = sr.ReadLine();
        string input2 = sr.ReadLine();

        int[] array1 = new int[200];
        int[] array2 = new int[200];
        foreach(char c in input1)
        {
            array1[c]++;
        }
        foreach(char c in input2)
        {
            array2[c]++;
        }

        foreach(char c in input1)
        {
            if(array2[c] > 0)
            {
                array1[c]--;
                array2[c]--;
            }
        }

        int result = array1.Sum() + array2.Sum();

        sb.Append(result);

        sw.WriteLine(sb.ToString());
        
        sr.Close();
        sw.Close();
        sb.Clear();
    }
}

 

 

코드2 - 정답

using System.Text;
using System.Linq;

public class BOJ1919
{
    static StreamReader sr = new StreamReader(Console.OpenStandardInput());
    static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
    static StringBuilder sb = new StringBuilder();

    static void Main(string[] args)
    {
        // 문자열1과 문자열2에서 같은 문자가 아닌 것들 헤아리기. 

        string input1 = sr.ReadLine();
        string input2 = sr.ReadLine();

        int[] array1 = new int[26];
        int[] array2 = new int[26];

        foreach(char c in input1)
        {
            array1[c - 'a']++;
        }
        foreach(char c in input2)
        {
            array2[c - 'a']++;
        }

        int sum = 0; 
        for(int i = 0; i < 26; i++)
        {
            sum += Math.Abs(array1[i] - array2[i]);
        }

        sb.Append(sum);

        sw.WriteLine(sb.ToString());

        sr.Close();
        sw.Close();
    }
}

다른 풀이를 참고해서 만들어봤다. 

아스키코드를 생각해서 만들어봤고 이렇게 하면 필요한 공간만 배열로 만들어서 문제를 풀 수 있다.