본문 바로가기
반응형

개발/알고리즘 문제56

[Codility] FrogRiverOne 0. 문제position 0에 있는 개구리가 하나 있다. 이 개구리는 X를 이동하여 X+1의 위치로 이동하고 싶어한다.(그러니까 A[0]에서 A[X+1]로 이동한다는 거) 리스트 A는 개구리가 건널 수 있는 잎의 위치리스트다. 배열의 index는 초(second)이고, value는 나뭇잎이 놓이는 위치이다. 그러니까, 개구리가 5로 이동하고 싶은데 리스트 A가 [1, 3, 1, 4, 2, 3, 5, 4] 면 6초가 지나야 개구리가 원하는 위치로 갈 수 있다는 거. 만약 배열이 [1, 3, 1, 3, 4] 이라면 개구리는 원하는 곳에 가지 못하고, 이럴 땐 -1을 리턴해야 한다. X와 A가 파라미터로 주어질 때, 개구리가 원하는 위치로 이동할 때까지 걸리는 시간을 구하라. 1. 답변 문제를 처음에 잘못 이.. 2017. 11. 10.
[Codility] PermCheck 0. 문제N개의 상수로 이루어진, 비어있지 않은 리스트 A가 있다. A 순열(permutation)은 1부터 N 까지의 중복되지 않는 숫자의 연속이다. 주어지는 리스트 A가 순열인지 판별하라. 1. 답변 이번 것도 난이도가 매우 낮았다. def solution(A): sorted_a = sorted(set(A)) if len(sorted_a) == len(A) and sorted_a[-1] == len(A): return 1 else: return 0 시간복잡도는 O(N) or O(N*log(N)) 2017. 11. 9.
[Codility] FrogJmp 0. 문제작은 개구리 하나가 X에서 Y(혹은 그보다 더 멀리)로 이동하고 싶어한다. 개구리는 매 점프마다 D만큼 이동한다. 개구리가 원하는 위치에 도달할 때까지 필요한 최소 점프 횟수를 구하라. 1. 답변 Codility에서 print()가 된다고 python3를 지원한다고 생각했던 게 오산이었다. 문제를 읽고 왜 이렇게 쉽지 하고 1-2분 만에 풀었는데, 정답률 44%.. python2와 python3의 round() 함수가 다른 값을 내놓는 다는 걸 처음 알았다.(python2를 쓴 적이 거의 없으니..) 처음 짰던 코드는 이렇다. def solution(X, Y, D): return int(round((Y - X) / D + 0.5)) 깨달음(?)을 얻고 난 뒤의 코드. 시간복잡도 O(1)def s.. 2017. 11. 7.
[Codility] TapeEquilibrium 0. 문제 비어있지 않은 리스트 A에 N개의 숫자가 있다.(N은 2와 100,000 사이의 숫자) 그리고 0 < P < N 의 조건을 가지는 자연수 P가 있다. 자연수 P에 의해 리스트 A는 이렇게 둘로 나눠지게 된다. A[0], A[1], ..., A[P − 1] A[P], A[P + 1], ..., A[N − 1] 이때 |(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])| 의 가장 작은 값을 구하라. 1. 답변 처음에 답변은 다 맞췄으나 TimeoutError가 났다. for p in range(1, len(A)): diff = abs(sum(A[:p]) - sum(A[p:])) 위와 같이 간지나게 풀었는데... 루프를 돌 때마다.. 2017. 11. 6.
반응형

티스토리툴바