PassingCars coding task - Learn to Code - Codility
Count the number of passing cars on the road.
app.codility.com
동쪽으로 이동하는 차를 P(0), 서쪽으로 이동하는 차를 Q(1)라할 때 두 차가 서로 지나칠 때의 (P, Q)쌍 수를 구하여라
P가 먼저 등장해야하며 (P, Q) 쌍을 구할 때 P 이후에 등장하는 Q만 고려해야한다.
예로 [0, 1, 0, 1, 1]이 주어질 때 0은 Q, 1은 P를 나타내고 인덱스가 0일 때 P가 등장한 이후 인덱스가 1, 3, 4일 때 Q가 등장한다.
이를 순서쌍으로 표현하면 (0, 1), (0, 3), (0, 4) 이고 모든 순서쌍을 구하면 (0, 1), (0, 3), (0, 4),(2, 3), (2, 4) 로 답은 5 이다.
* 1000,000,000을 초과하면 -1을 반환해야한다.
첫 번째 시도 100%
def solution(A):
answer = 0
p_list = []
for i in range(len(A)):
if A[i] == 0:
p_list.append(i)
else:
answer += len(p_list)
return -1 if answer > 1000000000 else answer0(P)가 등장한 이후의 1(Q)만 세야한다는 점을 중점으로 생각하니 쉽게 풀린 문제
- 0가 등장할 때마다 p_list에 등장한 위치의 인덱스를 저장한다.
- 1이 등장하면 앞에 등장한 0들과 순서쌍을 이룰 수 있음으로 지금까지 나온 0의 수가 곧 순서쌍의 수
- 0의 수는 p_list의 길이(p_list에 0의 인덱스가 저장되어있음으로)
CountDiv coding task - Learn to Code - Codility
Compute number of integers divisible by k in range [a..b].
app.codility.com
문제를 잘못 이해하여 시간이 조금 소요된 문제
첫 번째 시도 25~50%
처음에는 A부터 시작해서 B까지 K만큼 이동했을 때 몇개의 수가 나올 수 있는지 구하는 문제로 이해했다.
문제의 예시처럼 (6, 11, 2)가 주어지면 6부터 2씩 이동하여 6, 8, 10 이렇게 3개해서 답이 3인줄,,
def solution(A, B, K):
return trunc((B-A)/K) + 1- 처음에 ceil((B-A)/K)이라고 했지만 딱 떨어지는 경우 마지막 숫자가 포함이 안되서 어찌저찌 버림 + 1로 바꾸었다.
두 번째 시도 37%
문제를 다시 읽어보니 첫 시작이 A는 맞지만 카운트에 포함되는 수가 A부터인것이 아니라 K로 나눠지는 수부터 인것이였다,,
{ i : A ≤ i ≤ B, i mod K = 0 } 이 말처럼 A부터 B까지 수들 중 K의 배수들(K로 나눴을 때 나머지가 0)을 구하는 문제였다.
def solution(A, B, K):
for i in range(A, B+1):
if ((i % K) == 0) and (i != 0):
return ceil((B-i)/K)
return ceil((B-i)/K)- 카운트해야하는 [A, B] 중 가장 작은 K의 배수를 구하기 위해 for문을 돌려 K의 최소 배수 i를 구하고 i부터 B 사이 K가 몇번 들어가는지 구하였다.
- i가 0일때는 제외해야하는 줄 알고 조건에 i가 0이 아닌 조건을 포함시킴
세 번째 시도 100%
def solution(A, B, K):
for i in range(A, B+1):
if ((i % K) == 0):
return B//K - i//K + 1
return B//K - A//K- 알고보니 범위 안의 0은 무조건 포함된다. 0은 나머지가 언제나 0이기때문에,, 흥
- 조건문에 해당할 때만 1을 더해준 이유는 i//K(i까지의 K 배수 개수)에 i까지 포함되어있어 다시 1을 더해준다
다른 사람 풀이 1
def solution(A, B, K):
return B//K - (A-1)//K굳이 반복문을 돌려 K의 배수를 안찾고 {B까지 K의 배수 개수(B//K)}에서 {A-1까지의 K 배수 개수((A-1)//K)}를 빼서 구한 풀이
- A-1인 이유는 A는 포함되어야하기 때문에 A-1까지 K의 배수를 구한 것
GenomicRangeQuery coding task - Learn to Code - Codility
Find the minimal nucleotide from a range of sequence DNA.
app.codility.com
영어다보니 확실히 문제를 해석하는데 조금 시간이 걸리는 듯 하다 ㅠㅠ 구글을 참고함
A(1), C(2), G(3), T(4) 이렇게 대응관계를 갖는 유전자(letters)가 있다. S는 앞의 알파벳이 나열된 유전자 문자열이고 유전자 P와 Q는 S를 슬라이싱할 첫 인덱스(P)와 마지막 인덱스(Q)이다. 슬라이싱된 문자열 안에서 가장 숫자가 낮은 유전자(import factor)를 구하면 된다.
문제 예시처럼 S=CAGCCTA, P=[2, 5, 0], Q=[4, 5, 6]가 입력되었을 때 아래 표에 의해 답은 [2, 4, 1]이다.
| i | P[i] | Q[i] | S[p:q+1] | letters | min letter(int) |
| 0 | 2 | 4 | S[2:5] = GCC | C(2), G(3) | 2 |
| 1 | 5 | 5 | S[5:6] = T | T(4) | 4 |
| 2 | 0 | 6 | S[0:7] = CAGCCTA | A(1), C(2), G(3), T(4) | 1 |
첫 번째 풀이
시간복잡도때문에 당연히 안되는 코드, 문제 이해를 위해 빠르게 풀어봤다.
def solution(S, P, Q):
answer = []
letters = {'A': 1, 'C': 2, 'G': 3, 'T': 4}
m = len(Q)
for i in range(m):
p, q = P[i], Q[i]
tmp_s = S[p:(q+1)]
tmp = 100
for j in tmp_s:
tmp = min(tmp, letters[j])
answer.append(tmp)
return answer- 문제 내용 그대로 주어진 인덱스로 슬라이싱하여
- 슬라이싱된 문자열 안에서 가장 작은 글자를 찾아 정답 리스트에 추가한다.
두 번째 풀이 100%
도저히 푸는 방법이 생각 안나길래 구글링해서보니 다들 in 메서드를 사용한 것이다.. 그래서 나도 쓰니 100%로 통과
in 메서드도 O(N) 시간복잡도로 알고있는데 이상.. 파이썬만 가능하다는 얘기도 있던데 뭔가 잘못된 테스트케이스 설계를 오묘하게 빠져나간듯하다 ㅎ..
def solution(S, P, Q):
answer = []
m = len(P)
for i in range(m):
p, q = P[i], Q[i]
tmp_s = S[p:(q+1)]
if 'A' in tmp_s:
answer.append(1)
elif 'C' in tmp_s:
answer.append(2)
elif 'G' in tmp_s:
answer.append(3)
else:
answer.append(4)
return answer
다른 사람 풀이
in 메서드를 사용하지 않은 풀이는 대체로 2차원 배열을 만들어 푼듯
def solution(S, P, Q):
M = len(P)
N = len(S)
A = [[0, 0, 0, 0]]
counter = [0] * 4
result = []
for i in S:
if i == "A":
counter[0] += 1
A.append(counter[:])
elif i == "C":
counter[1] += 1
A.append(counter[:])
elif i == "G":
counter[2] += 1
A.append(counter[:])
elif i == "T":
counter[3] += 1
A.append(counter[:])
for i in range(M):
for j in range(4):
val = A[Q[i]+1][j] - A[P[i]][j]
if val != 0:
result.append(j + 1)
break
return result4x4 크기의 이차원 배열을 만들어 뭐 어떻게 하는거 같은데 아직 잘 모르겠다.....
MinAvgTwoSlice coding task - Learn to Code - Codility
Find the minimal average of any slice containing at least two elements.
app.codility.com
문제 내용은 쉽다. 구간의 길이가 최소 2가 되도록 리스트를 슬라이싱하고 리스트의 평균이 최소가 되는 슬라이스 인덱스의 시작값을 구하는 문제이다.
이 문제는 시간복잡도가 관건이다. 쉽게 풀면 O(N^2)가 나오는데 이를 O(N+M)로 줄이는 것이 어렵다ㅠ
결국 못풀고 구글링하여 다른 사람 코드 참고해서 품,, ㅠ 접근 방식이 조금 어려웠다. 다른 사람 풀이 보니 안봤으면 못풀었을듯^_^
첫 번째 시도 60%
시간복잡도 O(N^2)로 timeout
def solution(A):
min_avg = 1000000
answer = 100000
for i in range(len(A)-1):
tmp_sum = A[i]
for j in range(i+1, len(A)):
tmp_sum += A[j]
tmp = tmp_sum / (abs(i-j)+1)
if min_avg > tmp:
min_avg = tmp
answer = i
return answer말 그대로 길이가 2 이상이 되는 모든 경우의 평균을 구하여 최소값을 반환했다.
*** 문제를 풀기 위해선 중요한 수학적 지식(?)을 알아야 하는데 ***
a<b 일 때 (a, b)의 평균은 a보다 크고 b보다 작다.
a+b < c+d 일 때 (a+b)와 (c+d)의 평균은 (a+b)보다 크고 (c+d)보다 작다.
예) 1+5 < 3+5일때 6 < (6+8)/2=7 < 8
평균들의 평균은 각 인자들의 평균과 같다.
(1, 2, 3, 4)가 있을 때 전체 평균은 2.5이고 (1, 2) = 1.5, (3, 4) = 3.5이며 (1.5, 3.5) 또한 2.5이다.
종합적으로 생각해보면 길이가 4인 리스트는 고려하지 않아도 된다. 길이가 4인 경우 길이가 2인 부분집합의 평균이 더 작기 때문이다.
최소 길이가 2이고 4 이후부터는 부분집합의 평균이 더 작음으로 우리는 길이가 2일때와 3일때만 생각하면 된다.
사실 아직도 이해가 완벽히 되지는 않았다.
두 번째 시도 100%
위의 수학적 지식을 적용하여 길이가 2일때와 3일때만 고려한 풀이
def solution(A):
min_avg = 1000000
answer = 100000
for i in range(len(A)):
try:
# 길이 2
if min_avg > (A[i]+A[i+1] )/ 2:
min_avg = ((A[i]+A[i+1]) / 2)
answer = i
# 길이 3
if i < len(A)-2:
if min_avg > (A[i] + A[i+1] + A[i+2]) / 3:
min_avg = (A[i] + A[i+1] + A[i+2]) / 3
answer = i
except:
break
return answer반복문 돌릴때 i 범위를 고려하기 귀찮아서 try/except로 인덱스를 벗어나는 경우를 잡아 break 해주었다.
여기까지 풀고 다시 백준을 풀러갔는데... 하.. 난 아직 멀어따.. 코테 접수하기는 개뿔
| [BAEKJOON] 완전탐색 뽀개기 | 파이썬 | 백준 Lv11. 브루트 포스 문제풀이 (0) | 2022.02.11 |
|---|---|
| [CODILITY] 코딜리티 문제풀이 파이썬 L6.Sorting (0) | 2022.01.21 |
| [CODILITY] 코딜리티 문제풀이 파이썬 L3.TimeComplexity ~ L4.CountingElements (0) | 2022.01.17 |
| [CODILITY] 코딜리티 문제풀이 파이썬 L1.Iterations ~ L2.Arrays (0) | 2022.01.14 |
| [PROGRAMMERS] 프로그래머스 코딩테스트 연습 > Level 2 & python3 문제풀이 ~ 11.04 (0) | 2021.11.05 |
댓글 영역