본문 바로가기

TIL

[2021-12-30,31] 프로그래머스 연습 + 정규표현식

어제 프로그래머스에서 코딩테스트 연습에서 신규 아이디 추천 문제를 풀었다. 매개변수로 받은 문자열 new_id를 문자열을 규칙에 따라 가공하여 추천 아이디를 반환하는 문제였는데, 학교에서는 C로만 알고리즘문제를 풀었었기 때문에, 익숙하진 않지만 이것저것 검색해가면서 재밌게 문제를 풀었다.

class Solution {
    
    public String solution(String new_id) {
        String answer = "";
        String processingId = new_id;

        processingId = executeStep1(processingId);    //대문자 -> 소문자
        processingId = executeStep2(processingId);    //알파벳,.,-,_ 문자를 제외한 문자 제거
        processingId = executeStep3(processingId);    //연속적인 '.' 제거
        processingId = executeStep4(processingId);    //맨앞뒤 '.' 제거
        processingId = executeStep5(processingId);    //빈문자열 처리
        processingId = executeStep6(processingId);    //길이 16이상일 때 자르기
        processingId = executeStep7(processingId);    //길이 2 이하일 때 처리

        answer = processingId;

        return answer;
    }

    //대문자 -> 소문자
    private String executeStep1(String id){
        return id.toLowerCase();
    }

    //알파벳,.,-,_ 문자를 제외한 문자 제거
 private String executeStep2(String id){
        char[] charArrayId = id.toCharArray();

        int index = 0;
        for(char ch: charArrayId){
            if(!Character.isAlphabetic(ch) && !Character.isDigit(ch)){
                if(ch != '-' && ch != '_' && ch !='.'){
                    charArrayId[index] = ' ';
                }
            }
            index++;
        }

        return String.valueOf(charArrayId).replace(" ","");
    }

    //연속적인 '.' 제거
    private String executeStep3(String id){
        StringBuilder processingId = new StringBuilder(id);
        int startDotsIndex = processingId.indexOf("..");

        while(processingId.indexOf("..") != -1){
            processingId = processingId.replace(startDotsIndex,startDotsIndex+2,".");
            startDotsIndex = processingId.indexOf("..");
        }

        return processingId.toString();
    }

    //맨앞뒤 '.' 제거
    private String executeStep4(String id) {
        if(id.length() != 0) {
            if(id.charAt(0) == '.') id = new StringBuilder(id).deleteCharAt(0).toString();
        }
        if(id.length() != 0) {
            if(id.charAt(id.length() - 1) == '.') id = new StringBuilder(id).deleteCharAt(id.length() - 1).toString();
        }

        return id;
    }

    //빈문자열 처리
    private String executeStep5(String id) {
        if(id.length() == 0) return new StringBuilder(id).append('a').toString();

        return id;
    }

    //길이 16이상일 때 자르기
    private String executeStep6(String id) {
        if(id.length() > 15) id = id.substring(0,15);
        if(id.charAt(id.length() - 1) == '.') id = id.substring(0,id.length()-1);

        return id;
    }

    //길이 2 이하일 때 처리
    private String executeStep7(String id) {
        if(id.length() < 3){
            StringBuilder processingId = new StringBuilder(id);
            char lastChar = processingId.charAt(processingId.length() - 1);
            while(processingId.length() < 3){
                processingId.append(lastChar);
            }

            return processingId.toString();
        }

        return id;
    }
}

 

문제를 풀면서 처음으로 StringBuilder 클래스를 사용해봤다. String 문자열은 불변하는 객체이기 때문에 덧셈 연산을 하게 되면 문자열 객체가 있는 힙 영역에 더한 문자열이 추가되는게 아니라 새로운 공간에 할당 된다고 한다. 때문에 많은 문자열 연산이 필요 하다면 새로운영역을 할당하지 않고 문자열을 수정할 수 있는 StringBuilder를 꼭 사용해야한다.

 

얼마나 성능에서 차이나는지 간단하게 for문에서 index 를 추가시키는 코드를 테스트 해봤는데 거의 1000배 내외의 속도 차이가 있어서 처음엔 내가 코드를 잘못 짠건가 싶었다.

String StringBuilder 문자열 추가 연산 속도 비교

단순히 StringBuilder 클래스를 사용해서 문자열 연산을 했을 뿐인데 이정도로 성능의 차이를 낸다는 것이 많이 흥미로웠다. 다음번에 시간내서 String이 왜 연산마다 새로운 객체를 생성하는지, StringBuilder는 어떻게 새로운 객체를 생성하지 않고 문자열 연산을 수행하는지, 그리고 StringBuffer 에 대해서도 정리를 한번 해야겠다. 

 

어쨌든 문제를 다 풀고 제출한 후에 다른사람들이 푼 풀이도 한번 보았다. 그 중에 많은 추천 수를 받은 코드들을 보니 대부분 정규표현식을 통해 문제를 풀고 있었다.

 

또한 정규식을 사용하니까 내가 짠 코드보다 거의 절반 이상 간결하게 코드길이가 줄어드는 것을 확인했다.

 

그동안 주민번호, 휴대번호, 이메일 등 서비스를 만들 때 정규식이 필요하면 검색해서 긁어오는 방식으로만 사용했었는데 이번에는 공부해보고 직접 정규식을 짜서 문제를 풀어보았다. 코드는 다음과 같다.

class Solution {
    
    public String solution(String new_id) {

        return new RecommendationID(new_id)
                .toLowerCase()
                .removeUnavailableLetter()
                .changeDotsIntoOneDot()
                .removeFrontDot()
                .removeBackDot()
                .insertIfEmpty()
                .removeIfMoreThan15()
                .addIfLessThan2()
                .get();
    }

    private class RecommendationID{

        private String id;

        private String get(){
            return this.id;
        }
        public RecommendationID(String id){
            this.id = id;
        }

        private RecommendationID toLowerCase(){
            this.id = id.toLowerCase();
            return this;
        }

        private RecommendationID removeUnavailableLetter(){
            this.id = id.replaceAll("[^a-zA-Z0-9_.-]","");
            return this;
        }

        private RecommendationID changeDotsIntoOneDot(){
            this.id = id.replaceAll("[.]{2,}",".");
            return this;
        }

        private RecommendationID removeFrontDot(){
            this.id = id.replaceAll("^[.]","");
            return this;
        }

        private RecommendationID removeBackDot(){
            this.id = id.replaceAll("[.]$","");
            return this;
        }

        private RecommendationID insertIfEmpty(){
            if(this.id.equals("")) this.id = String.valueOf("a");
            return this;
        }

        private RecommendationID removeIfMoreThan15(){
            if(this.id.length() >= 16) this.id = this.id.substring(0,15).replaceAll("^[.]|[.]$","");
            return this;
        }

        private RecommendationID addIfLessThan2(){
            while(this.id.length() <= 2) this.id += this.id.charAt(this.id.length()-1);
            return this;
        }
    }
}

다른분들의 코드도 참고하고 이것저것 생각해서 짜보았다. 더 짧게 짜볼 수도 있었지만 solution 메서드에서 저렇게 메서드들을 연속으로 호출하면서 짜는 코드가 왠지 멋있어 보여서 조금 길게 짰다. 그럼에도 기존 코드보다 30줄 정도 코드가 줄어든 것을 알 수 있다.

 

근데 웬걸 깔끔해진만큼 속도도 최소한 같거나 빨라지지 않을까 했는데 기존 코드보다 훨씬 성능이 떨어졌다. replaceAll 메서드를 호출할 때 마다 complie 메서드를 통해 아래와 같이 Pattern 객체를 새로 생성하게 되는데 한번 사용하면 바로 GC의 대상이 되기 때문에 비효율적인 것이다.

 

그래서 아래 코드와 같이 Solution 클래스에 정규식 Pattern 객체를 static final로 선언해서 진행해보았다. Pattern 객체를 컴파일 타임에 할당해놓고 원래처럼 계속 객체를 생성하는 것이 아니라 이미 할당된 compile 된 Pattern 객체를 가져다 쓰게 한 것이다.

import java.util.regex.Pattern;

class Solution {

    private static final Pattern letterRegex = Pattern.compile("[^a-zA-Z0-9_.-]");
    private static final Pattern DotsRegex = Pattern.compile("[.]{2,}");
    private static final Pattern frontDotRegex = Pattern.compile("^[.]");
    private static final Pattern backDotRegex = Pattern.compile("[.]$");
    private static final Pattern bothEndsDotsRegex = Pattern.compile("^[.]|[.]$");

    public String solution(String new_id) {

        return new RecommendationID(new_id)
                .toLowerCase()
                .removeUnavailableLetter()
                .changeDotsIntoOneDot()
                .removeFrontDot()
                .removeBackDot()
                .insertIfEmpty()
                .removeIfMoreThan15()
                .addIfLessThan2()
                .get();
    }

    private class RecommendationID{

        private String id;

        private String get(){
            return this.id;
        }
        public RecommendationID(String id){
            this.id = id;
        }

        private RecommendationID toLowerCase(){
            this.id = id.toLowerCase();
            return this;
        }

        private RecommendationID removeUnavailableLetter(){
//            this.id = id.replaceAll("[^a-zA-Z0-9_.-]","");
            this.id = letterRegex.matcher(this.id).replaceAll("");
            return this;
        }

        private RecommendationID changeDotsIntoOneDot(){
//            this.id = id.replaceAll("[.]{2,}",".");
            this.id = DotsRegex.matcher(this.id).replaceAll(".");

            return this;
        }

        private RecommendationID removeFrontDot(){
//            this.id = id.replaceAll("^[.]","");
            this.id = frontDotRegex.matcher(this.id).replaceAll("");

            return this;
        }

        private RecommendationID removeBackDot(){
//            this.id = id.replaceAll("[.]$","");
            this.id = backDotRegex.matcher(this.id).replaceAll("");

            return this;
        }

        private RecommendationID insertIfEmpty(){
            if(this.id.equals("")) this.id = String.valueOf("a");
            return this;
        }

        private RecommendationID removeIfMoreThan15(){
            if(this.id.length() >= 16) {
//                this.id = this.id.substring(0,15).replaceAll("^[.]|[.]$","");
                this.id = bothEndsDotsRegex.matcher(this.id.substring(0,15)).replaceAll("");

            }
            return this;
        }

        private RecommendationID addIfLessThan2(){
            while(this.id.length() <= 2) this.id += this.id.charAt(this.id.length()-1);
            return this;
        }
    }

}

 

하지만 몇몇 테스트에서 약간 빨라졌을 뿐, 예상했던 것 처럼 시간이 드라마틱 하게 빨라지지는 않았다. 프로그래머스에서 this 를 출력해본 결과 한 번 Solution 객체를 생성하고 연속적으로 solution 메서드를 실행하는 것은 확인 했으므로 정규표현식 자체의 성능 문제인 것 같다. 아래 캡쳐는 왼쪽부터 차례대로 정규식을 쓰지 않은 초기 코드, 정규표현식 적용 코드, 정규표현식 + Pattern 객체 static final 로 선언한 코드 이다.

정규식을 쓰지 않은 초기 코드  /  정규표현식 적용 코드  /   정규표현식 + Pattern 객체 static final 로 선언한 코드

 

결론

깔끔하고 좋아보여서 정규식을 써봤는데 생각보다 많이 느렸다. 앞으로 공부하면서 생각이 바뀔수도 있지만 이메일처럼 보편적으로 많이 쓰는 경우와  많은 조건문으로 가독성을 해치는 복잡한 문자열을 체크해야하는 경우를 제외하고 웬만하면 정규표현식을 사용하지 않는 것이 좋지 않을까? 하는 생각이 들었다. 또 수천, 수만줄 이상의 문자열을 처리해야 한다면 시간이 너무 많이 걸릴 것이므로 다른 방법을 생각해보는게 좋겠다. 별개로 코딩테스트 문제들의 경우 정규식을 모르면 시간을 너무 소요하게 되는 문제들이 있기때문에 사용법은 꼭 숙지하고 있어야할 것 같다.