[알고리즘] 크로아티아 알파벳 (백준 2941번)

2941번: 크로아티아 알파벳

 일종의 문자 패턴 매칭? 부류의 문제라고도 볼 수 있을 듯 한데 나같은 경우엔 stack을 이용해서 풀었으나 다른 사람들의 코드를 보니 String의 replace 메서드를 이용해서 푼 사람들이 많았다. (생각도 못했음...)

 

Solution 1) Stack 사용

1. list라는 배열에 크로아티아 알파벳을 전부 집어넣는다.
2. isCroaticAlphabet() 메서드를 만들어서 word가 list 안에 있으면 크로아티아 알파벳으로 판별하고 true를 반환한다.
3. str의 길이만큼 반복문을 돈다
   1. stack이 비어있으면 바로 문자를 push 한다.
   2. stack이 비어있지 않다면 바로 전 문자를 꺼내어(stack.peek()) 현재 문자와 합친 후 크로아티아 알파벳인지 검사한다.
   3. 크로아티아 알파벳이 맞다면 stack.pop() 후 "z=" 여부 검사한다.,
      1. "z=" 가 맞다면 그전 문자를 꺼내어서 "dz="인지 확인한다.
      2. 맞다면 다시 한 번 stack.pop()을 한 후 word = "dz="로 만든다.
      3. stack에 word를 push 한다.
   4. 크로아티아 알파벳이 아니라면 바로 stack에 문자를 push 한다.
4. 반복문 종료 후 stack의 size를 출력한다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;

public class Main {

    static boolean isCroaticAlphabet(String list[], String word)
    {
        return Arrays.asList(list).contains(word);
    }

    public static void main(String[] args) {

        try
        {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

            String str = br.readLine();

            String list[] = {"c=", "c-", "dz=", "d-", "lj", "nj", "s=", "z="};

            Stack<String> stack = new Stack<>();

            for(int i = 0;i < str.length();i++)
            {
                char c = str.charAt(i);

                //스택이 비었다면 바로 push
                if(stack.isEmpty())
                    stack.push(c+"");
                //스택에 문자가 있다면 꺼내서 검사
                else
                {
                    String word = stack.peek() + c;

                    //크로아티아 알파벳 검사
                    if(isCroaticAlphabet(list, word))
                    {
                        stack.pop();

                        //z= 인 경우엔 dz=인지 추가로 검사
                        if(word.equals("z="))
                        {
                            if(!stack.isEmpty() && stack.peek().equals("d"))
                                word = stack.pop() + word;
                        }

                        stack.push(word);
                    }
                    else
                        stack.push(c+"");
                }
            }

            System.out.println(stack.size());
        }
        catch (Exception e)
        {
            e.printStackTrace();
        }

    }

}

 

---

Solution 2) String의 replace 사용

1. list라는 배열에 크로아티아 알파벳을 전부 집어넣는다.
2. list 크기만큼 반복문을 돈다.
   1. str에 list[i] 문자를 공백 문자 " "로 대체한다. ( str.replaceAll(list[i], " ") )
3. str의 길이를 출력한다.

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

public class Main {


    public static void main(String[] args) {

        try
        {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

            String str = br.readLine();

            String list[] = {"c=", "c-", "dz=", "d-", "lj", "nj", "s=", "z="};

            for(int i = 0;i < list.length;i++)
                str = str.replaceAll(list[i], " ");

            System.out.println(str.length());
        }
        catch (Exception e)
        {
            e.printStackTrace();
        }

    }

}