백준 15886번 [내 선물을 받아줘 2](C++) -yes6686- 티스토리

백준 문제 풀이: 15886 (내 선물을 받아줘)

---

문제 링크: https://www.acmicpc.net/problem/15886

문제 설명:

1차원 선을 따라 n개의 칸이 있으며, 각 칸에는 'E'(동쪽을 바라봄) 또는 'W'(서쪽을 바라봄)를 가진 사람이 있다. 'E'는 오른쪽으로, 'W'는 왼쪽으로 선물을 던진다. 선물은 던진 방향으로 끝까지 직진하며, 선물이 땅에 떨어지는 지점에 상자를 둬야 한다. 최소한의 상자 수를 구하라.

즉, 어떤 사람의 선물이 땅에 떨어지는 지점은 본인의 바라보는 방향에서 방향이 바뀌는 지점이다. 'W' 다음에 'E'가 나오는 순간이 하나의 분리된 구역이 되며, 각 구역마다 최소 하나의 상자가 필요하다.

---

문제 해결 코드

// 15886번: 내 선물을 받아줘
// W에서 E로 방향 전환이 일어나는 지점을 기준으로 선물 상자 수 결정

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    string s;
    cin >> s;

    int ans = 1; // 최소 하나는 무조건 필요
    for (int i = 0; i < n - 1; i++) {
        if (s[i] == 'W' && s[i + 1] == 'E') {
            ans++;  // W에서 E로 바뀌는 지점은 새로운 상자 필요
        }
    }
    cout << ans << '\n';
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명.

• 핵심 알고리즘: 단순 문자열 탐색. 인접한 문자가 'W' → 'E'로 전환되는 횟수를 센다.
• 구현 세부사항:
  • ans = 1: 첫 구간에는 항상 상자 1개 필요
  • if (s[i] == 'W' && s[i+1] == 'E'): 방향이 바뀌는 지점이 새로운 상자 설치 위치
• 시간 복잡도 분석:O(n) - 문자열을 한 번 순회하면서 변화 지점을 파악

---

결과

입력된 방향 문자열에서 'W' 다음 'E'가 나오는 지점 수 + 1이 최소 상자 수가 됩니다.

예시 입력:
8
EEWWWEWW

예시 출력:
2

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!