[ C++ ] 1071. 문자열의 최대공약수

 

안녕하소

반갑소

 

요즘도 꾸준히 문제는 풀고 있었긴 했는데..

매일 푸는 문제에 hard는 도전하기가 너무 벅차서

쉬운 거부터 하고자.. 어슬렁거리다가

 

 

중요한 친구들 75개를 모아둔 문제은행을 발견했습니다.

 

그래서 오늘은 이문제를 풀어보려고 합니다..

분명 easy 인데..

 

저한텐 하나도 안 easy 하네요.

 

퉤

---

 

문제가 길진 않습니다.

 

열심히 생각은 했는데

마땅한 패턴? 이 생각이 안나더군요..

 

특히 예시 4번의 경우..

 

사실 숫자의 최대공약수 경우

6이랑 8도 

최대공약수는 2지만

그러고 남은 수는 3이랑 4이고 얘네 둘은

공통점이 없는데

 

AAAAAB , AAA를 하면..

AA가 최대공약수면..?

AAAB , A 여서 문제가 안되지 않으려나..?

라는 생각이 들었습니다.

 

생각난 김에 인지 씨에게 물어봤습니다.

 

 

문제를 잘 읽어보라더군요.

 

t가 여러 개 있어야 해서.. 안된답니다.

그러네요. B를 넣을 수 없으니..

 

 

알겠습니다.

 

그리고 다시 고민해 봤지만?

아무리 생각해도 마땅한 패턴이 떠오르지 않아서

결국 다시 인지 씨를 찾았습니다.

 

 

인지 씨에게 힌트를 달라고 하니 3가지를 주었습니다.

 

 

1

str1은 최대공약수 g를 m번 반복한 거일 거고

str2는 g를 n번 반복한 거일 것이다.

그러니? 이 글자 두 개를 합치면?

동일한 문자열이 되어야 한다는 것!

 

 

 

2

1의 근거를 반대로 생각하면

g는 str1의 일부분이고 str2의 일부분이기도 하다.

문제에서 가장 큰 공통 문자열을 찾으라고 했으니

g가 가질 수 있는 가장 긴 글자수는

str1의 길이와 str2의 길이의 최대공약수가 그 길이가 되는 것!

 

 

 

3

이 1,2번의 근거를 바탕으로

str1이든 str2든 맨 앞에 규칙이 숨어있을 테니

substr을 써서 앞에를 싹둑 잘라보는 것!

 

 

 

오케이 해보겠습니다.

 

 

 

근거가 완벽해 서그런지?

쓰는데 어렵지 않았다.

 

 

3분?

하지만.. 오류는 투성이었다.

 

1. return " " 는 결국 스페이스가 들어가서 X

아예 "" 로 수정!

 

2. 저렇게 string answer이라고 하면..

return이 되겠음??!?!?!?!?!?

따로 빼주기!

 

 

3.strsub가 아니라..

substr입니다.

 

4. substr은 ( pos, count ) 로

 

pos는 시작 위치

만약에 첫 번째부터면 1

맨 앞이면 0

이렇게 해줘야 한다.

str1 [0] 할 필요 없음

 

count는 잘라낼 개수

pos 위치부터 몇 개의 문자를 잘라낼지 쓰는 것

생략 시 pos부터 끝까지 다 자른다.

 

헤헤

 

 

완성!

 

여기 코드가 좋은 이유는? 정렬이 된다 ㅎ

폰트도? 바뀐다.

 

 

히히 완성!

---

 

 

 

해결!

아니 근데 이거보다 빨리 푸는 방법이 있는지..

나는 꽤(?) 뒤에 있다.

 

운 좋게

c++로 다른 사람이 푼 걸 봤다.

 

 

 

식은 사실 같은데..

길이가 짧아서 그런가? 이 사람은 0ms 이 걸렸다고 한다.

 

 

결국은 글자 비교하는 게 중요했다.

str1 + str2가 정말 떠올리기 어려운 방법이었다.

 

그리고 이 사람 거 보니

str1. size()랑

size(str1)이랑 같은 건가 보다.

 

 

오케이.

다 풀었다.

이거 푸는데 한 시간이 걸렸네...

쉬운 듯 어려운 듯하다.