본문 바로가기
반응형

Coding Test/Codility14

[ Codility 코딜리티 ] Lesson 5 PassingCars Python 파이썬 풀이 // 문제 요약 동쪽으로 가는 차량을 0, 서쪽으로 가는 차량을 1 이라고 할때 N개의 1과 0으로 구성된 A중에서 지나간 차량의 수를 구해라 단 지나간 차량이란 0 1e9: return -1 return passing_cars P가 반드시 Q보다 작고 A[P]가 반드시 0이어야하는 점을 근거로 A[P] == 0 이면 P 이후의 모든 1의 개수를 리턴해라 라는 문제로 볼 수 있다. 여기서는 친절하게도 0과 1로 값을 주기 때문에 군더더기 없이 깔끔하게 풀 수 있다. 2021. 4. 17.
[ Codility 코딜리티 ] Lesson 5 MinAvgTwoSlice Python 파이썬 풀이 // 문제 요약 주어진 array A에 대해서평균이 가장 낮은 subarray의첫번째 index를 return해라 // 문제 풀이 머리가 많이 아픈 문제다.답을 한번 알고나면나올때마다 풀 수 있지만답을 알기전까지는 결코 풀 수 없다... 구글링을 통해서 많은 풀이를 봤는데다들 비슷비슷하게 푼 것으로 봐서이게 거의 유일한 풀이가 아닐까 싶다. 우선 subarray와 subsequence 부터 알아야한다.subarray는 기존의 array에서 slicing하여만드는게 가능하고subsequence는 기존의 array를 스캔하여원하는 값만 모아둔 것을 말한다. 그러니까[ 1, 3, 5, 7, 9 ]에서[1, 3]이나 [7, 9]는 subarray[ 1, 5, 9 ]는 subsequence이다. 어떻게 생각해도 .. 2021. 4. 17.
[ Codility 코딜리티 ] Lesson 5 GenomicRangeQuery Python 파이썬 풀이 // 문제 요약 DNA는 A,C,G,T라는 문자들로 구성된 S라는 긴 string으로 나타내 진다. A,C,G,T는 각각 1,2,3,4 의 impact factor를 가진다. S의 길이가 양의 정수 N이고 M개의 Query인 P,Q가 요청될때 S[P[K]] 이상 S[Q[K]] 이하의 가장 작은 impact factor는 얼마인가? 쿼리의 길이가 M 이므로 길이가 M인 배열로 반환하라. // 문제 풀이 아주 전형적인 Prefix sum algorithm 문제다. Prefix sum 알고리즘은 알면 풀고 모르면 못푸는 전형적인 문제라고 생각한다. 그러니까 아주 긴 데이터로 부터 아주 긴 쿼리가 요청될때는 O(M * N)이 되므로 사실상 O(N**2) 보다 더 커질 수도 있다. 따라서 이걸 O(N+M)까지 낮.. 2021. 4. 17.
[ Codility 코딜리티 ] Lesson 5 CountDiv Python 파이썬 풀이 // 문제 요약 A, B, K 세 정수가 주어지면 A 이상 B 이하의 정수 중 K의 배수는 몇개인지 구해라. // 문제 풀이 이 문제는 일종의 기믹을 쓴다. 수학적인 특징을 이용하는 것인데 어떤 구간을 K마다 자르면 완전한 subarray에는 반드시 1개의 K의 배수가 존재한다는 특성을 이용한다. 즉 주어진 구간의 길이를 K로 나눠서 마지막에 남는 나머지가 있다면 그 나머지 안에 K의 배수가 있는지만 검사해서 리턴하면 되는 방식이다. 코드부터 보자. # you can write to stdout for debugging purposes, e.g. # print("this is a debug message") def solution(A, B, K): # write your code in Python 3.6.. 2021. 4. 17.
[ Codility 코딜리티 ] Lesson 4 PermCheck Python 파이썬 // 문제 요약 주어진 배열이 permutation 인지 확인하고 맞으면 1 아니면 0을 반환해라. // 문제 풀이 permutation은 순열로 수학시간에 nPm 과 같이 쓰던 그걸 말한다. 여기서는 nPm일때 n=m인 경우를 말하고 1부터 A의 길이인 N 까지 모든 수를 한번씩만 사용해서 만든 순열을 의미한다. 비슷한 문제가 Lesson 3에서 한번 나온적이 있으므로 자세한 설명은 생략하도록 한다. 2021.04.17 - [Coding Test/Codility] - [ Codility 코딜리티 ] Lesson 3 PermMissingElem Python 파이썬 풀이 [ Codility 코딜리티 ] Lesson 3 PermMissingElem Python 파이썬 풀이 // 문제 요약 N개의 서로 다른 .. 2021. 4. 17.
[ codility 코딜리티 ] Lesson 4 MissingInteger Python 파이썬 풀이 // 문제 요약 N개의 정수로 구성된 배열 A를 받으면 A에 속해있지 않은 양의 정수 중 최소값을 구하는 함수를 짜라. // 물제 풀이 문제가 간단하다. 풀이도 간단할지 한번 보자. 우선은 양의 정수 중에서 최소값을 구하므로 A의 최대값이 음수인 경우는 무조건 1이 return되어야 한다. 그리고 중복된 값들은 그냥 지나가도 되므로 Counter의 key만을 이용할 수 있다는 것을 알 수 있다. 코드부터 한번 보자. # you can write to stdout for debugging purposes, e.g. # print("this is a debug message") import collections import sys def solution(A): # write your code in Pytho.. 2021. 4. 17.
반응형

티스토리툴바