122. 브라이언의 고민 (프로그래머스) [JAVA]

문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/1830

코딩테스트 연습 - 브라이언의 고민

문제

카카오스토리의 개발자 브라이언에게 최근 고민이 생겼다. 하루에도 수백만 명이 사용하는 서비스답게 사람들이 많이 보는 글에 광고성 댓글을 달아 불쾌감을 유발하는 사용자가 증가하고 있는데, 신고를 받은 글이 광고글인지를 운영자가 판단하여 차단하는 시스템으로는 빠르게 늘어나는 광고글을 처리하기 어렵기 때문이다. 그래서 브라이언은 신고된 글이 광고글인지를 자동으로 판단하는 시스템을 만들었다. 이제 사용자가 광고글을 보고 신고하면 그 글이 광고글로 판단된 경우 자동으로 차단된다! 드디어 깨끗한 카카오스토리를 만들었다는 기쁨도 잠시, 광고글을 올리는 사람들이 자동 차단 시스템을 회피할 수 있는 방법을 찾기 시작했고, 얼마 지나지 않아 광고 문구 사이에 특수문자를 넣으면 차단되지 않는다는 점이 알려지게 되었다. 즉, 아래와 같은 식으로 작성하면 광고글 차단이 적용되지 않는다.

♚프☆렌☆즈☆레☆이☆싱♚★사전예약★진행중
$지금$예약시♜이모티콘♜100%※증정※
★라이언★카트♨전원♨획@득@기@회
즉시이동 http://...

생각지 못한 광고글 패턴에 당황하던 브라이언은 광고글이 일정한 규칙에 의해 만들어진다는 사실을 알게 되었는데, 그 규칙은 다음과 같다.
(아래 설명 및 그 이후의 내용에서 영문 대문자는 원래 문구, 소문자는 특수기호를 의미한다.)

• 광고글은 원래 문구에 다음 규칙을 적용하여 만들 수 있다.
  • (규칙 1) 특정 단어를 선택하여 글자 사이마다 같은 기호를 넣는다. ex) HELLO -> HaEaLaLaO
  • (규칙 2) 특정 단어를 선택하여 단어 앞뒤에 같은 기호를 넣는다. ex) WORLD -> bWORLDb
  • 위의 두 가지 규칙은 한 단어에 모두 적용될 수 있지만 같은 규칙은 두 번 적용될 수 없다.
  • 한 번 쓰인 소문자(특수기호)는 다시 쓰일 수 없다.
• 마지막으로 원래 문구에 있던 공백을 제거한다.

위의 규칙에 따라, HELLO WORLD는 다음의 광고 문구로 변환될 수 있다.

• HELLOWORLD (기호 삽입 없이 마지막 규칙인 공백 제거만 적용되었다.)
• HaEaLaLaObWORLDb (첫 번째 단어에는 규칙 1이, 두 번째 단어에는 규칙 2가 적용되었다.)
• aHbEbLbLbOacWdOdRdLdDc (모든 단어에 모든 규칙이 적용되었다.)

단, 아래의 문구는 올바르게 변환된 광고문구가 아니다.

• aHELLOa bWORLDb (공백이 제거되어야 한다.)
• HaEaLaLObWORLDb (규칙 1은 단어의 모든 글자 사이에 적용되어야 한다. 단, 이 문장은 원문이 HELL O WORLD인 경우 올바른 변환이다.)
• aHELLOWORLDa (규칙 2는 한 단어에 적용되어야 한다. 단, 이 문장은 원문이 HELLOWORLD인 경우 올바른 변환이다.)
• HaEaLaLaOWaOaRaLaD (첫 번째 단어에 쓰인 기호 a를 두 번째 단어에 쓸 수 없다.)
• abHELLObaWORLD (하나의 규칙을 같은 단어에 두 번 적용할 수 없다.)

신고된 글에 대해 위 규칙이 적용되기 전 문구를 찾을 수 있으면 자동 차단 시스템을 다시 온전하게 실행할 수 있게 된다. 카카오스토리가 광고글 없는 깨끗한 공간이 될 수 있도록 프로그램을 만들어보자.

입력

입력은 문자열 변수 sentence로 주어진다. 이 문자열은 영문 대소문자로만 이루어져 있으며, 길이는 1,000 이하이다.

출력

입력으로 주어진 광고 문구의 규칙 적용 전 원래 문구를 리턴한다. 단 원래 문구의 경우 문장 앞뒤의 공백이 없어야 하며, 단어 사이의 공백은 한 글자여야 한다. 가능한 답이 여러 가지인 경우 그중 하나를 리턴하면 된다. 규칙에 따른 변환으로 만들 수 없는 문자열이 입력된 경우에는 소문자로 invalid를 리턴한다.

 

풀이

광고인지를 탐색하는 과정은 다음과 같다.

1. 우선 각 소문자의 위치를 구한다.
2. 구한 소문자를 순서대로 탐색하며 개수에 따라 규칙 1인지, 2인지 판단한다.
3. 각 규칙에 따라 올바른 단어인지의 여부와 단어의 시작, 끝 위치를 구한다.
4. 소문자를 제거하고 단어를 추가한다

사실 카카오의 간략한 해설을 보고도 이해를 못해서, 아래의 블로그를 보고 이해할 수 있었다. (정말 잘 정리해주셨다)

풀이 -> https://hyunjiishailey.tistory.com/301

[프로그래머스(Programmers)] (Lv3) 브라이언의 고민

 

풀이 이외로 참고할 팁은 우선 기존의 HashMap은 키가 들어오는 순서를 보장하지 못한다는 점인데,

LinkedHashMap은 put 연산에서 입력 순서를 보장해준다는 것이다.

 

또한, 소문자를 변환하는 것을 일일히 배열을 탐색하는 것이 아니라

String.replaceAll("[a-z]","")으로 해결하는 것과,

이렇게 변환한 문자열과의 길이비교를 통해 굳이 for문을 돌리지 않고 소문자의 개수를 파악할 수 있다는 것이다.

 

마지막으로 위의 4가지 단계만으로는 문제 해결에 성공할 수 없다.

문자열을 자르고 붙일때 발생하는 잔 에러들이 많아서 모두 체크해줘야 하는데,

이를 try - catch문으로 처리하여 미처 생각하지 못한 Exception들에 대해서 모두 invalid 처리를 함으로써 편하게 해결한 점이 인상깊었다.

 

코드 (JAVA)

import java.util.*;

public class Solution {

    public String solution(String sentence) {
        StringBuilder answerList = new StringBuilder();
        //HashMap과 달리 입력 순서 보장
        LinkedHashMap<Character, ArrayList<Integer>> lowerCount = new LinkedHashMap<>();
        String invalid = "invalid";
        try {
            int size = sentence.length();

            //소문자의 각 종류 / 위치 파악
            for(int i=0; i<size; i++){
                char c = sentence.charAt(i);

                if(Character.isLowerCase(c)){
                    if(!lowerCount.containsKey(c)){
                        lowerCount.put(c, new ArrayList<Integer>());
                    }
                    lowerCount.get(c).add(i);
                }
            }

            int stringIdx = 0;
            int startChar, endChar;
            int lastStartChar = -1, lastEndChar = -1;
            int startWord = 0, endWord = 0;
            int lastStartWord= -1, lastEndWord = -1;
            int count, distance;
            int rule = 0;

            ArrayList<Integer> temp;
            for(char c : lowerCount.keySet()){
                temp = lowerCount.get(c);
                count = temp.size();
                startChar = temp.get(0);
                endChar = temp.get(count-1);


                //AaA, AaAaAaA...
                if(count == 1 || count >= 3){
                    for(int i=1; i<count; i++){
                        //간격 2 넘어가면 x
                        if(temp.get(i) - temp.get(i-1) != 2) return invalid;
                    }
                    rule = 1;
                }

                else if (count == 2){
                    distance = endChar - startChar;

                    //다른 기호 안에 있음 (규칙 2와 겹침)
                    if(distance == 2 && (endChar < lastEndChar && startChar > lastStartChar)){
                        rule = 1;
                    }
                    else if(distance >= 2){
                        rule = 2;
                    }
                    //소문자 연속은 x
                    else  return invalid;
                }

                //규칙에 따른 예외
                if(rule == 1){
                    //기호 위치에서 앞뒤로 한칸씩
                    startWord = startChar -1;
                    endWord = endChar+1;

                    //이전 단어 안에 포함되어 있는 경우
                    if(lastStartWord < startWord && lastEndWord > endWord){
                        //규칙 2 아니면 안됨
                        if(startChar - lastStartChar  == 2 && lastEndChar - endChar == 2){
                            continue;
                        }
                        else return invalid;
                    }
                }

                else if (rule == 2){
                    startWord = startChar;
                    endWord = endChar;
                    //규칙 2는 중복되면 안됨
                    if(lastStartWord < startWord && lastEndWord > endWord) return invalid;
                }

                if(lastEndWord >= startWord) return  invalid;

                //소문자 등장 이전에 존재하던 앞의 단어 추가
                if(stringIdx < startWord){
                    answerList.append(makeWord(sentence,stringIdx,startWord-1));
                    answerList.append(" ");
                }
                answerList.append(makeWord(sentence,startWord,endWord));
                answerList.append(" ");
                lastStartWord = startWord;
                lastEndWord = endWord;
                lastStartChar = startChar;
                lastEndChar = endChar;
                stringIdx = endWord+1;
            }
            //뒤에 남는 단어들도 더하기
            if(stringIdx < size){
                answerList.append(makeWord(sentence,stringIdx,size-1));
            }
        }
        catch (Exception e){
            return invalid;
        }
        return answerList.toString().trim();
    }

    public String makeWord(String sentence, int start, int end){
        String word = sentence.substring(start, end+1);
        return word.replaceAll("[a-z]","");
    }
}

 

결과