lv1) 중요한 단어를 스포 방지 [정답률 가장 낮은 문제]

https://school.programmers.co.kr/learn/courses/30/lessons/468370

프로그래머스

 

 

#include <string>
#include <vector>
#include <queue>
#include <map>
#include <iostream>
using namespace std;

// 전략
// - 메시지를 공백 기준으로 단어 단위로 파싱한다.
// - 각 단어가 스포일러 구간과 하나라도 겹치면 스포일러 단어 -> q(큐)에 저장
// - 겹치지 않으면 스포일러 아닌 단어 -> mp(맵)에 저장 (등장 이력 기록용)
// - 이후 큐에서 왼쪽부터 하나씩 꺼내며, mp에 없는 단어일 때만 정답 개수 +1
//   (mp에 이미 있다는 건 "스포일러 아닌 곳에 등장했거나" "이전에 이미 공개된 스포일러 단어"라는 뜻)
map<string, string> mp;
queue<string> q;

int solution(string message, vector<vector<int>> spoiler_ranges) {
    int answer = 0;

    int a = 0;      // 현재 파싱 중인 단어의 시작 인덱스
    string tmp;     // 현재 파싱 중인 단어

    while (1) {
        // 다음 공백 위치 탐색 -> 이 위치 직전까지가 한 단어
        int b = message.find(" ", a);
        int isSpo = 0; // 현재 단어가 스포일러 구간과 겹치는지 여부

        // 마지막 단어 처리 (공백을 더 이상 못 찾은 경우, b == -1)
        if (b == -1) {
            tmp = message.substr(a, message.size() - a);

            // 마지막 단어의 끝 인덱스는 b-1이 아니라 message.size()-1
            // (b가 -1이라 b-1을 그대로 쓰면 -2가 되어 겹침 판정이 항상 실패하는 버그 방지)
            for (int idx = 0; idx < spoiler_ranges.size(); ++idx) {
                // 구간 겹침 조건: a <= end && start <= wordEnd
                // (완전 포함이 아니라 "일부만 겹쳐도" 스포일러 단어로 처리하기 위함)
                if (a <= spoiler_ranges[idx][1] && spoiler_ranges[idx][0] <= message.size() - 1) {
                    q.push(tmp);   // 스포일러 단어 -> 큐에 저장 (공개 순서 보존)
                    isSpo = 1;
                    break;
                }
            }
            if (!isSpo) {
                mp[tmp] = tmp; // 스포일러 아닌 구간에 등장한 단어 기록
            }
            a = b + 1;
            break; // 마지막 단어까지 처리했으므로 파싱 종료
        }

        // 일반 단어 처리 (공백을 찾은 경우)
        tmp = message.substr(a, b - a);

        for (int idx = 0; idx < spoiler_ranges.size(); ++idx) {
            // 구간 겹침 조건: a <= end && start <= b-1
            // 이 조건 덕분에 "may i"처럼 스포일러 구간이 공백을 넘어
            // 여러 단어에 걸쳐 있는 경우도 각 단어마다 올바르게 겹침으로 판정됨
            if (a <= spoiler_ranges[idx][1] && spoiler_ranges[idx][0] <= b - 1) {
                q.push(tmp);
                isSpo = 1;
                break;
            }
        }
        if (!isSpo) {
            mp[tmp] = tmp; // 스포일러 아닌 구간 단어 기록
        }
        a = b + 1; // 다음 단어 시작 위치로 이동
    }

    // 큐에 쌓인 스포일러 단어들을 왼쪽(등장 순서)부터 하나씩 확인
    while (q.size() != 0) {
        string tmp = q.front();

        // mp에 없다는 것은:
        // 1) 스포일러 아닌 구간에서 등장한 적 없고
        // 2) 이전에 이미 공개된 스포일러 단어도 아니라는 뜻
        // -> 두 조건을 모두 만족하므로 "중요한 단어"
        if (!mp.contains(tmp)) {
            mp[tmp] = tmp; // 공개 이력에 추가 (다음번 중복 체크용)
            answer++;
        }
        q.pop();
    }

    return answer;
}

 

 

• 큐 (스포일러 후보): 파싱하면서 스포일러 구간과 하나라도 겹친 단어는 전부 큐에 순서대로 쌓임 (왼쪽→오른쪽 순서 자동 보장)
• 맵 (스포일러 아닌 이력): 스포일러 구간과 전혀 안 겹친 단어들의 텍스트를 미리 다 모아둠
• 판정: 큐에서 하나씩 꺼내면서
  • 이미 맵에 있다 → 스킵 (스포일러 아닌 곳에서 등장했거나, 이전에 이미 공개된 스포일러 단어)
  • 맵에 없다 → 카운트하고, 그 즉시 맵에 추가 (다음 중복 체크를 위해)

 

 

 

조건범위가 핵심이었고 설명은 Claude 이용해 하기 내용으로 대체 

겹침 조건 a <= end && start <= b-1을 그림으로 표현했어요.

핵심 아이디어는 "두 구간이 안 겹친다"의 반대를 생각하는 거예요.

두 구간이 완전히 떨어져 있으려면 둘 중 하나여야 해요:

• 스포일러가 단어보다 완전히 왼쪽에 있음 → end < a
• 스포일러가 단어보다 완전히 오른쪽에 있음 → b-1 < start

이 두 경우가 아닐 때만 겹치는 거니까, 각각을 부정해서 AND로 묶으면:

• end < a가 아니다 → a <= end
• b-1 < start가 아니다 → start <= b-1

그래서 a <= end && start <= b-1이 성립하는 게 곧 "완전히 떨어져 있지 않다 = 겹친다"가 되는 거예요. 위 그림 첫 번째 케이스처럼 살짝만 겹쳐도 이 조건은 true가 됩니다.