반응형 Coding Test/Codility14 [ Codility 코딜리티 ] Lesson 4 MaxCounters Python 파이썬 풀이 // 문제 요약 N개의 0으로 초기화되어있는 카운터가 주어진다. 이때 카운터에 할 수 있는 연산은 increase(X) : X번째 항에 1을 더한다 max counter : 카운터의 모든 항을 카운터의 현재 최대값으로 바꾼다. 이 두가지 뿐이다. M개의 정수로 구성되어 있고 비어있지 않은 배열 A가 주어지면 아래와 같은 연산을 수행한다. A[K] = X 인 경우 X가 1에서 N사이 일때 increas(X), A[K] = N+1 일때는 max counter. 위의 연산들이 주어졌을때 N과 A가 주어지면 최종적으로 얻어지는 카운터를 return하는 함수를 만들어라 // 문제 풀이 슬슬 문제들이 복잡하고 난해해지기 시작한다. 그래도 잘 한번 따라가 보자. 이런 류의 문제들은 기믹을 빨리 파악하는 것이 중요하다.. 2021. 4. 17. [ Codility 코딜리티 ] Lesson 4 FrogRiverOne Python 파이썬 풀이 // 문제 요약 위치 0에서 폭이 X인 강을 건너 위치 X+1인 강의 반대쪽으로 가고자하는 개구리가 있다. 강물의 흐름을 무시할 수 있고 나뭇잎이 강 위로 떨어진다고 할때 (한번 떨어진 잎은 사라지지 않는다고 할때) 시간 K때 떨어진 나뭇잎의 위치는 A[K]이고 A는 N개의 정수로 구성된 비어있지 않은 배열이다. 1에서 X까지 모든 위치가 잎으로 채워지면 개구리가 건너갈 수 있다고 할 때 개구리가 강을 건널 수 있는 가장 빠른 시간을 구해라. 개구리가 강을 건널 수 없을 경우 -1을 return해라. // 문제 풀이 문제가 복잡하다. 하지만 간단하게 생각할 경우 "X 가 주어지면 1에서 X까지 한번 이상 등장하는 가장 작은 K를 구해라" 로 문제가 요약된다. 이렇게 핵심만 남기는 것이 실재로 개구리가 강.. 2021. 4. 17. [ Codility 코딜리티 ] Lesson 3 TapeEquilibrium Python 파이썬 풀이 // 문제 요약 비어 있지 않고 N개의 정수로 이루어진 배열 A가 주어질때 A가 한 테이프를 따라 매겨진 번호라고 하자. 0과 N 사이의 정수 P가 주어지면 A[0 ~ P-1], A[P ~ N-1] 으로 테이프를 나눈다고 할때 나누어진 두 테이프에 매겨진 값을 각각 모두 더하여 얻어진 두 값의 가장 작은 absolute difference는 얼마인가? // 풀이 이런 문제는 자칫 영어가 꼬이면 문제를 이해하는데 시간을 낭비하고 만다. 따라서 꼼꼼하게 차근차근 본문을 잘 읽어서 문제를 정확하게 이해해야 한다. 우선은 p를 옮겨가면서 p가 옮겨질때마다 양쪽을 모두 더하는 경우로 생각하기 쉬우나 그렇게 되면 p를 옮기기위해 N번 그리고 임의의 p에서 덧셈을 N번 하는 경우기 때문에 O(N**2)이 된다. 코딩.. 2021. 4. 17. [ Codility 코딜리티 ] Lesson 3 PermMissingElem Python 파이썬 풀이 // 문제 요약 N개의 서로 다른 정수들로 구성된 배열 A가 주어진다. 배열에 들어있는 정수들은 [1, (N+1)]의 범위를 가지며 정확히 하나의 원소가 사라져있다. 사라진 원소를 찾는 함수를 구현해라. // 풀이 이 문제는 collections페키지에 있는 Counter()를 알면 쉽게 풀리고 모르면 생각을 좀 해야할 수도 있는 문제다. 각 플랫폼마다 다르긴 하지만 코딜리티의 경우는 collections를 지원하고 있다. 따라서 이러한 점을 미리 파악하고 시험에 임하는 것이 더 많은 무기를 가지고 전장에 임하는 것과 같다. Counter()는 리스트를 입력받아서 element : the number of element 의 맵핑을 가지는 딕셔너리로 반환해준다. 코드를 보자. # you can write .. 2021. 4. 17. [ Codility 코딜리티 ] Lesson 3 FrogJmp Python파이썬 풀이 //문제 요약 개구리가 길을 건너고자 한다. 이 개구리는 지금 X위치에 있고 한번 점프할 때 마다 D 만큼 이동할 수 있는데 Y 보다 크거나 같은 지점까지 갈 수 있는 최소 점프 횟수는 얼마인가? // 풀이 이 문제는 while문 같은게 바로 떠오르는 아주 간단한 문제다. 하지만 X로 부터 Y 가 아주 멀고 D가 아주 작은 경우에는 while로 돌릴경우 시간 복잡도가 올라갈 수 있다. 따라서 X, Y 사이의 거리를 먼저 구하고 D로 나누어 주는 방식으로 루프를 피해서 간단히 계산할 수 있다. while의 경우 O(n)이 걸릴 것으로 예상되고 나눗셈의 경우 O(1)이 걸릴 것으로 예상되므로 나눗셈을 선택하는 것이 옳다. 코드를 먼저 보자. def solution(X, Y, D): # write your c.. 2021. 4. 17. [ Codility 코딜리티 ] # Lesson 2 OddOccurrencesInArray python 풀이 // 문제 요약 비어 있지 않은 리스트 A 가 있는데 홀수개의 정수 N 들을 담고있다. 이 N중에서 짝을 이룰 수 없는 정수가 하나 존재한다. 짝을 이룰 수 없는 정수를 출력해라. 예를 들어 A = [ 9, 3, 9, 3, 9, 7, 9 ] 인경우 7이 반환되어야 한다. //풀이 처음에는 two-pointer 같은 방법들로 짝을 이룰경우 소거하는 방식을 생각했으나 그냥 개수를 세어본 후 홀수개의 원소를 반환하면 되는 방법이 가장 간단했다. 물론 1인 경우 반환을 생각해서 한번 틀렸고 이것을 홀수로 고치니까 풀렸다. 이런 사소한 부분들을 생각해내는 훈련을 하는 것이 코딩테스트 문제풀이의 가장 좋은점이 아닐까 한다. 개수를 세는 방법을 쓰기 위해서는 collections 안에 있는 Counter 를 이용해서.. 2021. 4. 11. 이전 1 2 3 다음 반응형
