중요한 단어를 스포 방지

문제

카카오톡의 스포 방지 기능이 적용된 메시지에서 '중요한 단어'의 개수를 찾는 문제입니다. 단어는 공백으로 구분되며, 단어의 문자 중 하나 이상이 스포 방지 구간에 포함되면 스포 방지 단어로 간주합니다. 스포 방지 구간을 클릭해 단어가 공개되었을 때, 아래 조건을 모두 만족하면 중요한 단어입니다.

1. 스포 방지 단어여야 합니다.
2. 메시지의 스포 방지 구간이 아닌 곳(일반 텍스트 구간)에 등장한 적이 없어야 합니다.
3. 이전에 공개된 중요한 단어와 중복되지 않아야 합니다.

• 입력: 메시지 문자열 message (길이 20,000 이하), 스포 방지 구간 배열 spoiler_ranges
• 출력: 조건을 만족하는 중요한 단어의 총 개수를 반환합니다.

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

풀이: 문자열 인덱싱과 HashSet을 활용한 분류

문자열의 원본 인덱스를 추적하며 스포일러 여부를 마킹하고, HashSet을 통해 일반 단어 등장 여부와 중복을 동시에 걸러내는 효율적인 풀이입니다.

• 스포일러 구간 마킹: 메시지의 길이와 동일한 크기의 boolean 배열 spo를 선언하여, spoiler_ranges에 해당하는 모든 인덱스를 true로 갱신합니다. 이를 통해 특정 문자가 스포일러에 포함되는지 O(1) 시간에 확인할 수 있습니다.
• 단어 분리 및 위치 추적: message.split(" ")을 이용해 단어 단위로 분리합니다. 단어를 순회할 때마다 원본 문자열에서의 시작 인덱스(idx)를 유지하며, 단어 검사가 끝날 때마다 idx += word.length() + 1 (단어 길이 + 공백 1칸)을 더해 다음 단어의 위치를 추적합니다.
• 스포일러/일반 단어 집합 분리: * 각 단어의 문자 인덱스 범위(idx ~ idx + word.length() - 1) 내에 spo 배열 값이 하나라도 true라면 이 단어는 스포일러 단어입니다. 중복을 방지하기 위해 set1에 추가합니다.
  • 만약 스포일러 문자가 단 하나도 없다면 이는 일반 텍스트로 노출된 단어이므로 set2에 추가합니다.
• 중요한 단어 필터링: set1(스포일러 단어 집합)을 순회하면서, 해당 단어가 set2(일반 단어 집합)에도 존재하는지 확인합니다. 일반 단어로도 등장한 적이 있다면 조건 2에 위배되므로 건너뛰고(continue), 그렇지 않은 단어만 카운트(ans++)하여 반환합니다.

코드

import java.util.*;

class Solution {
    public int solution(String message, int[][] spoiler_ranges) {
        boolean[] spo = new boolean[message.length()];
        
        // 스포일러 구간을 boolean 배열에 마킹
        for (int[] range : spoiler_ranges) {
            for (int i = range[0]; i <= range[1]; i++) {
                spo[i] = true;
            }
        }
        
        String[] words = message.split(" ");
        int idx = 0;
        Set<String> set1 = new HashSet<>(); // 스포일러 구간에 포함된 단어들
        Set<String> set2 = new HashSet<>(); // 스포일러 구간 밖(일반 구간)에 등장한 단어들
        
        for (String word : words) {
            boolean flag = true;
            
            // 현재 단어의 인덱스 구간을 돌며 스포일러 문자 포함 여부 확인
            for (int i = idx; i < word.length() + idx; i++) {
                if (spo[i]) {
                    set1.add(word);
                    flag = false;
                    break;
                }
            }
            
            // 스포일러 문자가 하나도 없으면 일반 구간 단어
            if (flag) {
                set2.add(word);
            }
            
            // 다음 단어의 시작 인덱스 (단어 길이 + 공백 1칸)
            idx = idx + word.length() + 1;
        }
        
        int ans = 0;
        // 스포일러 단어 중 일반 구간에 등장하지 않은 단어 개수 세기
        for (String s : set1) {
            if (set2.contains(s)) continue;
            ans++;
        }

        return ans;
    }
}

알고리즘 분류

구현 (Implementation), 문자열 (String), 해시를 사용한 집합과 맵 (Hash Set)