[Codility] FrogRiverOne
https://app.codility.com/programmers/lessons/4-counting_elements/frog_river_one/start/
개구리 강 건너는 문제
숫자 X와 리스트 A가 주어지고, 주어진 리스트 A에 1~X 가 모두 나오는 최소 step을 구한는 문제 (1~X 중 하나라도 없으면 -1 리턴)
나의 첫 번째 풀이
리스트A의 범위가 1 ~ 10만이기 때문에 O(N)의 방법을 찾아야 했다.
내가 생각한 방법은 1~X의 합을 구한 뒤, 각 숫자가 최초로 나올 시에만 A의 원소만큼 빼주어 합이 0이 되면 원소가 모두 나왔다고 가정하고 해당 인덱스를 반환하는 방식으로 풀었다.
def solution(X, A): # write your code in Python 3.6 all_sum = sum(range(X+1)) # 1~X의 합 river_step = [0 for _ in range(X)] for i in range(len(A)): if river_step[A[i]-1] == 0: all_sum -= A[i] if all_sum == 0: return i river_step[A[i]-1] = 1 return -1 pass
결과는 O(N)이 나오긴 했지만 더 깔끔한 방법이 무조건 있다고 생각하였다.
나의 두 번째 풀이
두 번째 풀이는 set와 enumerate() 함수를 사용하였다.
set는 중복을 허용하지 않기 때문에 같은 수를 아무리 add해도 원소 자체는 그대로이다.
enumerate()는 순서가 있는 자료구조의 인덱스와 원소값을 리턴해주기 때문에 더 깔끔한 for문을 작성할 수 있다.
def solution(X, A): # write your code in Python 3.6 num_set = set() for index, value in enumerate(A): num_set.add(value) # 매 반복마다 쓸 데 없이 add를 해주긴 하지만 O(N)는 변하지 않는다. if len(num_set) == X: return index return -1 pass
Author And Source
이 문제에 관하여([Codility] FrogRiverOne), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@sloools/Codility-FrogRiverOne저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)