[회고] 지난 문제를 다시 풀어보며, 좋은 코드에 대해

글을 작성하는 이유

최근 문제를 풀면서 키워드 유추 -> 접근법 생각 -> 검증 -> 코드로 구현 순으로 풀이를 진행하는 연습을 하고 있습니다.

이 과정에서 접근법에 대해 코드로 구현하는게 잘 되지 않는다고 느껴져서 이유를 생각해보고, 어떻게 개선해나갈지 정리하고자 글을 작성하게 되었습니다.

 

참고 문제

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

 

 

키워드 유추

• 0과 1로 이루어진 어떤 문자열 x
• x를 최대한 사전 순으로 앞에 오도록
• x에 있는 "110"을 뽑아서
• 임의의 위치에 삽입

접근법 생각

• 문자열 x에서 "110"을 추출
  • 추출 후 남은 문자열에 대해서도 계속해서 추출
• 최종적으로 남은 문자열에서 마지막 0의 위치를 탐색
• 추출한 "110"을 순차적으로 마지막 0 뒤에 삽입 후 결과 return

검증

사전 순 특성 상 0이 최대한 앞에 많이 배치되어 있어야 함.

"110"을 뽑을 때 새로 생기는 "110"은 있지만, 삽입으로 인한 생성은 없음.

남은 문자열에서 0앞에 1이 2개 이상 있을 수 없음. (있다면 "110"이 되므로)

 

코드로 구현

여기까지 올 경우 제가 코드로 구현해야 하는 부분은 다음과 같습니다.

1. 문자열 x에 대해서 "110"을 계속해서 추출하는 로직
2. 남은 문자열 x에서 마지막 0의 위치를 탐색하는 로직
3. 탐색된 위치에서 "110"을 순차적으로 삽입해서 새로운 문자열을 만드는 로직

각 구현 로직에 대해서 저의 첫 방식과 개선할 수 있는 포인트에 대해서 찾아보겠습니다.

---

문자열 idx에 대해서 "110" 추출 메서드

// "110"추출 메서드
    private static String extract110(String idx) {
        Stack<Character> st = new Stack<>();
        
        for(int i=0; i<idx.length(); i++) {
            // i를 기준으로 앞 두 개의 문자를 비교
            if(st.size() >= 2 && idx.charAt(i) == '0') {
                char mid = st.pop();
                char first = st.pop();
                if(first == '1' && mid == '1' && idx.charAt(i) == '0') continue;
                else {
                    st.push(first);
                    st.push(mid);
                    st.push(idx.charAt(i));
                }
            }
            else {
                st.push(idx.charAt(i));
            }
        }
        
        // 효율적인 문자열 연산을 위한 StringBuilder 활용
        StringBuilder sb = new StringBuilder();
        for(char x : st) {
            sb.append(x);
        }
        
        return sb.toString();
    }

 

알고리즘 문제를 푸는 환경은 주로 단일 쓰레드 환경이므로 StringBuffer대신 StringBuilder를 활용하여 문자열 연산을 수행했습니다.

 

또한 "110"을 추출할 때 마다 남은 문자열을 이어 붙이고, 첫 인덱스부터 재탐색하는 O(N^2)과정을 줄이기 위해 Stack을 활용하여 O(N)의 시간복잡도로 수행하도록 했습니다.

 

코드의 간결을 위해 i를 중간 인덱스로 두는게 아닌 마지막 인덱스로 두어 가독성을 향상시키고자 했습니다.

 

개선점 1. 추가적인 push()과정을 없앨 수는 없을까?

해당 메서드에서 수행되는 주요 과정은 문자열에 대해 특정 값을 찾고 그 값을 제외한 나머지값을 구하는 것입니다.

 

사실 처음에는 String.substring()메서드를 통해서 3개의 글자를 계속 비교하며 문자열 삽입/삭제를 진행하려 했습니다.

Stack을 활용하는 방식도 스터디 토론으로 적용한 방식이였죠.

substring의 경우 문자열 길이 N에 대해 O(N)복잡도가 나옵니다.

이것을 N-2회 진행하게 되면 탐색에만 O(N^2)의 시간복잡도가 소요됩니다. 이후 추가적인 문자열 제거/삽입 과정을 생각하면 너무나도 비효율적입니다.

 

현재 Stack 활용도 O(N)으로 괜찮아보이지만 탐색을 위해 두번의 pop()과정과 miss의 경우 다시 push()되는 과정이 비효율적으로 보입니다.

 

이를 개선하기 위해 ArrayList로만 바꿔도 개선이 가능할 것으로 보입니다.

다음은 ArrayList를 활용한 코드입니다.

// "110"추출 메서드
    private static String extract110(String idx) {
        List<Character> str = new ArrayList<>();
        
        for(int i=0; i<idx.length(); i++) {
            if(str.size() >= 2 && idx.charAt(i) == '0') {
                if(str.get(str.size()-2) == '1' && str.get(str.size()-1) == '1') {
                    str.remove(str.size()-1);
                    str.remove(str.size()-1);
                }
                else {
                    str.add(idx.charAt(i));
                }
            }
            else {
                str.add(idx.charAt(i));
            }
        }
        
        // 효율적인 문자열 연산을 위한 StringBuilder 활용
        StringBuilder sb = new StringBuilder();
        for(char x : str) {
            sb.append(x);
        }
        
        return sb.toString();
    }

 

이제 스택과 리스트 두 개의 결과를 비교해보겠습니다.

Stack

 

ArrayList

 

Stack -> List를 통해 시간복잡도와 공간복잡도를 생각보다 줄일 수 있었고, 코드 가독성 또한 한단계 상승시킬 수 있었습니다.

 

그러나 ArrayList로 변경해도 삽입과 삭제 연산이 일부분 남아있어서 이 과정이 시간복잡도에 영향을 줄 수도 있습니다.

이를 개선하기 위해 추가적인 Character배열과 pointer를 활용할 수 있습니다.

"110"을 앞에서부터 제거해나가기 때문에 pointer를 관리함으로써 남은 문자열을 계산할 수 있는데요.

다음은 개선한 코드입니다.

// "110"추출 메서드
    private static String extract110(String idx) {
        char[] chars = idx.toCharArray();
        char[] arr = new char[chars.length];
        
        int p = 0;
        
        for(int i=0; i<chars.length; i++) {
            arr[p] = chars[i];
            if(p >= 2) {
                if(arr[p-2] == '1' && arr[p-1] == '1' && arr[p] == '0') {
                    p -= 3;
                }
            }
            p++;
        }
        
        
        // 효율적인 문자열 연산을 위한 StringBuilder 활용
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<p; i++) {
            sb.append(arr[i]);
        }
        
        return sb.toString();
    }

위 코드에 대한 결과는 다음과 같습니다.

배열 + pointer

시간복잡도가 꽤 많이 개선된걸 볼 수 있습니다.

이외에도 개선할 수 있는 부분이 있을 수도 있겠지만 이정도면 초기 Stack코드에서 충분한 개선을 했다고 볼 수 있을 것 같습니다.

---

0 위치 탐색 및 삽입 메서드

// "110"추출을 제외한 나머지 로직에 대한 메서드
    private static String process(String idx) {
        String remainStr = extract110(idx);
        
        int cnt110 = (idx.length() - remainStr.length()) / 3; //추출된 "110"의 개수
        
        //삽입위치 탐색
        int zeroIdx = 0;
        for(int i=0; i<remainStr.length(); i++) {
            if(remainStr.charAt(i) == '0') {
                zeroIdx = i+1;
            }
        }
        
        StringBuilder res = new StringBuilder();
        for(int i=0; i<zeroIdx; i++) {
            res.append(remainStr.charAt(i));
        }
        for(int i=0; i<cnt110; i++) {
            res.append("110");
        }
        for(int i=zeroIdx; i<remainStr.length(); i++) {
            res.append(remainStr.charAt(i));
        }
        return res.toString();
    }

 

기존 글자 수와 추출된 글자 수의 차이를 통해 개수를 탐색했습니다.

 

또한 남은 문자열의 순회를 통해 0의 마지막 인덱스 위치를 탐색했습니다.

 

결합 과정에서도 마찬가지로 StringBuilder를 사용하여 수행했습니다.

1. 마지막 0의 위치까지는 기존 문자열을 추가
2. 이후 "110"의 개수만큼 추가
3. 남은 문자열 추가

마지막으로 만들어진 문자열에 대한 String 객체를 return했습니다.

 

이 부분에 대해서는 더 나은 방법이 아직 생각이 나지 않기 때문에 제일 최적으로 로직을 작성했다고 생각합니다.

 

어떻게 개선해야할까?

다시 본론으로 돌아와서 생각한 접근법에 대해 코드로 빠르게 작성하고, 그 과정에서 효율성과 가독성을 고려하여 작성하기 위해서는 어떻게 연습해야할까 생각해봤습니다.

 

자료구조

우선 이번 정리를 통해 Java에서 사용할 수 있는 자료구조들에 대해 잘 알고있어야 활용 또한 쉽게쉽게 할 수 있다고 생각합니다.

어떤 자료구조들이 있고. 어떤 특성을 가지고 있는지. 까지는 잘 알고 있다고 생각합니다.

그러나 Java Collections Framework에서 제공하는 다양한 메서드 및 상세한 내용에 대해서는 잘 알고 있지 않습니다.

또한 toCharArray()와 같은 자바 기본 클래스 라이브러리들도 다양하게 활용하진 못하고 있다고 생각합니다.

이러한 부분들에 대한 자세한 숙지가 곧 좋은 코드를 작성하기 위한 기반이 되고, 빠른 구현에 도움이 된다고 생각하게 되었습니다.

 

큰 틀에 대한 시간복잡도와 작은 틀에 대한 시간복잡도

위 문제에 대해서 "110"을 추출하는 방식에 대해 O(N^2) 완전탐색 방식에서 Stack을 통한 O(N)으로의 개선은 빠르게 찾을 수 있었습니다.

하지만 O(N) 내부에서도 어떤 자료구조를 사용하고, 어떤 메서드를 통해 로직을 수행하냐에 따라 눈에 보이는 개선을 할 수 있었습니다.

이처럼 큰 틀에 대해서의 최적화 뿐만 아니라 내부의 작은 코드에 대해서도 깊게 고민하고 효율적이게 작성하는 연습을 해야하겠다고 생각했습니다.

 

코드 리뷰

다양한 알고리즘 스터디를 하면서 되게 도움이 되었던 스터디는 문제풀이에 그치지 않고, 서로의 접근법/코드에 대해서 피드백을 나눌 수 있었던 스터디들이 실력향상에 많은 도움이 되었습니다.

이번 문제 또한 스터디 토론을 통해 이렇게 "110"을 추출하는 방법이 다양하구나 라는것을 배울 수 있었듯, 앞으로 개발인생에서도 코드 리뷰 및 피드백에 대해서는 적극적인 모습을 갖출 수 있도록 노력해야겠다고 생각했습니다.

 

같은 문제를 여러번, 그 과정에서 리팩토링

또한 제 잘못된 습관 중 하나는 정답을 맞췄다면 더이상 바라보지 않고, 다음 문제를. 그렇게 계속해서 절대적인 양을 늘려나가는 습관인데요.

이번에도 Stack을 통한 풀이 후 잠시 덮어두었다가 생각이 나서 한번 점검을 해보고, 개선할 수 있는 부분이 있을까? 하고 리팩토링을 수행해보았습니다.

이렇게 함으로써 이번 포스팅의 내용처럼 다양한 생각을 하고, 많은 생각을 할 수 있었다 생각합니다.

실제 서비스 개발에서도 이런 습관은 되게 중요하고, 개선을 위한 첫번째 단계라고 생각을 할 수 있었고 이런 좋은 습관을 들일 수 있도록 노력해야 겠다고 생각했습니다.