[백준OJ] 13022번 늑대와 올바른 단어

 

 

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

13022번: 늑대와 올바른 단어

---

풀이

'w' = 0, 'o' = 1, 'l' = 2, 'f' = 3 으로 인덱스를 정해준 뒤, 문자열을 탐색하면서 조건을 확인해주었습니다.

1. 이전 알파벳의 인덱스 == 현재 알파벳의 인덱스
   이 경우에는 해당 인덱스의 cnt를 갱신시켜 줍니다.
2. 이전 알파벳의 인덱스+1 == 현재 알파벳의 인덱스
   이 경우에는, 이전 알파벳의 인덱스를 갱신시켜주고, 현재 알파벳의 개수를 갱신시켜줍니다.
3. 현재 알파벳이 w인경우(새로운 wolf의 시작점인 경우)
   현재까지 나온 w,o,l,f의 개수가 모두 일치하는지에 대해 검증합니다.
   검증을 통과하면 cnt배열을 새로 초기화 한 뒤, 이전 알파벳의 인덱스와 현재 알파벳 개수를 갱신시켜 줍니다.
4. 1~3번 이외의 경우는 잘못된 문자열입니다.

 

시간복잡도

선형 시간안에 해결할 수 있으므로, O(N)이 됩니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    //해당 알파벳을 인덱스로 치환하는 함수
    public static int charToIndex(char c){
        switch(c){
            case 'w':
                return 0;
            case 'o':
                return 1;
            case 'l':
                return 2;
            case 'f':
                return 3;
            default:
                return -1;
        }
    }
    //모든 알파벳들이 동일한 개수인지 확인하는 함수
    public static boolean check(int[] cnt){
        int n = cnt[0];
        for(int i=1;i<4;i++){
            if(cnt[i]!=n) return false;
        }
        return true;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String str = br.readLine();

        int[] cnt = new int[4];
        char prev = str.charAt(0);
        int pIndex = charToIndex(prev);
        cnt[pIndex]++;
        int answer=1;

        for(int i=1;i<str.length();i++){
            char c = str.charAt(i);
            int cIndex = charToIndex(c);
            if(cIndex==pIndex){//이전 문자와 같은 문자일때
                cnt[cIndex]++;
            }
            else if(cIndex == pIndex+1){//이전 문자의 다음번 문자일때
                cnt[cIndex]++;
                pIndex=cIndex;
            }
            else if(cIndex==0){//다음번 w로 넘어갔을때 검증
                if(!check(cnt)) answer = 0;

                Arrays.fill(cnt,0);
                pIndex=cIndex;
                cnt[cIndex]++;
            }
            else{//아닌경우 잘못된 문자열
                answer = 0;
            }
        }
        if(!check(cnt)) answer = 0;
        System.out.println(answer);
    }
}