1071. Greatest Common Divisor of Strings

[문제]

For two strings s and t, we say "t divides s" if and only if s = t + ... + t (i.e., t is concatenated with itself one or more times).

Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2.

 

[TC]

Example 1:

Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"

Example 2:

Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"

Example 3:

Input: str1 = "LEET", str2 = "CODE"
Output: ""

Constraints:

• 1 <= str1.length, str2.length <= 1000
• str1 and str2 consist of English uppercase letters.

[접근]

TC 3 의 처리는 매우간단하다. 그냥 앞자리부터 안맞으면 "" 리턴했다. 어차피 나눌수도 없기때문에..

까다로웠던건 TC 2 였는데 자른 후에 내 안에서도 자를 수 있으면 잘라야한다. 라는 조건 처리가 상당히 애매했다.

ABAB니까 div 를 이용해서 중간 자르고 하려했는데, 이것또한 뭔가 애매해서 str2 로 str1 로 자른후에 남은것으로 str2를 자르고 최종적으로 str1 == str2 가되면 공통으로 자를 수 있는 가장 큰 문자라고 생각해서 그렇게 작성했다.

 

[코드] C#

-> TC 에는 없는 부분들이 Submit 에서 튀어나와 지저분한 예외처리 코드가 많이 들어갔다.

고품질의 코드를 뽑지못함에대해 상당히 아쉽다.

public class Solution {
    public string GcdOfStrings(string str1, string str2) {

    if(str1[0] != str2[0])  return ""; 
    if(str1 == str2) return str1;
    // 처음부터 안맞는 경우 예외처리

    bool pass = false;
    while(str1 != "" || str2 != "" )
    {
        if(str1.Length > str2.Length)
        {
            if(str1.StartsWith(str2,false,null))
                str1 = str1.Substring(str2.Length,str1.Length - str2.Length);
            else
                pass = true;
        }
        else
        {
            if(str2.StartsWith(str1,false,null))
                str2 = str2.Substring(str1.Length,str2.Length - str1.Length);
            else
                pass = true;
        }

        if(str1 == str2)
            break;

        if(pass == true)
            break;
    }

    if(pass) return "";
    else if(str1 == "")
        return str2;
    else    
        return str1;
    }
}

[결과]

[후기]

이 문제는, 몇년전 아니면, 몇개월전 마주했던 코딩테스트 문제와 동일한 부분이 있었다.

코테에선 자주나오게 되는 유형으로 판단된다.

처음 트라이했을때는 풀지못했다. 이유는 while 문으로 인한 Time Limit 때문에 결과도 안보여주더라.

힌트를 보고 뒤에서 부터 자른다는 개념을 봤는데, 아무리봐도 인덱스때문에 꼬일거 같아서 앞에서부터 잘랐다.

그로인해 코드가 더러워졌나보다.

 

나중에 다른 코테에서 다시만나게될 유형이라고 생각한다. 그때는 더욱 군더더기 없는 고품질의 코드를 짰으면 좋겠다.

진짜 Submit A 360개 B 360개는 진짜 악질이라고 생각한다..