오늘 할일
- 리츠코드
- 도커 온라인 강의
- 영어공부
오늘 한일
- 리츠코드
- Greatest Common divisor of strings은 두 문자열에 반복되는 최소공배수개념의 단위단어를 찾는 문제이다. 처음 제출한 코드는 아래와 같다.
class Solution {
public String gcdOfStrings(String str1, String str2) {
//check1. 포함관계 확인
if(!str1.contains(str2))
return "";
//check2. str2의 분해가능성 확인
if((str2.length()&1)==1)
return str2;
//str2의 분해_첫글자가 다시나오는 위치를 단위문자로 split
char first_char=str2.charAt(0);//첫문자
int last_index_of_first_char=str2.lastIndexOf(first_char);//뒤에서 부터 찾은 첫문자의 첫번째 인덱스
//check 3. 시작문자와 같은 문자가 뒤에 더 존재하지 않는다면
if(0==last_index_of_first_char)
return str2;//분해불가능 판단
//check 4. 단위 단어값 외에 단어가 존재하는지 확인
String word=str2.substring(last_index_of_first_char);//반복되는 단위 단어 값 구하기
for(String elem: str2.split(word)){//단위 단어로 분해한 String[]에 대해
if(!elem.isEmpty())//하나라도 단위 단어 값으로 깔끔하게 나뉘어지지 않는다면
return str2;//분해 불가능 판단
}
//check5. str2는 분해가능
return word;
}
}
제출 결과 올바르지 않은 답이라고 채점되었는데, 이유는 현재 코드에서 str2의 분해에만 집중하여 str1전체가 나뉘어야만 단위단어가 출력되어야 한다는 점을 간과했었다. 그 후 해당 부분을 디버깅하여 제출하였는데
아래와 같이 또 오답이 나왔다. 디버깅 과정에서 문제가 되는 케이스만 고쳐서 생긴 문제이다. 디버깅 후 다시 다른 버그를 맞이하며 제대로 문제를 이해했지만 그 이해를 구현하는 과정에서 놓치는 부분이 많다는 것을 알게되었다. 기능 하나를 구현하기 전에 전반적인 가이드라인을 수립하는 것이 좋아보이고 가장 간단한 실천으로는 몇가지 테스트케이스를 생각해보면 도움이 될 듯 해보인다.
고로 이번에는 가이드라인을 세워서 순서에 맞추어 코딩해보았다. 또한 모든 테스트 케이스를 한눈에 확인할 수 있게하기위해 main부에 케이스 별 값을 출력하게 했다.
public class Solution {
public static String solve(String str1, String str2){
//접근: str1에 str2가 존재하는가, str2는 분해가능한가, str1은 단위단어로만 구성되었는가
//1. str1에 str2가 존재하는가
if(!str1.contains(str2))
return "";
//2. str2는 분해가능한가
String word="";
if(str2.length()%2==1){
word=str2;
} else if(str2.length()%2==0){
char first_char=str2.charAt(0);
int last_index_of_first_char=str2.lastIndexOf(first_char);
if(last_index_of_first_char==0) {
word = str2;
} else if(last_index_of_first_char!=0){
word=str2.substring(last_index_of_first_char);
}
}
//3. str1은 단위단어로만 구성되어있는가
if(!word.equals("")){
if(str1.split(word).length==0)
return word;
else if(str1.split(word).length>0)
return "";
}
return word;
}
public static void main(String[] args) {
System.out.println(solve("ABCABC", "ABC"));//ABC
System.out.println(solve("ABABAB", "ABAB"));//AB
System.out.println(solve("LEET", "CODE"));//""
System.out.println(solve("ABCDEF", "ABC"));//""
}
}모든 테스트를 통과하고 다시 제출해보았더니 또 오답처리가 되었다.
str1을 str2로 나누는 것으로 이해를 했는데 str1보다 str2가 더 클 때를 추가적으로 고려해야하는 듯 하다.
현재 알고리즘에서는 시작하자마자 str1.contains(str2)를 확인하기 때문에 ""로 출력이 되었다. 여기서 문제 이해가 참 어렵구나 싶은 생각이 든다. 문장의 최대공약수가 되는 단어를 찾고 그 단어의 단위단어를 찾아야하는...
문제에서 설명한 아래의 문장에서 the largest string x such that x dividex both str1 and str2즉 str1과 str2의 최대공약수를 찾는 문제인 것인가..? 그냥 단위단어만 계산하면 될 듯 하다.
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.
디버깅을 해보니 아래의 코드 첫 if에서 문자열의 길이가 홀수면 나뉘어질 수 없다로 판단하게 했는데, 문홀수단위 단어가 홀수번 반복되면 길이가 홀수인 문자열이 만들어 지기에 오류가 발생했다.
//2. str2는 분해가능한가
String word="";
if(str2.length()%2==1){
word=str2;
} else if(str2.length()%2==0){
char first_char=str2.charAt(0);
int last_index_of_first_char=str2.lastIndexOf(first_char);
if(last_index_of_first_char==0) {
word = str2;
} else if(last_index_of_first_char!=0){
word=str2.substring(last_index_of_first_char);
}
}해당 부분을 제거하고 다시 제출해보니 "ABABABAB"와 "ABAB"케이스에서 "ABAB"가 아닌 "AB"가 출력되어 오답처리되었다. 해당 부분을 아래의 코드를 추가하여 단위단어 값으로 최대단위값을 구하게끔 수정하였다.
//4. 최대의 단위단어 찾기
if(!word.equals("")){
int min_len=Math.min(str1.length(), str2.length());
for(int repeat=2; repeat<min_len/word.length(); repeat++){
String repeated_word=word.repeat(repeat);
if(str1.split(repeated_word).length==0 &&
str2.split(repeated_word).length==0){
word=repeated_word;
}
}
}하지만 또 오답처리가 되었고, 새로운 테스트케이스를 보니 "OBCNO"처럼 같은 알파벳이 중복되는 단위인 경우에 오류가 발생했다. 생각보다 정말 까다롭다.. TDD처럼 테스트 케이스를 하나하나 수정하게끔 접근했는데 이제보니 테스트 케이스가 123개고 그 중 73번까지밖에 도달하지 못했다. 이대로 TDD방식을 고집하는 것은 과도한 시간낭비라고 판단하여 코드를 다시 처음부터 문제를 완벽히 이해한 후 재작성해보겠다.
최종적으로 재작성한 코드는 아래와 같다. 공간복잡도와 시간복잡도를 현재 내 능력에서 고려하면 지나치게 코드가 복잡해진다고 판단하여 최대한 간결하게 코드를 작성해보았다. swap을 사용하여 str1과 str2의 길이대소를 고정했고, 단위단어를 길이가 짧은 것부터 탐색하지 않고 길이가 긴 것부터 탐색하여 찾게했다.
public class Solution {
public static String solve(String str1, String str2){
if(str2.length()>str1.length()){//str1이 str2보다 길게 유지
String temp=str1;
str1=str2;
str2=temp;
}
for(int index=str2.length(); index>0; index--){
String word=str2.substring(0,index);
if(str2.split(word).length==0 && str1.split(word).length==0){
return word;
}
}
return "";
}
public static void main(String[] args) {
System.out.println(solve("ABCABC", "ABC"));//"ABC"
System.out.println(solve("ABABAB", "ABAB"));//"AB"
System.out.println(solve("LEET", "CODE"));//""
System.out.println(solve("ABCDEF", "ABC"));//""
System.out.println(solve("TAUXXTAUXXTAUXXTAUXXTAUXX", "TAUXXTAUXXTAUXXTAUXXTAUXXTAUXXTAUXXTAUXXTAUXX"));//"TAUXX"
System.out.println(solve("ABABABAB", "ABAB"));//"ABAB"
System.out.println(solve("OBCNOOBCNOOBCNOOBCNOOBCNOOBCNOOBCNOOBCNO", "OBCNOOBCNOOBCNOOBCNOOBCNOOBCNOOBCNOOBCNOOBCNOOBCNOOBCNOOBCNOOBCNO"));//"OBCNO"
}
}그 결과
진짜 반가운 Accepted가 아닐 수 없다. 이번 문제를 통해 배운 것은 테스트케이스의 작성, 문제의 완전한 이해, 문제를 어떻게 코드레벨로 구현할 것인지 계획세우기, 간결한 코드인 것 같다.
