[Python 코테 입문] 2. (문제 3번) 연속된 '1'의 길이

🖥️ 입문자를 위한 코딩테스트 핵심 - Python (김태원, 인프런)

 

섹션2. 배열, 연결리스트, deque

 

(문제 3번) 연속된 '1'의 길이

매개변수 nums에 0과 1로 된 수열이 주어지면 1이 연속된 부분수열 중 가장 긴 부분수열의 길이를 반환하는 프로그램을 작성하세요.

 

입출력 예

nums	answer
[1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1]	5
[0, 0, 1, 0, 1, 0, 0]	1
[1, 1, 1, 1, 1]	5
[1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1]	3

 

제한사항

• nums의 길이 : 3 <= n <= 100,000

 

풀이

모른다.

 

정답 풀이

분석

첫 번째 제한사항에서 입력크기가 최대 100,000까지 들어오므로 효율성을 따지는 문제다.

배열을 순차탐색하며 풀면 되므로 시간복잡도는 O(n)이다.

 

풀이

def solution(nums):
  answer = 0
  maxLength = 0
  for x in nums:
    if x == 1:
      maxLength += 1
    else:
      # 기존까지의 최대길이와 현재 연속된 최대길이 중 더 큰 값을 저장한다.
      answer = max(answer, maxLength)
      # 0을 만나 연속된 1이 끝났으므로 maxLength를 다시 초기화한다.
      maxLength = 0
  # 배열의 맨 마지막에 연속된 1이 있을 경우 최대길이가 반영되지 않았으므로 한 번 더 최대길이를 비교하여 더 큰 값을 저장한다.
  answer = max(answer, maxLength)
  return answer;

print(solution([1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1]));
print(solution([0, 0, 1, 0, 1, 0, 0]));
print(solution([1, 1, 1, 1, 1]));
print(solution([1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1]));

5

1

5

3