24453번 디버깅

문제 설명

이 번 문제는 자동으로 생성된 코드에 오류가 반드시 존재할 때, 이 오류를 자동으로 고쳐주는 커맨드를 누르기 위해 필요한 전제 조건을 만족하여 커맨드를 누를경우 해결되는 오류의 개수를 최대로 하는 문제입니다.

전제 조건

• 작성된 코드에서 오류가 없는 연속된 X줄이 존재
• 사용자는 오류를 Y개 이상을 찾아 해결한 뒤에 커맨드를 누르고 싶다

 

 

문제 풀이

아이디어

이번 문제는 Y와 관련된 전제 조건을 마지막에 생각하는 것이 핵심인 것 같습니다.

 

X에 관련된 조건과 문제의 답을 연관 시켜보면, 연속된 X줄에서 찾게되는 오류의 개수를 최소로 해야한다는 것을 알 수 있습니다.

그 이유는 이 개수가 최소여야지만, 에디터가 해결할 오류의 개수를 최대로 할 수 있기 때문입니다.

 

따라서, 연속된 X줄 중에서 나올 수 있는 오류의 최소값을 구한 뒤, 이 최소값과 Y중 최대값을 오류의 총 개수에서 빼면 답이 나옵니다!

 

풀이

시간복잡도

이 번 문제는 문제의 개수 N과 오류의 개수 M의 크기가 상당히 큽니다 ( 1 <= N <= 2 * 10^7 , 1 <= M  <= min(N, 5 * 10^5) )

그러므로, 시간 복잡도에 대한 고민도 동반했습니다.

 

방법 1.

연속된 줄 X안의 오류의 최소값을 찾는 방법으로 우선 투 포인터를 생각해 냈습니다.

 

인덱스를 지정하는 i1, i2를 두고 min_value를 저장할 변수를 선언해주었습니다.

오류가 있는 줄의 번호는 error_list 리스트에 저장해두었습니다.

i1,i2=0,0
min_value = M

그리고, i1과 i2를 아래 조건을 만족하면서 전진시켜주었습니다.

1. i1 <= i2, i1 > i2가 될 경우 i2 += 1
2. error_list[i2] - error_list[i1] - 1 < X 일 경우 i2+=1
3. error_list[i2] - error_list[i1] - 1 < X 일 경우 기존 min_value와 (i2-i1-1)의 비교 이후 최소값을 min_value에 저장, i+=1
4. 1~3으, i2<M일 동안 반복한다.
5. M - (4.를 통해 얻어낸 값과 Y의 최대값)가 답이 된다.

방법 1 설명

i2와 i1이 인덱스를 이동하면서 최소의 오류값을 찾아내는 로직입니다.

 

2번과 같은 경우, 현재 i2, i1이 가리키는 오류값 사이의 내부의 줄 수가 X 보다 작으면 작성된 코드에서 오류가 없는 연속된 X줄이 존재해야 한다는 문제의 조건에 맞지 않으므로 i2를 1 더해줘서 더 많은 줄을 포함하도록 합니다.

 

3번과 같은 경우, 현재 i2, i1이 가리키는 오류값 사이의 내부 줄 수가 X 보다 크면 문제의 조건에 부합하므로 해당 내부 줄 수 안에 포함된 오류의 개수와 min_value를 비교해주면 된다.

while i2<M:
    if i1>=i2 or error_list[i2]-error_list[i1]-1<X:
        i2+=1
    else:
        min_value = min(min_value,i2-i1-1)
        i1+=1

그리고 마지막으로

 

방법 1의 문제점

위 코드의 문제는 i2가 M에 도달했을 경우 i1이 전진하면서 비교할 수 있는 것들을 하지 못하고 끝나게 된다는 것이다.

 

방법 1 추가

위 코드를 진행한 후 i1이 더 전진하면서 더 비교할 수 있도록 해줍니다.

이 때에도 X줄 이상일 경우만 값을 비교해주어야 하고, min_value와  M-i1-1을 비교해 더 작은값을 min_value에 저장해준다.

while i1<M and N-error_list[i1]>=X:
    min_value = min(min_value,M-i1-1)
    i1+=1

 

해결

연속된 X줄이라는 말을 통해 앞에서 부터 조금씩 값을 비교해봐야한다는 생각을 해야되고, N,M이 매우 큰 수 이므로 투포인터로 해결해야겠다는 생각을 하고, 빠진 케이스는 없는지 다시 한 번 확인해봐야 했던 문제라 맞왜틀을 엄청 했던 것 같습니다.

 

 

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

24453번: 디버깅

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