[코딩테스트] BOJ 11328

자료구조, 코딩테스트/배열(Array)

[코딩테스트] BOJ 11328 - Strfry (실패)

RꞮbble 2026. 4. 2. 23:20

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

문제

C 언어 프로그래밍에서 문자열(string)은 native한 자료형이 아니다. 사실, 문자열은 그저, 문자열의 끝을 표시하기 위한 말단의 NULL이 사용된, 문자들로 이루어진 문자열일 뿐이다. 하지만 프로그래밍 언어에서 문자열을 다루는 것은 매우 중요하기 때문에, C 표준 라이브러리는 문자열을 다루는 데에 매우 유용한 함수들을 제공하고 있다 : 그들 중에는 strcpy, strcmp, strtol, strtok, strlen, strcat 가 있다.

하지만, 잘 알려져 있지 않으며, 잘 사용되지도 않는 함수가 하나 있다 : strfry 함수다. strfry 함수는 입력된 문자열을 무작위로 재배열하여 새로운 문자열을 만들어낸다. (역자 주 : 여기에서 입력된 문자열과 새로 재배열된 문자열이 다를 필요는 없다.)

두 개의 문자열에 대해, 2번째 문자열이 1번째 문자열에 strfry 함수를 적용하여 얻어질 수 있는지 판단하라.

입력

입력의 첫 번째 줄은 테스트 케이스의 수 0 < N < 1001 이다.

각각의 테스트 케이스는 하나의 줄에 영어 소문자들로만 이루어진 두 개의 문자열이 한 개의 공백으로 구분되어 주어진다. 각각의 문자열의 길이는 최대 1000 이다.

출력

각각의 테스트 케이스에 대해, 2번째 문자열이 1번째 문자열에 strfry 함수를 적용하여 얻어질 수 있는지의 여부를 "Impossible"(불가능) 또는 "Possible"(가능)으로 나타내시오. (따옴표는 제외하고 출력한다.)

예제 입력1

4
a a
ab ba
ring gnir
newt twan

예제 출력1

Possible
Possible
Possible
Impossible

풀이

첫째줄에는 테스트케이스 수(N) (0 < N < 1,001)

두번째 줄부터 N개의 줄에는 영어 소문자 문자열이 공백으로 구분되어 주어진다. (영어 소문자 문자열 길이는 최대 1,000)

이때 2번째 문자열(=문자열2)에 있는 각 문자들의 개수가 1번째 문자열(=문자열1)의 각 문자들의 개수가 같으면 "Possible"을 다르다면 "Impossible"을 출력하면 된다.

배열에 문자의 개수를 저장해서 풀어봤다.

1. 문자열1, 문자열2의 문자 각각의 개수를 arr1, arr2에 저장하자.

2. 문자열2의 첫번째 문자부터 읽으면서, arr2[문자열2의 문자]가 arr1에 있는지 확인한다.

2-1. 있다면 arr1[문자열2의 문자]--

2-2. 없다면 "Impossible"을 출력한다.

3. 문자열2를 첫번째 문자부터 마지막 문자까지 읽었는데 모두 일치하는 문자가 있다면 "Possible"을 출력한다.

이걸 코드로 풀면 다음과 같다.

코드1

internal class BOJ11328_Strfry
{
    static void Main(string[] args)
    {
        StreamReader sr = new StreamReader(Console.OpenStandardInput());

        int N = int.Parse(sr.ReadLine());

        int[] arr1 = new int[2000];
        int[] arr2 = new int[2000];

        string[] input;
        bool flag = true;
        for(int i = 0; i < N; i++)
        {
            input = sr.ReadLine().Split(" ");

            foreach(char c in input[0])
            {
                arr1[c]++;
            }

            foreach(char c in input[1])
            {
                arr2[c]++;
            }


            foreach(char c in input[1])
            {
                if (arr1[c] != 0)
                {
                    arr1[c]--;
                }
                else
                {
                    flag = false;
                    break;
                }
            }

            if (!flag)
            {
                Console.WriteLine("Impossible");
                flag = true;
            }
            else
            {
                Console.WriteLine("Possible");
            }
        }
    }
}

문제 원인

i번째 문자열을 비교하고 "Impossible" 혹은 "Possible"을 출력하고 나면 배열에 저장된 문자의 개수들은 0으로 초기화해야 한다.

그런데 내 코드는 0으로 초기화하지 않고 이전 문자 개수들이 그대로 배열에 저장되어 있다.

그 상태에서 다음 문자열들을 비교하니 오답이 나온다.

코드2

internal class BOJ11328_Strfry
{
    static void Main(string[] args)
    {
        StreamReader sr = new StreamReader(Console.OpenStandardInput());

        int N = int.Parse(sr.ReadLine());

        int[] arr1 = new int[2000];
        int[] arr2 = new int[2000];

        string[] input;
        bool flag = true;
        for(int i = 0; i < N; i++)
        {
            input = sr.ReadLine().Split(" ");

            foreach(char c in input[0])
            {
                arr1[c]++;
            }

            foreach(char c in input[1])
            {
                arr2[c]++;
            }


            foreach(char c in input[1])
            {
                if (arr1[c] != 0)
                {
                    arr1[c]--;
                }
                else
                {
                    flag = false;
                    break;
                }
            }

            if (!flag)
            {
                Console.WriteLine("Impossible");
                flag = true;
            }
            else
            {
                Console.WriteLine("Possible");
            }
            
            Array.Fill(arr1, 0);
            Array.Fill(arr2, 0);
        }
    }
}

문제 원인

문자열2의 각 문자가 문자열1에 포함되어 있는지만 체크하고 있다.

문자열1 = "aabb", 문자열2 = "aab"와 같이 두 문자열 길이가 다를 경우, 문자열2의 문자들은 모두 문자열1에 존재하므로 "Possible"이 출력된다.

코드3

internal class BOJ11328_Strfry
{
    static void Main(string[] args)
    {
        StreamReader sr = new StreamReader(Console.OpenStandardInput());

        int N = int.Parse(sr.ReadLine());

        int[] arr1 = new int[2000];
        int[] arr2 = new int[2000];

        string[] input;
        bool flag = true;
        for(int i = 0; i < N; i++)
        {
            input = sr.ReadLine().Split(" ");

            foreach(char c in input[0])
            {
                arr1[c]++;
            }

            foreach(char c in input[1])
            {
                arr2[c]++;
            }


            foreach(char c in input[1])
            {
                if (arr1[c] != 0 && arr2[c] != 0)
                {
                    arr1[c]--;
                    arr2[c]--;
                }
                else
                {
                    flag = false;
                    break;
                }
            }

            if (!flag)
            {
                Console.WriteLine("Impossible");
                flag = true;
            }
            else
            {
                Console.WriteLine("Possible");
            }

            Array.Fill(arr1, 0);
            Array.Fill(arr2, 0);
        }
    }
}

문제 원인

문자열2가 "a"이고, 문자열1이 "aabb"이면 위 코드는 "Possible"이 출력된다.

문자의 존재 여부로 문제를 풀어서 틀렸다.

문자의 존재 여부가 아니라 문자의 개수로 문제를 풀어야 한다.

코드4

internal class BOJ11328_Strfry
{
    static void Main(string[] args)
    {
        StreamReader sr = new StreamReader(Console.OpenStandardInput());

        int N = int.Parse(sr.ReadLine());

        int[] arr1 = new int[2000];
        int[] arr2 = new int[2000];

        string[] input;
        bool flag = true;
        for(int i = 0; i < N; i++)
        {
            input = sr.ReadLine().Split(" ");

            foreach(char c in input[0])
            {
                arr1[c]++;
            }

            foreach(char c in input[1])
            {
                arr2[c]++;
            }


            foreach(char c in input[1])
            {
                if (arr1[c] != 0 && arr2[c] != 0)
                {
                    arr1[c]--;
                    arr2[c]--;
                }
                else
                {
                    flag = false;
                    break;
                }
            }

            if (input[0].Length != input[1].Length)
            {
                flag = false;
            }
            if (!flag)
            {
                Console.WriteLine("Impossible");
                flag = true;
            }
            else
            {
                Console.WriteLine("Possible");
            }

            Array.Fill(arr1, 0);
            Array.Fill(arr2, 0);
        }
    }
}

문자열1과 문자열2의 길이가 맞지 않을 경우 "Impossible"을 출력하도록 코드를 추가해주니 통과했다.

코드5

internal class BOJ11328_Strfry
{
    static void Main(string[] args)
    {
        StreamReader sr = new StreamReader(Console.OpenStandardInput());
        StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

        int N = int.Parse(sr.ReadLine());

        int[] arr1 = new int[2000];
        int[] arr2 = new int[2000];

        string[] input;
        bool flag = true;
        for(int i = 0; i < N; i++)
        {
            input = sr.ReadLine().Split(" ");

            foreach(char c in input[0])
            {
                arr1[c]++;
            }

            foreach(char c in input[1])
            {
                arr2[c]++;
            }


            foreach(char c in input[1])
            {
                if (arr1[c] != 0 && arr2[c] != 0)
                {
                    arr1[c]--;
                    arr2[c]--;
                }
                else
                {
                    flag = false;
                    break;
                }
            }

            if (input[0].Length != input[1].Length)
            {
                flag = false;
            }
            if (!flag)
            {
                //Console.WriteLine("Impossible");
                sw.WriteLine("Impossible");
                flag = true;
            }
            else
            {
                //Console.WriteLine("Possible");
                sw.WriteLine("Possible");
            }

            Array.Fill(arr1, 0);
            Array.Fill(arr2, 0);
        }

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

StreamReader, StreamWriter를 사용해서 풀이 시간을 줄여봤다.

복습1 풀이 (5/22)

문자열1을 뒤집은 것이 문자열2인지 확인하는 문제인 것 같았다.

문자열1, 문자열2를 각각 다른 리스트에 넣고, 리스트1의 첫번째부터 마지막까지와 리스트2의 마지막번째부터 첫번째까지 서로 비교하면 되겠다.

코드1 - 오답

using System.Text;

public class BOJ11328
{
    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를 뒤집은 것과 같다 -> Possible
        // 문자열1이 문자열2를 뒤집은 것과 같지 않다. -> Impossible

        // 문자열1을 리스트에 넣는다. 
        // 문자열2을 리스트에 넣는다. 
        // 문자열1 리스트 첫번째부터 마자믹까지와 문자열2 리스트 마지막번째부터 첫번째와 비교한다. 
            // 하나라도 일치하지 않으면 Impossible을 출력
            // 모두 일치하면 Possible을 출력 

        // 문자열 데이터 넣기 -> O(1000) + O(1000) = O(N)
        // 문자열 비교 -> O(N)
        // 충분하다. 
        
        int N = int.Parse(sr.ReadLine());

        string[] input;
        List<char> strList1;
        List<char> strList2;
        int index1 = 0; 
        int index2 = 0;
        bool isSuccess = false;
        for(int i = 0; i < N; i++)
        {
            input = sr.ReadLine().Split(" ");

            strList1 = input[0].ToList();
            strList2 = input[1].ToList();

            index1 = 0; 
            index2 = strList2.Count - 1;

            for(int j = 0; j < strList1.Count; j++)
            {
                if(strList1[index1] == strList2[index2])
                {
                    isSuccess = true;
                }
                else
                {
                    isSuccess = false;
                    break;
                }

                index1++;
                index2--;
            }

            if (!isSuccess)
            {
                sb.AppendLine("Impossible");
            }
            else
            {
                sb.AppendLine("Possible");
            }
        }

        sw.WriteLine(sb.ToString());

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

문제를 잘못 이해하고 풀어서 오답이 나왔다.

이 문제는 문자열1을 무작위로 재배열한 것이 문자열2인지 확인하는 문제다. ~~문자열1을 뒤집은 것이 문자열2인지 확인하는 문제가 아니다.~~

코드2 - 오답

using System.Text;

public class BOJ11328
{
    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를 얻을 수 있는지 확인하는 문제
         문자열1 각 문자를 딕셔너리에 넣고  (딕셔너리 = Dictionary<string, int>)
         문자열2 각 문자를 딕셔너리와 비교하면 된다. 
            딕셔너리에 없는 문자라면 -> Impossible
            딕셔너리에 있는 문자라면 해당 문자의 개수를 차감한다. 
                문자 개수가 음수가 되면 -> Impossible 
                다 돌았고 음수가 되지 않는다면 -> Possible 
        */

        int N = int.Parse(sr.ReadLine());

        string[] input;
        string str1;
        string str2;
        Dictionary<char, int> dict1 = new Dictionary<char, int>();
        Dictionary<char, int> dict2 = new Dictionary<char, int>();
        bool isSuccess = true;
        for(int i = 0; i < N; i++)
        {
            input = sr.ReadLine().Split(" ");

            str1 = input[0];
            str2 = input[1];

            isSuccess = true;
            dict1.Clear();
            dict2.Clear();

            foreach(char c in str1)
            {
                if (!dict1.ContainsKey(c))
                {
                    dict1.Add(c, 1);
                }
                else
                {
                    dict1[c]++;
                }
            }

            foreach(char c in str2)
            {
                if (!dict1.ContainsKey(c))
                {
                    sb.AppendLine("Impossible");
                    isSuccess = false;
                    break;
                }
                else
                {
                    dict1[c]--;

                    if(dict1[c] < 0)
                    {
                        sb.AppendLine("Impossible");
                        isSuccess = false;
                        break;
                    }   
                }
            }

            if (isSuccess)
            {
                sb.AppendLine("Possible");
            }
        }

        sw.WriteLine(sb.ToString());

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

문자열1과 문자열2의 길이가 다를때 잘못된 결과값이 나와 오답이 나온다.

코드3 - 정답

using System.Text;

public class BOJ11328
{
    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를 얻을 수 있는지 확인하는 문제
         문자열1 각 문자를 딕셔너리에 넣고  (딕셔너리 = Dictionary<string, int>)
         문자열2 각 문자를 딕셔너리와 비교하면 된다. 
            딕셔너리에 없는 문자라면 -> Impossible
            딕셔너리에 있는 문자라면 해당 문자의 개수를 차감한다. 
                문자 개수가 음수가 되면 -> Impossible 
                다 돌았고 음수가 되지 않는다면 -> Possible 
        */

        int N = int.Parse(sr.ReadLine());

        string[] input;
        string str1;
        string str2;
        Dictionary<char, int> dict1 = new Dictionary<char, int>();
        Dictionary<char, int> dict2 = new Dictionary<char, int>();
        bool isSuccess = true;
        for(int i = 0; i < N; i++)
        {
            input = sr.ReadLine().Split(" ");

            str1 = input[0];
            str2 = input[1];

            if(str1.Length != str2.Length)
            {
                isSuccess = false;
                sb.AppendLine("Impossible");
                continue;
            }

            isSuccess = true;
            dict1.Clear();
            dict2.Clear();

            foreach(char c in str1)
            {
                if (!dict1.ContainsKey(c))
                {
                    dict1.Add(c, 1);
                }
                else
                {
                    dict1[c]++;
                }
            }

            foreach(char c in str2)
            {
                if (!dict1.ContainsKey(c))
                {
                    sb.AppendLine("Impossible");
                    isSuccess = false;
                    break;
                }
                else
                {
                    dict1[c]--;

                    if(dict1[c] < 0)
                    {
                        sb.AppendLine("Impossible");
                        isSuccess = false;
                        break;
                    }   
                }
            }

            if (isSuccess)
            {
                sb.AppendLine("Possible");
            }
        }

        sw.WriteLine(sb.ToString());

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

'자료구조, 코딩테스트 > 배열(Array)' 카테고리의 다른 글

[코딩테스트] BOJ 10808 - 알파벳 개수 (성공) (0)	2026.04.06
[코딩테스트] BOJ 1919 - 에너그램 만들기 (성공) (0)	2026.04.05
[코딩테스트] BOJ 13300 - 방 배정 (실패) (0)	2026.04.01
[코딩테스트] BOJ 10807 - 개수 세기 (성공) (0)	2026.03.31
[코딩테스트] BOJ 3273 - 두 수의 합 (성공) (0)	2026.03.30

현재글[코딩테스트] BOJ 11328 - Strfry (실패)

회고록

ribblestudy 님의 블로그 입니다.

Today I Learned, 개인 프로젝트, C#, Radix Sort, 연결리스트, Unity, 코딩테스트, magnitude, heap, LLM, counting sort, 유니티, deque, Merge Sort, sqrMagnitude, Til, 힙, Boyer_Moore, 깊이 우선 탐색, Quick Sort, DFS, 너비 우선 탐색, Rigidbody, 게임 클라이언트 개발자, shader, BFS, GitHub Desktop, 스택, 111퍼센트, 자료구조,

Today :
Yesterday :

회고록