[김홍찬]

이미 제줄해 버렸지만, 제출후에야 아래 테스트셋 있는걸로 검사해보니 틀린게 나와서요ㅜ

찾아보니 처음부터 생각을 다르게 한게 있더군요

예를들어

[김홍찬]

그렇게 이해해서 code가 아닌 string이 recursive하게 수행되어 반복되는 구간을 찾아내도록 만들었기 때문에, plus가 100개 이상 반복되도 1초이상 걸리지 않고 오히려 string의 길이에 관계하는 complexity가 나오네요

실제로 code와 string중 어떤것의 길이에 관계된 time complexity가 나오는게 정상인가요?ㅜ

[장민석]

[c]를 코드 c가 의미하는 스트링 집합이라고 한다면, 숙제 스펙의 정의에 따라

[0] = {0}
[1] = {1} 이고,

[c1|c2] = [c1]∪[c2] 이므로

[0|1] = {0, 1}

그리고
[c+] = [c]∪[c.c]∪ [c.c.c] ....
[c1.c2] = {s1s2|s1∈[c1], s2∈[c2]} 이므로

[(0|1)+] = {0, 1} ∪ {00, 01, 10, 11} ∪ {000, 001, 010, 100, 011, 101, 110, 111} ∪ ....

가 됩니다. 즉 0과 1을 조합하여 만들 수 있는 모든 스트링(공스트링 제외)의 집합이 되죠.

[공순호]

장민석씨가 답변하신 내용이 정확합니다.
_________________
- soon@ropas