1번은 그냥 해쉬 이용해서
문자열마다 n ~ 1 길이 가진 substring 뽑아서 체킹해주면 됨
문자열이 만개니까 시간 복잡도는 최악의 경우에 1e4 *log(1e4) * 1e2 정도로 1초안에 풀림
다만 조금 애매한게 예시가 한글로 되있어 "봄봄" 같은 경우 문자열 길이가 내부적으로는 6이라서
"가가가가가가가가가" 이런 케이스가 있다면 해쉬 배열 크기가 16보다 커야 되지않나 싶긴함(아마 그렇진 않을듯)
2번 같은 경우 정렬 후 set 만들어서
함수마다 find() 로 짜면 되는데
문제는 문제에서 값의 범위는 알려주는데 처음 배열크기는 알려주지 않음
만약에 1부터 1e6값 까지 1000개씩 들어있다면 그냥 O(n)으로 돌린 경우 시간 초과 남
나같은 경우에는 이분탐색으로 짰는데 아마 문제에서 배열크기 안알려준거보면 이런 테스트 케이스는
충분히 있을만 한듯 이것만 고려하면 다음부터는 set크기가 아무리커도 1e6 안에 있으니
함수마다 잘짜면 시간 초과는 안 날듯
해당 댓글은 삭제되었습니다.
일일히 다 비교해준거면 엄청느림...
그게 먼소리임 stl은 당연히 써야지
아 언어가 c++이 아닌가보구나 시행횟수 1억넘기면 시간초과 날 수 있다고 보면됨
ㅇㅇ 1번 10분만에 풀었대서 좀 깜짝놀랏는데 다 저렇게 풀었을라나...
1~n substring 뽑는 가짓수가 존나 많아질 것 같은데... 한 문자열당 256개인데?
문자열 길이가 16이니까 (16*17)/2 가지나옴
아 그럼안전하네 ㅇㅋ
256* n이니까 별로 안크죠
별로안큼
근데 시간제한 걸려 있었음?
문제에서 명시는 안해줬는데 ps경력 1년차 시간 제한 10초 아래로 걸려있는 문제는 본 적이없음
만약에 2번 같은 경우 배열 크기가 10억인 데이터가 존재할 때 그냥 정렬 후 for문 돌려서 10억개 다보면 10초 넘어감
2번은 그냥 크기 배열 1'000'001 2개 만들어서 각 함수들 1'000'001시간 이내에 다 실행 되는거아님? A, B set은 배열크기 만큼 더 걸리고
ps나도 하구 있는데 제한 안적어 놓고 컽하는건 좀 아닌거 같은데
처음에 set을 만드는 과정에 대해서 얘기하는거임 거기서 그냥 1씩 증가하는 for문 돌렸으면(O(n)으로 짠 경우) 저런 케이스있으면 시간초과임
물론 문제 난이도 보면 딱히 고려하지 않은 것 같기도 함 근데 수 범위가 딱 1e6 까지인게 1e6 * log(1e6) 으로 1초안에 돌아가는거보면 내 생각에는 그거 고려해야할듯
이분 탐색으로 1000'000 까지 숫자 존재 찾으면서 하는거는 알겠는데 결국 정렬 하고 해야되니까 nlog n 아님?
배열 크기도 1e6안넘을거 같은데
정렬하고 nlogn으로 짜면 돌아갈텐데 O(n)으로 짜면 시간초과 날 수 있음
o(n)인데 어케 시간 초과가 남
첨에 배열길이가 10억이면 시행횟수 10억이니까 십초 넘어감
그문제는 이분탐색 같은거 쓰는 풀이나 set구현 풀이는 nlog n이 들어가니까 10초 더 넘어가는거 아님?
아 N= 1e6 n = 배열길이라 하면O( Nlogn )하고 O(n) 말한거임 약간 잘못말했네
2번은 그냥 카운팅소트 하면 됨
ㅇㅇ
해설 고맙따 1번 계속 시간초과난 이유가 있었네