gkfkagkfka12   6년 전

시간초과나서 string 클래스 쓰다가 char*바꿔서 scanf랑 printf로 바꿨는데

이번엔 런타임 에러네요 ㅠㅠ 문자열 크기도 널문자 포함해서 50+1인데 어디서 발생하는지 모르겠습니다.

도와주시면 감사하겠습니다.

djm03178   6년 전

2

a

b

면, 21번째 줄에서 list[0]과 list[2]를 비교하려는 일이 벌어집니다. list에는 [0]과 [1]밖에 할당이 안 되어 있습니다.

gkfkagkfka12   6년 전

@djm03178 님 말 처럼 그 부분은 해결했습니다.

그런데 시간초과가 나오네요ㅠㅠ 미치겠습니다 ㅠ

코드는 주석 붙이고 수정한 부분포함해서 다시 올렸습니다.

djm03178   6년 전

아까 설명은 안 드렸지만 코드의 설계에 문제가 있습니다.
29번째 줄에서 strlen이 조건 검사 시마다 호출되는데 이의 시간 복잡도가 O(문자열의 길이)니 최악의 경우 약 200억 정도 되는 시간복잡도가 되고 맙니다. 문자열의 길이는 항상 같으니 strlen은 한 번만 호출해서 그 길이를 기억해두는 것이 낫습니다.
하지만 이 코드는 그를 해결한다고 하더라도 27~29번째 줄의 이중 루프가 이미 O(N^2)인 데다가 그 내부에서 역시 문자열의 길이만큼 시간이 걸리는 strcmp 들을 수행하고 있기 때문에 시간 내에 들어오기는 어렵습니다.
sort를 사용하시는 이상 그 자리에서 쉽게 해결이 가능하니 잘 생각해보세요. "길이가 같으면 사전 순으로" 라는 조건을 comp 함수에 포함시켜버리면 됩니다.

gkfkagkfka12   6년 전

comp함수에 포함시키니 해결됬네요. 정말 감사합니다. 정말 잘하시네요... 근데 strlen함수를 호출하는 것으로 200억이 최악인 경우는 잘 이해가 안되네요... 혹시 이 한심한 저를  이해시켜주실 수 있으신가요? 문자열의 길이가 최대 50인데 strlen이 2번 되니까 최대라고 하면 2*O(50)인데 for문이 2개, 따라서 n이 최대라고 했을 때 20000*(20000+100) 아닌가요? 최대 200만 같은데 200억이 잘 이해가 안가네요 죄송합니다.

djm03178   6년 전

조건 검사는 루프가 돌 때마다 일어나죠. 따라서 곱하기가 되어야 합니다. 여러 번 검사하는 건 상수배라 계산하지 않았지만 20000 * 20000 * 50 으로 200억이 됩니다.

gkfkagkfka12   6년 전

정말 감사합니다!!! 새해복 많이 받으세요 :)

댓글을 작성하려면 로그인해야 합니다.