32073번 - XOR 최대
최대한 시간복잡도를 줄여봤는데도 시간초과가 납니다 ㅠㅠ
로직이 잘못 된건지 혹은 비효율적으로 구현한 것인지 모르겠습니다.
어떻게 해야 시간초과를 해결 할 수 있을지 도와주시면 감사하겠습니다.
로직은 이렇습니다.
모든 문자열이 0으로 이루어져있으면 0출력 후 종료
1. 가장 처음에 나오는 1찾기 (길이가 가장 길고 1이 가장 맨 앞에 나와야 최대값이기 때문)
2. 가장 처음에 나오는 1 뒤에 오는 가장 처음에 나오는 0의 위치를 찾고 비교할 수를 그 위치부터 끝까지로 정하기 (앞에 나오는 1들은 비교안하면, 즉 0으로 xor 하면 1이 나와 최대값이기 때문)
만약 가장 처음에 나오는 1뒤에 0이 없다면 비교할 수는 가장 처음에 나오는 수부터 끝까지 (ex 00111, 비교할 수 : 111)
ex 001010 -> 0의 위치 3, 비교할 수 : 010
3. a에서 비교할 수의 길이만큼 슬라이딩 윈도우를 통해 비교하기
ex 001010, 비교할 수 : 010, 비교할 수의 길이 : 3, 비교되는 수들 : 001, 010, 101, 010
107자리 이진수에 대해 비트 연산을 하는 비용은 공짜가 아닙니다. n - length개의 후보를 모두 직접 확인하지 않고 최적의 j를 찾아내야 합니다.
n - length
j
댓글을 작성하려면 로그인해야 합니다.
ash_girlfriend 1년 전
최대한 시간복잡도를 줄여봤는데도 시간초과가 납니다 ㅠㅠ
로직이 잘못 된건지 혹은 비효율적으로 구현한 것인지 모르겠습니다.
어떻게 해야 시간초과를 해결 할 수 있을지 도와주시면 감사하겠습니다.
로직은 이렇습니다.
모든 문자열이 0으로 이루어져있으면 0출력 후 종료
1. 가장 처음에 나오는 1찾기 (길이가 가장 길고 1이 가장 맨 앞에 나와야 최대값이기 때문)
2. 가장 처음에 나오는 1 뒤에 오는 가장 처음에 나오는 0의 위치를 찾고 비교할 수를 그 위치부터 끝까지로 정하기 (앞에 나오는 1들은 비교안하면, 즉 0으로 xor 하면 1이 나와 최대값이기 때문)
만약 가장 처음에 나오는 1뒤에 0이 없다면 비교할 수는 가장 처음에 나오는 수부터 끝까지 (ex 00111, 비교할 수 : 111)
ex 001010 -> 0의 위치 3, 비교할 수 : 010
3. a에서 비교할 수의 길이만큼 슬라이딩 윈도우를 통해 비교하기
ex 001010, 비교할 수 : 010, 비교할 수의 길이 : 3, 비교되는 수들 : 001, 010, 101, 010