내가 보는 세상 이야기

Lesson 5-3 - MinAvgTwoSlice 내용 : Find the minimal average of any slice containing at least two elements. 시간 복잡도 : O(n) 정답 코드는 : def solution(A): min_avg_value = (A[0] + A[1])/2.0 # The mininal average min_avg_pos = 0 # The begin position of the first # slice with mininal average for index in xrange(0, len(A)-2): # Try the next 2-element slice if (A[index] + A[index+1]) / 2.0

Lesson 5-2 - PassingCars내용 : Count the number of passing cars on the road. 시간 복잡도 : O(n)정답 코드 :1234567891011121314function solution(A) { // write your code in JavaScript (Node.js 6.4.0) let rt=0; let eastcnt=0; for(i in A) { if(A[i] == 0) { eastcnt ++; } else { rt += eastcnt; } if(rt > 1000000000) { rt = -1; break; } } return rt;Colored by Color Scriptercs 동쪽과 서쪽 짝을 이루어야 되므로 구분해서 계산쉽지 않은 문제이런 방법..

Lesson 5-2 - CountDiv내용 : Compute number of integers divisible by k in range [a..b]. 시간 복잡도 : O(1)정답 코드 : 1234567891011int solution(int A, int B, int K) { double a = A; double b = B; int ret = floor(b/K) - floor((a - 1)/K); return ret; } Colored by Color Scriptercs 출처 : http://ccomsi.tistory.com/56 이번엔 수학 이론을 알아야 가능 했던 문제 인 듯...수포자는 ㅠㅠ 수학 이론은https://namu.wiki/w/%ED%95%A9%EB%8F%99%EC%8B%9D여기에서 확인..

Lesson 4-4 - MaxCounters내용 : Calculate the values of counters after applying all alternating operations: increase counter by 1; set value of all counters to current maximum.문제 설명은 여기를 참고 http://hojak99.tistory.com/316 시간 복잡도 : O(N+M)80% 코드 :function solution(N, A) { // write your code in JavaScript (Node.js 6.4.0) let rt_arr = new Array(N); let max_counter = 0; let now_idx=0; rt_arr.fill(0); for..

Lesson 4-3 - MissingInteger내용 : Find the smallest positive integer that does not occur in a given sequence.시간 복잡도 : O(N)성공한 코드 :function solution(A) { // write your code in JavaScript (Node.js 6.4.0) let tmp_obj = {}; let tmp_arr = new Array(); let rt_val = 1; let all_tot = 0; let ele_tot = 0; for(let i=0;i 0) { tmp_obj[A[i]] = 0; } } tmp_arr = Object.keys(tmp_obj); if(Object.keys(tmp_arr).lengt..

Lesson 4-2 - FrogRiverOne내용 : Find the earliest time when a frog can jump to the other side of a river. 시간 복잡도 : O(N)성공한 코드 : function solution(X, A) { // write your code in JavaScript (Node.js 6.4.0) let rt_val = -1; let tmp_arr = {}; let jump_cnt = 0; for(let i=0;i

Lesson 4-1 - PermCheck내용 : Check whether array A is a permutation.시간 복잡도 : O(N)성공한 코드function solution(A) { // write your code in JavaScript (Node.js 6.4.0) let A_len = A.length; let total = A_len*(A_len+1)/2; let rt_val = 0; let tmp_arr = {}; for(i in A) { rt_val += A[i]; tmp_arr[(A[i]-1).toString()] = A[i]; /* for [1,4,1] antisum test case */ } if(rt_val==total && Object.keys(tmp_arr).length =..

Lesson 3-3 - TapeEquilibrium내용 : Minimize the value |(A[0] + ... + A[P-1]) - (A[P] + ... + A[N-1])|시간 복잡도 : O(N)성공한 코드function solution(A) { // write your code in JavaScript (Node.js 6.4.0) let tot = 0; let rt_val = 100001; let tmp_tot = 0; for(i = 0;i

Lesson 3-2 - PermMissingElem내용 :Find the missing element in a given permutation시간 복잡도 : O(N) 성공 했지만 민망해서 공개 안하는 코드 : function isZero(element) { return element == 1; } function solution(A) { // write your code in JavaScript (Node.js 6.4.0) let rt_arr=new Array(A.length+1); rt_arr.fill(1); for(i in A) { rt_arr[A[i]-1]=0; } //console.log(rt_arr.findIndex(isZero)+1); return rt_arr.findIndex(isZero)+..

Lesson 3-1 - FrogJmp내용 :Count minimal number of jumps from position X to Y.시간 복잡도 : O(1) 성공한 코드 :function solution(X, Y, D) { // write your code in JavaScript (Node.js 6.4.0) let rt_val = (Y-X)/D; return Math.ceil(rt_val); } 결론 : 요것도 좀 쉬운듯쉬워도 댓글 보면서 다른 방법에 대한 고민 필요댓글 살펴보다 든 생각:과연 잘 짠 소스랑 무엇일까?rt_val = (Y-X)/D; return Math.ceil(rt_val);return (Y-X) % D > 0 ? (Y-X)/D+1 : (Y-X)/D;Y = JD + X, JD = -..