Notice
Recent Posts
Recent Comments
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 |
Tags
- lambda
- FPS
- flask
- C#
- 우분투
- 그래픽노블
- Python
- Project Euler
- 먹방
- 프로젝트오일러
- certbot
- 인디게임
- codility
- 몽골여행
- 중국맛집
- 스팀
- github
- AWS
- django
- https
- 워킹데드
- API
- coursera
- 컴퓨터네트워크
- pycon
- 퍼즐게임
- 파이썬
- 알고리즘
- 블라디보스토크
- 게임
- Today
- 134
- Total
- 324,498
YUDA't
[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:]))
위와 같이 간지나게 풀었는데...
루프를 돌 때마다 리스트 A의 합을 구하는 건 너무 멍청했다.
이번 기회로 sum()이 꽤 많은 시간을 차지할 수도 있다는 걸 알았다.
어쨌든 아래처럼 고쳤더니 무난히 통과!
def solution(A): left_sum = A[0] right_sum = sum(A[1:]) min_diff = abs(left_sum - right_sum) for i in range(1, len(A)-1): left_sum += A[i] right_sum -= A[i] if abs(left_sum - right_sum) < min_diff: min_diff = abs(left_sum - right_sum) return min_diff
더하기 1번과 N번의 차이..
최종 시간복잡도는 O(N)이 나왔다.
'개발 > 알고리즘 문제' 카테고리의 다른 글
[Codility] PermCheck (0) | 2017.11.09 |
---|---|
[Codility] FrogJmp (0) | 2017.11.07 |
[Codility] PermMissingElem (0) | 2017.11.05 |
[Codility] CyclicRotation (0) | 2017.11.04 |
[Codility] OddOccurrencesInArray (0) | 2017.11.02 |
- Tag
- Python, TapeEquilibrium, 알고리즘, 파이썬
0 Comments