[Algorithm/Java] 백준 15886번 - 내 선물을 받아줘 2

---

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

---

🔍 문제 풀이

풀이 과정

문자열을 앞에서부터 순회하며 ‘E’ 다음에 ‘W’가 있는 위치 개수를 세는 것이 핵심이다.

‘E’는 오른쪽, ‘W’는 왼쪽으로 이동하고 절대 멈추지 않는다.

구사과가 무조건 선물 하나를 지나가게 하려면, 선물을 반드시 지나치는 칸에만 놓아야 한다.

E → W 일 때, 양쪽에서 온 구사과가 모두 그 칸을 지나치므로, E → W가 나오는 지점에만 선물을 놓으면 최소 개수로 모든 출발 위치를 커버할 수 있다.

헷갈린점

처음엔 count 배열을 사용해 구사과가 이동하면서 영향을 주는 위치에 값을 누적하여, 가장 많이 방문한 위치의 개수를 정답으로 구하려 했다.

하지만 가장 많이 방문된 지점을 찾는 게 아니라, 구사과가 어딘가에서 출발해도 반드시 지나치는 “교차 지점”을 찾으면 되는 문제였다.

💻 전체 코드

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

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

        int n = Integer.parseInt(br.readLine());
        String str = br.readLine();

        int result = 0;
        for (int i = 0; i < n - 1; i++) {
            if (str.charAt(i) == 'E' && str.charAt(i + 1) == 'W') {
                result++;
            }
        }

        System.out.println(result);
    }
}