24023번 아기 홍윤

문제 설명

이번 문제는 주어진 배열에서 연속된 원소들을 bitwise or 연산했을 때 주어진 수가 나오도록 하는 연속된 원소들을 구하는 문제입니다.

(해당 배열에서 가능한 구간이 여러개일 경우 한 가지만 출력해도 됩니다.)

 

문제 풀이

아이디어

시간 초과를 피하는 방법

이번 문제의 주어진 배열의 원소 개수가 200,000이고, 원소의 크기는 1<=Ai<=2^(30) - 1 이므로 가능한 구간들을 모두 찾아볼 경우 시간 초과가 날 가능성이 큽니다.

 

배열에서 연속된 구간을 찾는 문제로는 투 포인터를 자주 사용하므로 투 포인터를 사용해보도록 하겠습니다.

 

 

bitwise or 연산

bitwise or 연산의 특성을 살펴보면, 1이 하나라도 있다면 결과값은 1이 됩니다.

 

 

투 포인터 사용 시 저장할 값

(두 개의 포인터는 s, e이고 s<e라고 설정하겠습니다)

연속된 구간의 bitwise or 연산의 결과값을 가지고 있을 때 중요한 것은 2진수의 각 자리수의 1의 개수라고 생각합니다.

그 이유는 연속된 구간에 대한 포인터가 움직일 경우를 생각해보면, 예를 들면 s가 s+1로 이동할 경우를 생각해보겠습니다.

 

s포인터가 s+1로 이동하게 되면서, A[s]를 연속된 구간의 bitwise or 연산의 결과값에서 빼줘야 합니다.

이 때 각 자리수 마다의 1의 개수를 알고 있어야지만 A[s]의 2진수의 각 자리수에서 1인 자리수를 1씩 빼줘서 s+1~e 구간의 bitwise or 연산의 결과값을 알 수 있다고 생각합니다.

 

그러므로 투 포인터를 이동하면서 저장하고 있어야 하는 값은 연속된 구간의 원소에 대한 2진수의 각 자리수의 1의 개수입니다.

 

 

풀이

투 포인터 이동 조건

투 포인터를 이동하면서 각 자리수의 1의 개수를 저장하고 있는 변수를 pointer로 선언했습니다.(len(pointer)==30)

 

e가 이동할 조건

• e<N이고 s==e일 경우 (s<e 여야 하므로)
• e<N이고 연속된 구간의 bitwise or 결과값 < K

e가 이동하면 A[e+1]원소의 2진수의 각 자리수에서 1인 자리수를 pointer의 자리수에서 1씩 더해줍니다.

 

 

s가 이동할 조건

• e 이동 조건을 만족하지 않을 경우

s가 이동하면 A[s] 원소의 2진수의 각 자리수에서 1인 자리수를 pointer의 자리수에서 1씩 빼줍니다.

 

 

각 조건을 만족할 경우 포인터를 이동시키면, s>e이거나, 연속된 구간의 bitwise or 연산의 결과값이 K일 경우 반복문을 벗어나게 됩니다.

s>e일 경우 연속된 구간의 bitwise or 결과값이 K인 경우가 없는 것이므로 -1을 출력합니다.

연속된 구간의 bitwise or 연산의 결과값이 K일 경우 s 와 e를 공백을 사이에 두고 출력합니다.

 

 

해결

문제 풀이 자체가 처음부터 끝까지 깔끔하게 풀어내지는 못했지만, 연속된 구간이라는 말을 통해 투포인터를 생각해내고 투포인터 사용 시 저장할 값은 무엇인지 스스로 생각해낼 수 있어 만족스러웠던 문제였습니다.

 

문제 링크 : https://www.acmicpc.net/problem/24023

24023번: 아기 홍윤

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/24023.py