본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.
문의는 댓글 바람.
두 문자열의 최대공약 문자?를 구해라.
[문제 설명]
t가 a번 반복되는 문자 배열은 str1 = t+t+t+t....+t => a*t
t가 b번 반복되는 문자 배열은 str2 = t+t+t+...+t=> b*t
t를 구하시오.
[처음 생각한 접근 방법]
결국에 최대공약수를 구하는 게 핵심인 문제다.
최대 공약수 구하는 법은 그냥 검색해봤다. 원래 그냥 일차 검색하려했는데 유클리드 호제법이라는 게 있는 걸 알아서.
출처는 링크
str1의 길이가 a, str2의 길이가 b라고 하자.
그러면 a와 b의 최대 공약수인 c를 구하고, 문자열에서 c개를 뽑은 것이 반복될 수 있는 기준 문자열이 된다.
최대 공약수란 두 수를 나눌 수 있는 최대의 값이다.
str1의 길이가 6, str2의 길이가 3으로 주워줬다면 answer의 길이는 최대공약수인 3.
str1과 str2 모두 answer을 반복해서 만든 문자열이므로 둘 중 아무한테서나 앞에서부터 3문자를 뽑으면 반복할 문자열이 되어야 한다.
str1을 3글자씩 나눠서 answer과 같은지 확인 후 모두 같으면 str1은 answer을 반복한 문자열이 된다.
str2도 마찬가지로 3글자씩 나눠서 answer과 같은지 확인 후 모두 같으면 str2는 answer을 반복한 문자열이 된다.
예)
str1=ABCABC, str2=ABC
-> answer은 str1에서 두 수의 최대 공약수의 개수만큼 뽑은 문자열 "ABC"가 된다.
-> str1이 answer을 반복한 건지 체크, 맞으면 str2를 체크하러 감
아니면? answer은 반복문자열이 아니므로 return ""
-> str2가 answer을 반복한 건지 체크, 맞으면 str1, str2를 반복한 문자열이 됩니다.
아니면? answer은 반복문자열이 아니므로 return "";
class Solution {
public String gcdOfStrings(String str1, String str2) {
// 최대 공약수 구하기
int gcd = getGCD(Math.max(str1.length(), str2.length()), Math.min(str1.length(), str2.length()));
// 최대 공약 문자열 구함
String answer = str1.substring(0, gcd);
// str1이 answer을 반복하는지 확인
for (int i = 0; i <= str1.length()-gcd; i+=gcd) {
// 반복하지 않으면, 공약 문자열은 없음
if (!str1.substring(i, i+gcd).equals(answer)) {
return "";
}
}
// str2가 answer을 반복하는지 확인
for (int i = 0; i <= str2.length()-gcd; i+=gcd) {
// 반복하지 않으면, 공약 문자열은 없음
if (!str2.substring(i, i+gcd).equals(answer)) {
return "";
}
}
// 전부 answer을 반복하고 있으므로 answer을 리턴
return answer;
}
public int getGCD(int a, int b) {
while(b > 0) {
int tmp = a;
a = b;
b = tmp%b;
}
return a;
}
}
public String gcdOfStrings(String str1, String str2) {
if (!(str1+str2).equals(str2+str1)) return "";
int gcdVal = gcd(str1.length() , str2.length());
return str2.substring(0, gcdVal);
}
public static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}
리트코드 답안을 볼 때마다 정말 화가 난다.
str1,str2 모두 같은 문자열의 반복이므로 둘이 순서를 바꿔서 더해도 당연히 같아야 하는데, 그걸 이용해서 초기에 잘 걸러줬다.
'알고리즘 문제 풀이 > 문자열' 카테고리의 다른 글
백준 - Contact(Java) (0) | 2022.01.05 |
---|---|
프로그래머스 - 숫자 문자열과 영단어 (0) | 2021.08.26 |
1436. Destination City (0) | 2021.07.23 |
14. Longest Common Prefix (0) | 2021.07.19 |
500. Keyboard Row (0) | 2021.07.13 |