[코테] 중요한 단어를 스포 방지

문제 출처

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

프로그래머스

풀이 핵심

• message 내 각 단어의 [start, end] 인덱스 파악하기
• 스포일러 구간 먼저 파악 후,
  • 단어 하나씩 순회하며 비스포 방지 단어 저장(추후 비교)
  • 스포 방지 대상 단어는 별도로 저장
• 이후 스포 방지 대상 단어를 순회하며
  • 비스포 방지 단어에 포함되어 있으면 skip
  • 중요한 단어에 없으면 추가, 결과값에 1 누적

예시 코드 1

import java.util.*;

class Solution {
    public int solution(String message, int[][] spoilers) {

        // 스포일러 위치 표시
        boolean[] isSpoiler = new boolean[message.length()];

        for (int[] spoiler : spoilers) {
            for (int i = spoiler[0]; i <= spoiler[1]; i++) {
                isSpoiler[i] = true;
            }
        }

        Set<String> normalWords = new HashSet<>();
        List<String> spoilerWords = new ArrayList<>();

        int idx = 0;

        while (idx < message.length()) {

            // 공백 건너뛰기
            while (idx < message.length() && message.charAt(idx) == ' ') {
                idx++;
            }

            if (idx >= message.length()) break;

            int start = idx;

            while (idx < message.length() && message.charAt(idx) != ' ') {
                idx++;
            }

            int end = idx - 1;

            String word = message.substring(start, idx);

            boolean containsSpoiler = false;

            for (int i = start; i <= end; i++) {
                if (isSpoiler[i]) {
                    containsSpoiler = true;
                    break;
                }
            }

            if (containsSpoiler) {
                spoilerWords.add(word);
            } else {
                normalWords.add(word);
            }
        }

        Set<String> importantWords = new HashSet<>();

        for (String word : spoilerWords) {
            if (!normalWords.contains(word)) {
                importantWords.add(word);
            }
        }

        return importantWords.size();
    }
}

예시 코드 2

특징: 스포일러 구간을 매 단어마다 순회하지 않도록 누적합을 사용

import java.util.*;

class Solution {

    public int solution(String message, int[][] spoilers) {

        int n = message.length();

        // 차분 배열
        int[] diff = new int[n + 1];

        for (int[] spoiler : spoilers) {
            diff[spoiler[0]]++;

            if (spoiler[1] + 1 < diff.length) {
                diff[spoiler[1] + 1]--;
            }
        }

        // 각 위치가 스포일러인지 계산
        boolean[] isSpoiler = new boolean[n];

        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += diff[i];
            isSpoiler[i] = sum > 0;
        }

        // 스포일러 여부의 누적합
        int[] prefix = new int[n + 1];

        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + (isSpoiler[i] ? 1 : 0);
        }

        Set<String> normalWords = new HashSet<>();
        Set<String> importantWords = new HashSet<>();

        int idx = 0;

        while (idx < n) {

            while (idx < n && message.charAt(idx) == ' ')
                idx++;

            if (idx == n)
                break;

            int start = idx;

            while (idx < n && message.charAt(idx) != ' ')
                idx++;

            int end = idx - 1;

            String word = message.substring(start, idx);

            // [start, end]에 스포일러가 하나라도 있는가?
            boolean hasSpoiler = prefix[end + 1] - prefix[start] > 0;

            if (hasSpoiler) {
                if (!normalWords.contains(word)) {
                    importantWords.add(word);
                }
            } else {
                normalWords.add(word);
                importantWords.remove(word); // 이전에 추가되었더라도 제거
            }
        }

        return importantWords.size();
    }
}