sosu 문자열을 계속 쌓는게 아니라 현재 소수n번째가 무슨 숫자인지 저장해도 상관없었군요... 뻘질문을 쓴거에 굉장히 부끄럽군요...

그런데 문자열에 문자를 붙이는게 그 문자의 크기가 커지면 시간도 선형으로 늘어나는 이유가 뭔가요?

당연히 이럴때 무조런 시간복잡도 O(1) 인줄 알았는데 말이에요...

python string의 + 연산은 객체 전체를 내부적으로 복사해서 메모리에 저장한 후 합치는 연산을 수행하기 때문에 문자열의 길이만큼 연산을 진행합니다.
그래서, 이를 좀 더 내부적으로 효율적으로 수행해주는 join method를 활용하면 O(1)에 이가 수행되고, 아래 코드처럼 AC를 받게 됩니다.
http://boj.kr/9a18f44bd3d94d3b...

mok의 길이가 최대 1이므로 join을 안 쓰고 str(mok)을 그냥 대입하는 것과 같지 않나요?

공유하신 코드의 9번줄과 질문자님의 코드의 9번줄의 결과는 전혀 다릅니다.

str.join은 iterable 객체를 인자로 받아서, 그 인자들 사이에 str을 삽입하여 하나의 문자열로 반환합니다. ex) 'ab'.join('cde') ==> 'cabdabe'

공유하신 코드에서는 sosu = sosu.join(str(mok))의 꼴로 쓰셨는데, 여기에서 mok은 항상 0이상 9이하의 정수이므로, 사실상 sosu = str(mok)과 같은 코드입니다.

실제로 아래와 같은 입력에서 sosu 전체를 출력해보시면 질문자님의 코드에서는 전체 몫들이 저장되어있는 반면, 공유하신 코드는 마지막 결과만이 저장되어 있는 것을 확인하실 수 있습니다.

여담으로, +=을 이용한 string concatenation (s += t)의 시간복잡도는 C++에서 amortized O(|t|)이지만 파이썬에서는 O(|s|+|t|)에 동작합니다.

파이썬의 문자열은 변경 불가능한 (immutable) 객체이기 때문에 새 문자열을 만들어야 하기 때문입니다.