Leetcode 13. Roman to Integer

링크: https://leetcode.com/problems/roman-to-integer/description/

 

질문

이 문제를 해결하기 위해 두 가지 방법을 생각했는데, 첫 번째 방법을 택하려고 해. 이유를 설명할게.

첫 번째 방법은 문자열을 split한 후, for문으로 각 문자를 순회하며 뒷자리 문자가 앞자리보다 큰지 비교하는 방식이다. 문자열 길이가 최대 15이므로 성능상 문제는 없을 거라고 판단했다.

두 번째 방법은 if문 안에 또 if문을 넣어서 M, D, C 순으로 분기하는 방식이다. M이 1000으로 고정되어 있으니까, M 다음에 D가 나오면 다시 M이 나올 가능성은 없다고 가정하고 분기 수를 줄일 수 있어.(여기가 오류) 하지만 코드가 너무 복잡해지고 가독성이 떨어질 것 같아 이 방법은 선택하지 않았다.

내가 놓친 부분이 있을 수 있으니, 문제될 부분을 생각하게끔 질문을 통해 알려줘. 나는 답이나 풀이를 알고싶은게 아니다. 내가 놓친 부분이 있을 수도 있으니 내게 질문을 해서 문제가 되는 부분을 생각할 수 있게 알려줘.

답변

좋은 접근을 하고 있네요!

첫 번째 방안에서는 for문을 사용해서 문자를 하나씩 비교하는 전략을 선택하셨는데, 이 방법은 적절해 보입니다. 특히, 길이가 15로 한정되어 있다면 성능 면에서도 문제가 없을 것으로 보입니다. 하지만, 내가 질문을 던지자면, '뒷자리 문자가 앞자리보다 클 경우'를 처리할 때 각 문자가 로마 숫자의 규칙을 따르는지에 대한 정확한 검증이 이루어지고 있는지 궁금합니다. 예를 들어, IV는 유효하지만 IL은 유효하지 않습니다. 이런 규칙을 어떻게 체크할지 생각해보셨나요?

두 번째 방안에 대해서도 충분히 좋은 인사이트가 있는데, 코드가 복잡해질 수 있다는 문제를 스스로 인지하신 것이 인상적입니다. 그렇다면 첫 번째 방안을 사용하면서도, 코드의 가독성과 유지보수성을 고려해 로마 숫자의 규칙을 깔끔하게 처리할 방법이 있을까요?

 

질문

이 문제는 로마 규칙을 따르고 있어서 IL이 나올 확률은 제로이다. 그랬을때 첫번째 방법에서 문제될 부분이 또 있는가?

답변

로마 규칙을 따르기 때문에 IL과 같은 경우는 없다는 점을 명확히 인지하고 계시군요! 그렇다면 첫 번째 방안에서 남은 부분은 두 가지 정도의 질문을 던져볼 수 있을 것 같아요.

앞자리보다 큰 뒷자리의 값일 때 어떻게 처리할지는 잘 설계되었나요? 예를 들어, "IV"는 5에서 1을 빼는 방식인데, 이를 제대로 감지하고 처리할 로직이 있는지 생각해볼 수 있을 것 같습니다. 뒷자리가 더 큰 경우 값을 더하는 것이 아니라 빼야 하는 특수 규칙이 있기 때문에 이 부분이 잘 처리되고 있는지 확인이 필요할 것 같습니다.

마지막 문자에 대한 처리는 잘 되고 있나요? 예를 들어, 마지막 문자는 비교할 뒷자리가 없기 때문에 특별한 처리가 필요한지, 혹은 현재 로직에서 자연스럽게 해결되는지 한번 고려해보는 것이 좋을 것 같아요.

이 두 가지 질문을 바탕으로 로직이 모두 완벽하게 작동할지 한 번 더 생각해보면 좋을 것 같습니다.

 

질문

내 코드가 나쁜 코드일까 좋은 코드일까. 일반적으로 빅 테크 기업에서 생각하는 기준으로 판단해줘. 만약, 나쁜 코드든 좋은 코드든 이유가 있다면 네가 내게 질문하는 방식으로 내가 유추하고 사고할수 있게 알려줘.

답변

좋은 질문입니다! 일반적으로 빅 테크 기업에서 코드를 평가할 때는 효율성, 가독성, 유지보수성, 확장성, 그리고 버그 가능성을 주요 기준으로 삼습니다. 이에 기반해서 몇 가지 질문을 통해 코드의 품질을 분석할 수 있도록 하겠습니다.

코드의 중복성을 고려했을 때:
romanSum과 romanDiff 두 메서드가 유사한 로직을 포함하고 있습니다. 빅 테크 기업에서는 중복 코드를 지양하고, 재사용 가능하고 간결한 코드를 선호합니다. 이 두 메서드를 어떻게 합칠 수 있을까요? 혹은 더 나은 방식으로 처리할 방법은 없을까요?

유지보수성을 고려했을 때:
if-else 체인이 여러 번 등장하고 있습니다. 이렇게 많은 분기 처리가 들어가는 코드는 새로운 로마 숫자 규칙이 추가되거나 변경될 때 유지보수에 어려움을 줄 수 있습니다. 조건 분기 대신 더 나은 자료 구조(예: 맵이나 배열)를 사용할 방법은 없을까요? 이런 방식으로 가독성을 높일 수 있을까요?

로직의 효율성 관점에서:
romanDiff를 두 번 호출하고 있는데, 그 중 하나는 바로 앞에서 호출한 결과와 비교하고 있습니다. 이 반복 호출을 줄일 수 있는 방법이 있을까요? 이 부분이 성능에 영향을 미칠 수 있는지 고려해보셨나요?

가독성 측면에서:
++i를 사용하는 방식이 코드 흐름을 복잡하게 만들 수 있습니다. 로직을 따라가기 쉽지 않으며, i의 증감에 따른 흐름이 명확하지 않을 수 있습니다. 이 부분을 어떻게 더 직관적으로 만들 수 있을까요? 다른 사람도 코드를 쉽게 이해할 수 있도록 개선할 방법이 있을까요?

 

질문

1. 문자를 바로 값으로 계산하는 함수와 문자를 비교한 후 계산하는 함수가 필요하기 때문에 분리할수밖에 없었다. 더 효율적이고 명확하게 함수를 작성할 수 있는 방법이 존재한다는 뜻이니?

2. Map 을 사용하면 속도는 빠르지만 확장성이나 유지보수면에서 좋은 방법이 아닐 것이라 판단했다. Map에는 어떤 자료가 담겨있는지 눈에 띄게 확인하기 어렵기 때문이다. 내가 잘못 알고 있는 것이라면 말해줘.

3. 바로 처리하게 한다는게 함수 안에서 말고 함수 호출 전에 처리하는 방법이 있다는 뜻이니?

4. 2번과 같은 이유다. Map 말고 다른 방법이 있다는 뜻이니? 앞서 내가 물어본 방법과 마찬가지로, 네가 내게 질문하는 방식으로 내가 유추하고 사고할수 있게 알려줘.

답변

1. 함수 분리에 관한 질문:
두 개의 함수가 분리된 이유는 충분히 이해가 됩니다. 그런데, 문자를 바로 값으로 계산하는 romanSum 함수와 비교 후 계산하는 romanDiff 함수 사이에서 중복되는 코드가 있는지 확인해보셨나요? 예를 들어, romanSum을 한 번만 호출하고 그 값을 romanDiff에서도 재사용할 수 있는 방법이 있을까요? 이 방식으로 성능을 최적화할 수 있을지 생각해볼 수 있습니다.

2. Map에 대한 질문:
Map의 확장성이나 유지보수 측면에서 고민한 점도 중요한 포인트입니다. 하지만, 코드 가독성과 유지보수를 생각할 때, 수십 개의 if-else 체인을 나열하는 것과 비교했을 때 Map을 사용하는 것이 장기적으로 더 직관적일 가능성도 있지 않을까요? 또한, 만약 Map을 사용하면서도, 어떤 자료가 담겨있는지 직관적으로 알기 쉽게 작성하는 방법이 있을까요? 예를 들어, SYMBOL과 VALUE 배열처럼 간단한 방식으로 보일 수 있지 않을까요?

3. 로직 간결화에 대한 질문:
함수 안에서 처리하는 것보다 호출 전에 처리하는 방법이 있다는 뜻이 맞습니다. 로직을 함수 호출 전에 간단하게 처리한다면, 함수가 너무 복잡해지지 않고도 로직이 간결해질 가능성은 없을까요? 예를 들어, 숫자를 비교하는 단순 규칙을 함수 외부에서 먼저 해결할 수 있다면, 함수 안의 분기를 줄일 수 있을지 생각해볼 수 있습니다.

4. Map 이외의 방법에 대한 질문:
Map이 아니더라도 다른 자료구조나 패턴을 고려해 볼 수 있습니다. 정적 배열과 switch-case나 enum 같은 구조를 사용하면 가독성과 성능을 동시에 유지할 수 있을까요? 이러한 구조를 사용하면 Map이 주는 단점(눈에 잘 띄지 않는 자료)과 if-else의 단점을 동시에 해결할 수 있을지 고민해볼 수 있습니다.

 

질문

1. 수정해보았다.

2. Map 방식 말고 그렇다면 PB Tree 방식을 쓰면 더 효율적일까?

3. 수정해보았다.

4. switch-case 의 경우 case 레이블이 컴파일 시점에 상수값이어야 하기 때문에 내 경우와는 안 맞는 방식인 것 같다. 그래도 if-else 보다 switch-case를 더 추천하는 이유가 있나?

답변

1. 코드 수정에 대한 질문:
수정한 코드에서 romanSum과 romanDiff 부분이 더 명확해졌습니다. 그런데 romanDiff를 두 번 호출해서 비교하는 부분이 있습니다. 이미 구한 prev와 next 값을 한 번만 계산하고 그 결과를 재사용할 수 있는 방법은 없을까요? 중복 계산을 피하면 성능 최적화에 더 도움이 될 수 있을 것입니다.

2. PB Tree (Prefix/Binary Tree)에 대한 질문:
PB Tree는 특정 패턴을 빠르게 찾거나 트리 구조에서 효율적으로 데이터를 탐색하는 데 유리한 자료 구조입니다. 현재 문제에서는 트리 구조를 사용해 얻는 이점이 얼마나 클지 생각해보셨나요? 예를 들어, 문자열의 길이가 짧고(최대 15), 비교할 문자의 종류도 7개로 한정되어 있어 PB Tree의 장점이 충분히 발휘될지 의문이 듭니다. 트리 구조가 실제로 성능에 크게 기여할지, 아니면 간단한 배열이나 Map이 더 적합할지 다시 한번 고민해보는 것이 좋을 것 같습니다.

3. 코드 수정에 대한 질문:
수정하신 코드에서 romanDiff를 두 번 호출하고 그 값을 비교하여 ++i를 처리하는 부분이 있는데요, 중복 계산을 피하기 위해 조건문에서 romanDiff와 romanSum을 한 번씩만 호출하고 그 값을 변수에 저장해 두면 어떨까요? 이렇게 하면 불필요한 호출을 줄이고 성능을 향상시킬 수 있을지 생각해볼 수 있습니다.

4. switch-case와 if-else에 대한 질문:
switch-case는 컴파일러가 내부적으로 효율적으로 최적화할 수 있기 때문에, 특히 상수 값을 처리할 때 if-else보다 빠를 수 있습니다. 다만, switch-case가 컴파일 시점에 상수 값이 필요하다는 점을 고려할 때, 혹시 다른 패턴이나 자료 구조로 상수 값을 처리할 방법은 없을까요? 예를 들어, 상수 값 비교를 빠르게 할 수 있는 또 다른 방법으로는 enum이나 Map을 사용하는 것이 더 적합할 수 있겠죠. 그러면 switch-case 대신 무엇을 사용할 수 있을까요?

 

질문

1. 이미 충분히 잘 재활용 했다고 생각하는데 더 필요한가? 문제에서 요구하는 부분에서는 더 필요 없는데, 질문의 의도를 모르겠다. 한번만 사용하는데 굳이 변수에 담을 필요가 없다고 이야기 하는 것이라면 사람이 눈으로 볼때의 가독성을 생각해서 그리 작성한 것인데, 혹시 그걸 얘기하는 거니? 그렇다면 diff_num 으로 수정하고, num 을 없앴다.

2. 확장가능성이 있다는 가정을 해보았을때 효율적인지 궁금하다.

3. 중복 계산을 피하라는게 이해가 잘 안 간다. i와 i+1를 계산하는 건 중복이 아니지 않니?

4. Map은 아까도 얘기했지만 직관적이지 않은 부분 때문에 배열로 대체했다.

답변

1. 가독성과 변수 재활용에 관한 질문:
diff_num 변수로 개선한 부분이 가독성 측면에서 좋은 선택입니다. 그런데, 가독성을 위해 변수를 추가했을 때 성능과 유지보수성 측면에서도 이 선택이 항상 유리할까요? 예를 들어, 코드의 규모가 커질 때 가독성을 유지하면서도 변수를 효율적으로 사용할 방법이 있을지 고민해볼 필요가 있을 것 같습니다. 즉, 이 변수를 추가하는 것이 장기적으로 유지보수에 얼마나 도움이 될지, 혹은 가독성을 위해서라도 조금 더 최적화할 여지가 있는지 다시 한번 생각해보는 것이 좋을 것 같습니다.

2. 확장 가능성에 대한 질문:
확장 가능성이라는 가정을 했을 때, 새로운 로마 숫자 규칙이나 다른 문자가 추가될 가능성을 고려해 봤다고 하셨습니다. 그런데, 현재 배열 구조를 그대로 사용할 경우, 만약 더 많은 문자가 추가된다면 이 코드가 어떻게 확장될 수 있을까요? 예를 들어, 규칙이 더 복잡해질 경우 if-else 체인이 계속해서 길어질 가능성이 있는데, 이 경우를 고려해 Map 같은 다른 자료 구조가 더 확장성에 유리할까요? 아니면 배열 기반이 유지보수 측면에서 더 나을까요?

3. 중복 계산에 대한 질문:
i와 i+1을 계산하는 것은 중복이 아니라고 말씀하셨는데 맞습니다. 하지만, romanDiff에서 prev와 next를 다시 한 번 비교하는 방식이 성능 최적화 측면에서 최선인지 고민해보셨나요? 즉, 이미 계산한 값을 변수로 저장해 두고 재사용할 수 있는 부분이 있지는 않은지, 성능 최적화와 가독성의 균형을 맞출 수 있는 방법이 있을지 생각해 볼 수 있습니다.

4. 배열과 Map의 선택에 대한 질문:
배열이 더 직관적이라고 판단하여 선택한 점은 잘 이해됩니다. 하지만, 나중에 새로운 로마 문자 규칙이 추가되거나, 로마 숫자가 아닌 다른 문자열 규칙을 처리할 가능성이 있다고 가정했을 때, 배열보다 더 직관적이고 효율적인 자료 구조가 있을까요? 예를 들어, 배열은 문자의 순서에 의존하는데, 문자가 규칙 없이 추가되거나 변동될 경우에도 배열이 가장 효율적일지 다시 한 번 고민해볼 필요가 있습니다.

 

초기 코드

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {

    private static final int I = 1;
    private static final int V = 5;
    private static final int X = 10;
    private static final int L = 50;
    private static final int C = 100;
    private static final int D = 500;
    private static final int M = 1000;

    public int romanToInt(String s) {
        
        String[] letter = s.split("");

        int result = 0;

        for(int i=0; i<letter.length; i++) {

            if((i+1)<letter.length) {
                if(letter[i].equals(letter[i+1])) {
                    result += romanSum(letter[i]);

                } else {
                    result += romanDiff(letter[i+1], letter[i]);
                    ++i;
                }
            } else {
                result += romanSum(letter[i]);
            }
        }
        return result;
    }

    public int romanSum(String ss) {
        int sum = 0;
        if("M".equals(ss)) {
            sum += M;
        } else if("D".equals(ss)) {
            sum += D;
        } else if("C".equals(ss)) {
            sum += C;
        } else if("L".equals(ss)) {
            sum += L;
        } else if("X".equals(ss)) {
            sum += X;
        } else if("V".equals(ss)) {
            sum += V;
        } else if("I".equals(ss)) {
            sum += I;
        }
        return sum;
    }

    public int romanDiff(String sss, String ss) {
        int next = 0;
        int prev = romanSum(ss);

        if("M".equals(sss)) {
            next = M;
        } else if("D".equals(sss)) {
            next = D;
        } else if("C".equals(sss)) {
            next = C;
        } else if("L".equals(sss)) {
            next = L;
        } else if("X".equals(sss)) {
            next = X;
        } else if("V".equals(sss)) {
            next = V;
        } else if("I".equals(sss)) {
            next = I;
        }

        if((prev-next) <0) {
            return next-prev;
        } else {
            return prev;
        }
    }
}

 

개선 코드

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {

    private static final String[] SYMBOL  = {"M", "D", "C", "L", "X", "V", "I"};
    private static final int[] VALUE = {1000, 500, 100, 50, 10, 5, 1};

    public int romanToInt(String s) {
        
        String[] letter = s.split("");
        int result = 0;

        for(int i=0; i<letter.length; i++) {
            int prev = romanSum(letter[i]);
            
            if((i+1)<letter.length && !letter[i].equals(letter[i+1])) {
                int next = romanSum(letter[i+1]);
                int diff_num = romanDiff(next, prev);

                result += diff_num;
                if(diff_num!=prev) {
                    ++i;
                }
            } else {
                result += prev;
            }
        }
        return result;
    }

    public int romanSum(String ss) {
        int sum = 0;
        if(SYMBOL[0].equals(ss)) {
            sum += VALUE[0];
        } else if(SYMBOL[1].equals(ss)) {
            sum += VALUE[1];
        } else if(SYMBOL[2].equals(ss)) {
            sum += VALUE[2];
        } else if(SYMBOL[3].equals(ss)) {
            sum += VALUE[3];
        } else if(SYMBOL[4].equals(ss)) {
            sum += VALUE[4];
        } else if(SYMBOL[5].equals(ss)) {
            sum += VALUE[5];
        } else if(SYMBOL[6].equals(ss)) {
            sum += VALUE[6];
        }
        return sum;
    }

    public int romanDiff(int next, int prev) {
        if((prev-next) <0) {
            return next-prev;
        } else {
            return prev;
        }
    }
}