[백준 Java] 24956번 나는 정말 휘파람을 못 불어

💡문제

[Gold IV] 나는 정말 휘파람을 못 불어 - 24956

문제 링크

성능 요약

메모리: 16368 KB, 시간: 128 ms

---

🤔접근법

범위 체크 및 시간복잡도 예상

• 1 ≤ N ≤ 200,000
• $O(N)$ 이하여야 한다.

풀이법

❌ 접근 방법. 완탐

1. 문자열을 순회하면서 H를 찾는다. → $O(N)$
   1. H를 기준으로 이전 문자열에 W 가 존재하는지 확인 , H를 기준으로 이후 문자열에 E 가 몇개 존재하는지 확인→ $O(2N)$
      1. $_{E의개수}C_i$ , 2 ≤ i ≤ E의개수 → $O(N)$

➡️ 해당 풀이법의 시간 복잡도 : $O(N^3)$

당연히 시간복잡도 초과

❌ 접근 방법. 누적합

1. 문자열을 순회하면서 W의 개수를 누적합 배열로 만든다. → $O(N)$
2. 문자열을 뒤에서 부터 순회하면서 E의 개수를 누적합 배열로 만든다. → $O(N)$
3. 문자열을 순회하면서 H를 찾는다. → $O(N)$
   1. H가 있는 인덱스를 기준으로 W 누적합 배열을 통해 앞에 올 수 있는 W의 위치의 경우의 수를 알아낼 수 있다. → $O(1)$
   2. H가 있는 인덱스를 기준으로 E 누적합 배열을 통해 뒤에 올 수 있는 E의 위치의 경우의 수를 알아낼 수 있다. $_{E의개수}C_i$ , 2 ≤ i ≤ E의개수 → $O(N)$

➡️ 해당 풀이법의 시간 복잡도 : $O(N^2)$
터짐..

⭕ 접근 방법. DP

변수 설명

w : 지금까지 나온 W의 개수, wh : 지금까지 조합 수 있는 WH의 개수, whe : 지금까지 조합할 수 있는 WHE의 개수 , whee : 지금까지 조합할 수 있는 “유사 휫바람 문자열”의 개수

로직 설명

1. 문자열을 순회을 순회한다. → $O(N)$

   • 현재 문제가 W라면 w += 1

   • 현재 문자가 H라면 “WH”를 문자열을 만들 수 있는 개수는 W의 개수만큼 추가 됨으로 wh += w

     WWWH → W가 3개인데 W개수 만큼 WH를 만들수 있다.

     WWWHWH → 첫번째 H에서 W가 3개이고 그때의 W 개수 만큼 WH를 만들 수 있고 두번째 H일 때 두번째 H를 이용해서 만들수 있는 WH의 개수는 W가 4개이고 그때의 W개수만큼 만들수 있으므로 4개이다.
     

   • 현재 문자가 E라면

     1. 지금까지 만들었던 WHEE 문자열에 E를 하나 더 붙여 “유사휘바람문자열”로 만들 수 있으므로 whee*=2

        whee → wheee

        whe_e → whe_ee

        whee_ → whee_e

     2. 지금까지 조합할 수 있는 WHE에 E를 하나 더 붙이면 WHEE로 “유사 휘바람 문자열”에 해당하므로 whee += whe

     3. “WHE”를 만들 수 있는 문자열의 개수는 WH의 개수만큼 추가되므로 whe += wh

        WWWHE → W가 3개이면 WH의 조합개수도 3개이다. 그러면 WHE의 조합의 개수도 3개이다.

        WWWHEE → W가 3개이면 WH의 조합개수도 3개이다. 그러면 첫번째 E를 이용해서 만들수 있는 WHE의 조합의 개수는 3개이다. 그러나 두번째 E를 이용해서 만들 수 있는 WHE의 개수도 WH의 개수와 같으므로 그만큼인 3을 더 추가하게 된다.

➡️ 해당 풀이법의 시간 복잡도 : $O(N)$

---

🤯FAIL

답을 봐서 문제를 푼 경우

• 해결이 되지 않은 부분 : 누적합 배열을 사용해도 시간복잡도가 충분하지 않았다.
• 정답의 로직은 ?
  누적합 배열을 만들지 않고 누적합 변수를 가지고 있다는 것이 다른점이었던거 같다.
  또한 유사 휘바람 문자열에 대한 W, WH, WHE, WHEE 문자열간의 규칙을 찾지 못하였다.
• WH의 문자열 개수는 W의 개수이고 WHE의 문자열 개수는 WH의 개수라는 것이 아이디어가 굉장히 좋았다.

범위 오류

• WHEE*2 하는 과정에서 Int 범위를 넘어 갈 수 있다는 것을 생각하지 못하였다.

---

👩‍💻 코드

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

public class Main_24956 {
    static int N;        // 입력으로 주어지는 문자열의 길이
    static char[] S;     // 입력으로 주어지는 문자열을 저장하는 배열
    static long w;       // 'W'의 개수를 저장하는 변수
    static long wh;      // 'WH'의 개수를 저장하는 변수
    static long whe;     // 'WHE'의 개수를 저장하는 변수
    static long whee;    // '유사 휫바람 문자열'의 개수를 저장하는 변수
    static final long MOD = 1000000007;  // 결과를 나눌 모듈러 값
    static long result;  // 최종 결과를 저장하는 변수

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());  // 문자열의 길이를 입력 받음

        S = new char[N];  // 문자열을 저장할 배열 생성
        S = br.readLine().toCharArray();  // 문자열을 문자 배열로 변환하여 저장

        for (int i = 0; i < N; i++) {
            if(S[i] == 'W'){
                w += 1;  // 'W'가 나오면 'W'의 개수 증가
            } else if (S[i] == 'H') {
                wh += w;  // 'H'가 나오면 'W'의 개수만큼 'WH'의 개수 증가
            } else if (S[i] == 'E') {
                whee = 2 * whee;  // 'E'가 나오면 'WHE'의 개수를 계산하기 위해 현재까지의 '유사 휫바람 문자열'의 개수를 두 배로 증가
                whee += whe;  // 이전까지의 'WHE'의 개수를 더함
                whee %= MOD;  // 모듈러 연산을 통해 값의 범위를 제한
                whe += wh;  // 현재까지의 'WH'의 개수를 더함
            }
        }

        System.out.println(whee);  // 결과 출력
    }
}