Codility for Programmers

오늘 공부한 codility 문제들 자기전에 한번 정리해본다.

Lesson은 1부터 17까지 + 90, 91, 92, 99

 

총 21개 Lesson으로 구성되어있으며 각 레슨마다 강의가있지만 그냥 패스하고 풀어봤다.

 

솔직히 만만하게봤지만 생각보다 머리가 팍팍 안굴러간다.

 

우선 오늘은 Lesson 4 Painless(easy) 등급 문제까지 풀어보았다.

 

기억나는만큼만 정리해본다.

Lesson1. Iterations
 BinaryGap - int를 binary로 바꿔서 그 사이에 0 갭 숫자 맥시멈을 찾는거

Lesson2. Arrays
 CyclicRotation - array 안에 shift 나온대로 한칸씩 옮기는거
 OddOccurrencesInArray - pair 맞추고 남은거 뽑아내기, XOR 로 하는방법있는데 이해안되고, 다시풀어봐야할듯

Lesson3. Time Complexity
 FrogJmp- 복잡도 O(1) 수준에서 구할수있는 그냥 산술연산 문제.
 PermMissingElem - 빠진수 찾기. SUM을 먼저한다음에 원래 맞아야하는 SUM에서, 배열 SUM을 뺐다.  int, long 관련된 상세제약을 안읽어서 점수깎였다.
 TapeEquilibrium - index 기준으로 앞에까지 합 뒤에 합을 조사해서 차이가 젤 작은 i를 정하는건데  SUM이 양수일거라는 착각, index 계산 기준을 착각해서 고생했다. 다시풀어볼만함

Lesson4. Counting Elements
 PermCheck - 퍼뮤테이션. 정렬해서 for문돌려서 인덱스랑 같은지 조사
 FrogRiverOne - Count로 풀줄은 생각못했다. Boolean array만들어서 값별로 T/F 저장하고 True 카운트가 목적값과 같은지 조사해서 맞아떨어지면 인덱스 리턴

 

일단 쭉쭉 풀어볼예정.

--------

2일차

Lesson5. Prefix Sums
 PassingCars - 음.... 0,1 조합으로 둘이 다른 조합을 세는 문제인데 별생각없이 포문 2개돌리면 역시 복잡도가 올라간다. 0이 나올때마다 더해주는 숫자를 늘려주는 식으로 해결 0한개면 1나올때마다 1씩더하고 0이 2개나오면 그때부턴 1나올때마다 2씩더함.

Lesson6. Sorting
 Distinct - ArrayList의 contains를 사용했으나 ArrayList는 순서가 의미있는 자료구조기때문에 복잡도가 높아진다. HashSet을 사용해서 구현하니 복잡도가 줄어서 훨씬 빠르다. 그래서... 점수깎임 ㅋ
 MaxProductOfTree - 3 수를 곱해서 제일큰값 만드는건데 정렬해서 젤큰값 세개가 나올수있는 경우의수 4가지를 생각해서 비교함. easy
 Triangle - 수업시간에 언제인가 배운건데... 부등호를 몰라서 포문을 세번이나돌렸다. 부등호 3개중 1개만 체크하면 되기때문에 맞춰서돌리면 됨. 다시풀만함

Lesson90. Tasks from Indeed Prime 2015 challenge
 Longest Password - 문자/ 특수문자 걸러서 문자개수세고 숫자개수 세서 valid 체크하는건데 특수문자체크를 빼먹었다.

Lesson92. Tasks from Indeed Prime 2016 College Coders challenge
 Tennis tournament - 그냥 단순계산.

Lesson99. Future training
 SqlSum - 간단한 쿼리
 TreeHeight - 2진 트리 길이 구하기. 재귀호출로 풀었다.
 StrSymmetryPoint - 문제를 잘이해 해야한다.... if문을 배열할거면 문제를 제대로읽고 크리티컬 케이스를 연구해야 한다. String은 Array에 담지 않아도 charAt을 사용해서 접근할 수 있다.

 

2일차까지 Prefix Sum, Sorting까지풀고 뒤에 출제문제 중 쉬운것들만 일단 풀었다.

 

-----

 

3일차

7. Stack and Queue

 brackets - 스택을쓰는건 맞는데 닫히지 않은경우...에 대한 예외케이스에 대해 내가 너무 무지했다. 예외처리를 신경써서 해야한다.... 다시풀어야해 꼼꼼하게

 fish - Stack을써서 풀어야되는데 어떻게 반복문을 구성할지에 대해 난감했다. 다 통과한녀석들을 따로 카운트하면되는건데 그걸 놓쳤고, 꼭 인덱스만 스택에 넣어야겠다고 생각해서 또 틀렸다. 이건 완전 기억해야되는 문제. peek을 여기서 처음봄.

 Nesting - Brace 맞추는문제. Stack으로 해결, 전체가 다 감싼케이스만  Nested 인데 나는 앞에서 짤린케이스를 생각안했다. 더 꼼꼼해야되

 StoneWall - Stack사용. 값이 커질때만 push하고 pop카운트를 세는방식으로 계산함. 두 개가 같을때..를 빼먹었고, 뺏다가 다시 푸시할때를 또 빼먹음.. 젠장

 

8. Leader

 Dominator - 대표값구하기 nLogN으로일단 구해봄, 또 널체크를 안함.... array 복사는 그냥 넣는다고 되는게 아니다.system.arraycopy(src, 0, dest, 0, length) 요래해야된다.

 EquiLeader - 리더를구하고 그 둘을 나눴을때 양쪽다 리더가 유지되는 경우의 수를 찾는거. 일단쥐쥐

 

오늘은 여기까지하고 일단 퇴근하도록한다. 죽것다 머리아파. Lesson 7, 8 까지 품.

9, 10, 11, 12, 13, 14............. 시바?

 

 

4일차

9. Maximum slice problem

 MaxProfit - O(n) 알고리즘을 기억해야되겠다 ending = Max(0, ending+current), slice = Max(slice, ending), return slice; 더했을때 음수가되면 걍 걔는 째버리고 다음칸부터 계산한다. 이걸 Max(0, ending+currnet) 로 표현했다. 대단하다. 0보다 작은건 버린다.  slice는 항상 최대값이 남게된다. current를 다음칸 - 현재칸으로 구성하고 for문을 제일뒤에꺼 앞에까지만 돌렸다.

 MaxSliceSum - O(n), ending, slice  이용해서 풀었다. 바보같이 아까처럼 다음거랑 차이가 파라미터인줄알고 length-1까지만 계산함. 초기값을... 세팅을 잘못하면 또 다르게나옴. 하.. 이건 0이랑 ending을 비교하는게 아니라. 최소값이 각 아이템 하나 이니까 A[i]랑 비교했어야되고 처음값도 세팅했어야한다. 젠장

 

10. Prime Numbers

 CountFactors - 약수구하기. while(i*i<N) 일때 나눠지면 +2 본인이 제곱근이 있으면 +1, i++ 외우자. 근데 이경우엔 sqrt(N) 포함 검사했고 i*i==N 이면 하나를 뺐다.

 MinPerimeterRectangle - 가능한 약수 조합에서 최소 지름 구하기. 최대값 하나 미리 세팅해두고 약수인경우 min값을 각각 구해서 비교한다.

 

11. Sieve of Eratostenes - 표 만들어두고 지워가면서 소수 찾는 알고리즘.

 

12. Euclidian algorithm 유클리드 호제법. a==b이면 a, a>b -> gcd(b,a-b) 반복 , 반대의경우 (b, b-a) 반복
                                                         lcm = a*b / gcd

 Chocolates by Numbers - 나머지 구하는 연산이라 그냥 했음, 초기화하는 for문을돌리는게 또 좀 그럼.. int배열초기화시 0이고, String배열 초기화시  ""이다 bool배열 초기화하면 false 기본 object이면 null 기본이란다. 알고있자. 근데 이렇게하면 시간초과. 최대공약수로 N을 나누면 된다고한다. 그냥 한번더 풀어보자. 그냥 저렇게 공통으로 구하는... 그게나오면 최대공약수를 한번 의심해보자
 복잡도에 문제가있는지 recursive로 푸니까 마지막 한개가 overflow난다. while문으로 구현한걸 보면 N>M 일때 while(N%M) N= N%M; N,M swap. 나중에 나온 M이 GCD 이렇게 풀면 overflow안나고 깔끔하다. .... .그렇다

 

13.Fibonacci numbers - 앞에거와 그 다음거를 더한게 다음수가 나오는 수열

14.Binary serach algorithm - 이진 검색 반짤라서 검사하는거 while(first<=last) mid == target return, if(mid > target) last = mid-1, if(mid<target) first=mid+1. 실패시 -1;

 

15.Carterpillar method
 CountDistinctSlices  - 전~~혀 모르겠다 (http://blog.naver.com/PostView.nhn?blogId=ajoucyer&logNo=221335390029&parentCategoryNo=1&categoryNo=&viewDate=&isShowPopularPosts=true&from=search)
 CountTriangles - y=x+1, z=x+2 로 해서 조건 맞는친구 있을때 z부터 키워주고.. z-y만큼 더해준다. 아 그사이에있는친구는 다 된다고보는거구나. y와 z사이가 1이상 벌어지면 y를 키워주고, 둘다 해당안되는경우 y, z 둘다 하나씩 키워준다. 여튼 어렵다.
 AbsDistinct - HashSet으로 count 세서 해결

16.Greedy algorithms - 동전 거슬러주기 생각하면 된다. 앞에 놓인 것부터 해결하고 그다음으로 넘긴다. 재귀호출
 TieRopes - 난 정렬해서 생각했는데.. 그냥 인접한 두 줄이라네??  그냥 더해서 계산하니 ... 100 편..안..
 MaxNonoverlappingSegments - 이전거의 끝값을 유지하고 현재값의 시작과 비교해서 안겹치면 ++ 하는걸로 보이는데.. 머리가굳었는지 전혀생각이 안났다... 일단 끄읏

 

17.Dynamic programming - https://new93helloworld.tistory.com/220 계산에 사용된 임시값들을 저장하고있다가 나중에 활용하는것을 말한다. 일단 여기서 공부를 마친다. 아 슈바 집가서 다시 복습해야지.