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

13022 늑대와 올바른 단어

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

문제설명

 문자열에서 'w', 'o', 'l', 'f'가 규칙적으로 나타나고, 각 문자의 개수가 같아야 "wolf" 시퀀스가 유효할때

주어진 문자열에서 "wolf"의 각 문자가 특정한 순서와 개수로 나타나는지 검사한다.

 

• 'w', 'o', 'l', 'f'의 순서:
  • 'w'가 먼저 와야 하고, 다음에 'o', 그 다음에 'l', 마지막으로 'f'가 와야 한다
  • 각 문자의 개수가 같다.

 

문제풀이

 

1. 각 문자의 개수를 기록하기 위해 배열을 저장한다.
   • 배열 인덱스는 'w' (0), 'o' (1), 'l' (2), 'f' (3)와 같다.
2. 문자열을 처음부터 끝까지 순회한다:
   1. 각 문자의 이전 문자와 현재 문자의 인덱스 차이를 계산한다.
   2. 올바른 순서 ('w' -> 'o' -> 'l' -> 'f')인지 확인한다.
   3. 인덱스 차이가 -3인 경우 (즉, 'f' 다음에 'w'가 올 경우) 카운트를 초기화하고 새로운 시퀀스를 시작한다.
   4. 그 외의 경우에는 현재 문자의 카운트를 증가한다.
3. 문자열 순회를 끝낸 후, 각 문자의 개수가 같은지 확인한다.
4. 시퀀스가 유효하면 1을, 그렇지 않으면 0을 출력한다.

 

O(n)  시간복잡도

각 문자열을 순회하며 한번씩 검사한다.

전체코드

import java.util.*;
import java.io.*;

public class Main {
    static int count[]; // 'w', 'o', 'l', 'f'의 개수를 기록할 배열

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

        // 문자열 길이가 4 미만이면 "wolf"의 전체 시퀀스를 포함할 수 없음
        if (s.length() < 4) {
            System.out.println(0);
        } else {
            // 'w', 'o', 'l', 'f'의 개수를 추적하기 위해 count 배열 초기화
            count = new int[4];
            // 문자와 count 배열의 인덱스를 연결하기 위한 HashMap
            HashMap<Character, Integer> map = new HashMap<>();
            map.put('w', 0); // 'w'는 인덱스 0
            map.put('o', 1); // 'o'는 인덱스 1
            map.put('l', 2); // 'l'은 인덱스 2
            map.put('f', 3); // 'f'는 인덱스 3

            boolean flag = true; // 시퀀스의 유효성을 추적하는 플래그
            count[map.get(s.charAt(0))] = 1; // 첫 문자에서 카운트 시작

            // 문자열을 두 번째 문자부터 반복
            for (int i = 1; i < s.length(); i++) {
                int pre = map.get(s.charAt(i - 1)); // 이전 문자의 인덱스
                int cur = map.get(s.charAt(i)); // 현재 문자의 인덱스
                int dif = cur - pre; // 인덱스의 차이 계산

                // 현재 문자가 시퀀스를 리셋하는 경우 체크
                if (dif == -3) {
                    if (check()) { // 현재 카운트가 균형을 이루는지 확인
                        // 새로운 시퀀스를 위해 카운트 배열 리셋
                        count = new int[4];
                        count[0] = 1; // 새로운 시퀀스를 'w'로 시작
                    } else {
                        flag = false; // 카운트가 균형을 이루지 않으면 유효하지 않음
                        break; // 반복문 종료
                    }
                } else {
                    // 문자가 유효한 순서에 있는 경우 ('w' -> 'o' -> 'l' -> 'f')
                    if (dif == 1 || dif == 0) {
                        count[cur]++; // 현재 문자의 카운트를 증가시킴
                    } else {
                        flag = false; // 순서가 깨지면 유효하지 않음
                        break; // 반복문 종료
                    }
                }
            }
            // 카운트가 균형을 이루는지 최종 확인
            if (!check()) {
                flag = false; // 균형을 이루지 않으면 유효하지 않음
            }
            // 유효성 플래그에 따라 결과 출력
            if (flag) {
                System.out.println(1); // 유효한 시퀀스 발견
            } else {
                System.out.println(0); // 유효하지 않은 시퀀스
            }
        }
    }

    // 'w', 'o', 'l', 'f'의 카운트가 모두 같은지 확인하는 메서드
    static boolean check() {
        return count[0] == count[1] && count[1] == count[2] && count[2] == count[3];
    }
}