요즘시대에 중요한 단어를 스포 방지 문제 (카카오 기출)

About this offer

소집해제도 다가오고 (사실 아님) 동료도 퇴사하고 적적하다. 퇴근하자마자 집에와서 카카오 기출문제 2문제를 풀었다. 한개는 쉬웠고 이 문제는 레벨 1이라길래 만만하게 봤는데 정말 어려웠다. 처음에는 재밌었다가 나중에 때려치우고 싶은 마음을 겨우겨우 마음 다잡고했다. 평소에 런닝으로 단련된 내가 아니였다면 진작 GPT한테 문제 돌려봤을 것이다. 참고로 난 3km를 30분에 뛴다 어찌 어렵게 풀고나서 GPT한테 검수 요청하니 왜이렇게 어렵게 풀었냐고 뭐라해서 답지 보니깐 진짜 쉽게 풀더라. 요즘시대에 왜 알고리즘을 안보는지 더 체감하게된 요즘이였다. 거두절미하고 바로 들어가보자. 문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/468370 카카오톡은 메시지의 일부를 가려두는 스포 방지 기능을 제공하는데, 스포 방지 기능을 적용한 메시지를 왼쪽에서부터 오른쪽으로 클릭하면서 공개되는 단어들 중, 중요한 단어는 몇개인지를 알아내는 문제이다. 중요한 단어라 함은 다음과 같다. 스포 방지 단어여야 합니다. 메시지의 스포 방지 구간이 아닌 구간(각 구간의 앞·사이·뒤 포함)에 등장한 적이 없어야 합니다. 이전에 공개된 스포 방지 단어와 중복되지 않아야 합니다. 여기서 스포 방지 단어란, 단어의 문자 하나 이상이 스포 방지 구간으로 포함된 단어를 뜻한다. 한마디로 중요한 단어 후보자들이다. 아이디어 핵심은 스포 방지 단어 를 알아내는 것이고 단어는 사이에 공백 으로 구분 지어진다. 우선 메시지에서 공백의 Index를 알아내고, 스포 방지로 가려진 영역인 spoiler_range 로 spoiler_range 의 시작 구간보다 앞에 있고, spoiler_range 의 끝나는 구간보다 뒤에 있는 공백 간의 공간을 구하면 스포 방지 단어 를 구할 수 있다. 그 후 해당 단어가 스포 방지 구간이 아닌 지역에 존재하지 않는가 significWord 에 포함되지 않은 단어인가 를 만족한다면 significWord 에 추가하고 마지막에 significWord 의 길이를 반환하면 된다. 이건 아주 간략화된 풀이 방법이고 테스트케이스가 많기때문에 엣지 케이스를 많이 고민해봐야한다. spoiler_range 가 공백만을 가르킨다거나, 문장이 공백으로 시작할 수 있다. 본인은 문장이 공백으로 시작할 수 있다는걸 고려하지 못했기때문에 많이 헤맸다. 시간복잡도 내가 푼 방식대로하면 O(N^2)이다. 문제 유형 그냥 구현 문제다. 지문을 꼼꼼히 읽고 엣지 케이스들을 최대한 고려해야 한다. 소감 구현 문제의 어려운 점은 이런 엣지 케이스를 고려하는 것에서 나오는것 같다. 위에 요즘시대에 알고리즘이라고 써놓기는 했지만, 문제 해결력과 구조화 능력은 절대 죽지 않는다. 생각의 흐름을 잘 안풀린다고해서 포기하지 않고 차례 차례 밟아나가 보는 것이 문제 해결의 첫 단추라고 느꼈다. 전체 코드 function solution(message, spoiler_ranges){ const messageArray = [...message]; const spaceIndexs= []; for(let i =0; i<messageArray.length; i++){ if(messageArray[i] === ' '){ spaceIndexs.push(i) } } const extractWordChunk = (range) => { const startWordChunkRangePoint = [...spaceIndexs].reverse().find((i)=> i<=range[0]) ?? -1; const endWordChunkRangePoint = spaceIndexs.find((i)=> i>=range[1]) ?? message.length; for(let i = startWordChunkRangePoint + 1 ; i<endWordChunkRangePoint; i++){ messageArray[i] = "*" } return message.slice(startWordChunkRangePoint + 1 ,endWordChunkRangePoint) } const candidateOfSignificWord = []; for(const range of spoiler_ranges){ const chunk = extractWordChunk(range); if(chunk === ''){ continue; } candidateOfSignificWord.push(...chunk.split(' ')) } const coveredMessage = messageArray.join('').split(' '); const significWord = []; for(const candidate of candidateOfSignificWord){ if(!significWord.includes(candidate) && !coveredMessage.includes(candidate)){ significWord.push(candidate) } } return significWord.length; } 참고) GPT의 풀이다. extractWordChunk 함수 자체를 아예 없애버렸다. function solution(message, spoiler_ranges) { const messageArray = [...message]; // 실제 스포가 걸린 문자만 *로 변경 for (const range of spoiler_ranges) { const start = range[0]; const end = range[1]; for (let i = start; i <= end; i++) { if (messageArray[i] !== ' ') { messageArray[i] = '*'; } } } const originalWords = message.split(' '); const coveredWords = messageArray.join('').split(' '); const normalWords = []; const spoilerWords = []; for (let i = 0; i < originalWords.length; i++) { // *가 있으면 이 단어는 스포 단어 if (coveredWords[i].includes('*')) { spoilerWords.push(originalWords[i]); } else { normalWords.push(originalWords[i]); } } const significWords = []; for (const word of spoilerWords) { if (normalWords.includes(word)) { continue; } if (significWords.includes(word)) { continue; } significWords.push(word); } return significWords.length; }```