이 문제 각 테스트 케이스마다 배열 입력받고 정렬하고 한 번 처음부터 끝까지 지나가면서 같은 숫자가 이어지는 최대 길이를 찾아서 과반수 이상인지 확인했는데 시간초과 났음. 원소를 한 번씩 보는건 무조건 해야 할 것 같은데 정렬 때문에 시간초과 난건지 혹시 더 빠른 알고리즘 있나요?
실3짜리 문제긴 한데 푼 사람도 적고 질문 게시판도 클린하고 구글에도 없고...혹시 계신가 해서 여기 올려봅니다.
*수정
정렬된 배열 전체를 볼 거 없이 길이가 과반수가 넘는 연속된 수가 있어야 되니까 배열의 중간까지만 보는 걸로 수정해서 올려봤는데도 역시 시간초과 나네요 예상 못한 알고리즘을 써야 될 각
근데 제한시간이 10초나되는데 왜 시간초과가 나는거지 테스트케이스도 200개고 각 테스트 케이스마다 o(nlogn) + o(n/2)가 소요되는데 n 최댓값이 10만임. 되고도 남아야 된다고 생각하는데 말이에요...ㅠㅠ
아씨 코드 어찌 올리누
대충 어떤 알고리즘인지 설명해주실 수 있나요 ?
그게 틀렸으면 입출력 속도가 느린 거 아녀 ?
cin cout 다 printf랑 scanf로 교채해볼께요
ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
이거 추가 안 돼 있으면 입출력 속도 느림. 그리고 '\n' 대신 endl 쓰면 또 속도 엄청 늦어짐
위에서 알려주신 세줄 추가하니까 채점이 돌아가네요 감사합니다 ㅎㅎㅎ
문제 풀 때 항상 저 코드 넣는게 좋나요?
입출력이 많을 땐 반드시 넣어요. 저거 때문에 코드가 통과가 안 될 때가 꽤 있어서요
첨보는 코든데 개꿀 팁이네요 ㅎㅎ 감사함미다