[Python] BOJ 22114 - 창영이와 점프

https://www.acmicpc.net/problem/22114

22114번: 창영이와 점프

# 모든 케이스를 다 확인하기에는 N^2이 소요되어서 시간초과가 날 것이라 예상해

   '투 포인터' 알고리즘을 사용해서 풀었다. (이 코드가 투 포인터가 맞나 싶긴한데...)

 

1. 반복문을 돌며 i가 N-1이거나 j가 N-1이 되면(마지막까지 도달한다면) break를 한다.

 

2-1. i, j를 0, 0으로 설정하고 L[j]가 K보다 작거나 같으면 cnt와 j를 1증가시킨다.

2-2. L[j]가 K보다 크고 점프를 할 수 있으면, 점프를 하고 cnt와 j를 1증가시킨다.

    (점프한 위치를 check에 저장)

2-3. L[j]가 K보다 크고 점프를 할 수 없으면, i를 점프한 위치 다음인덱스로 옮기고

      j도 i와 같은 위치로 옮기고 answer에 현재 cnt와 answer중 큰 값을 저장한다.

      다시 cnt를 시작하므로 cnt=1, jump=0, check = 0으로 설정해준다.

 

3. 마지막까지 도달했을 때 cnt값과 answer 중 큰 값을 출력한다.

 

import sys
input = sys.stdin.readline
N, K = map(int,input().split())
L = list(map(int,input().split()))
i, j, cnt = 0, 0, 1
check, answer, jump = 0, 0, 0
while True:
	if i == N-1 or j == N-1:
		break

	if L[j] <= K:
		cnt += 1
		j += 1
	elif L[j] > K:
		if jump == 0:
			jump += 1
			cnt += 1
			check = j
			j += 1
		else:
			i = check + 1
			j = i
			answer = max(answer, cnt)
			cnt, check = 1, 0
			jump = 0
print(max(cnt, answer))

(solved.ac 티어: 실버 2)