내용 찾는 코딩 내용 찾는 코딩

공부

• [hackerrank] Ice Cream Parlor python

  공부/알고리즘 2021. 9. 11. 00:06

  처음에 그냥 딱히 생각이 안나서 O(N^2)풀이로 풀었는데 100% 정답이 뜨긴 했지만, 실제 코딩테스트에서는 O(N)시간 복잡도를 요구하는 것 같은 문제라 시간을 줄여 보았다. dictionary를 이용해서 문제를 풀어보았다 (키포인트) 1. 가격을 key값으로, 문제의 indices를 value로 dictionary를 생성하고, for문을 돌려보자. 2. arr의 0번째 인덱스부터 시작해서 for문이 돌면서 dictionary에 m-arr[i] 즉, cost = [1, 4, 5, 3, 2]이 있을때 1 4 5 를 거치면서 3을 만났을때 생성된 1의 key값을 가진 값이 dictionary에 있기때문에 return [priceDic[m-arr[i]], i+1]을 해주면 오름차순으로 정답을 찾을 수 있다..

  Read More
• [hackerrank] Candies python

  공부/알고리즘 2021. 9. 10. 14:24

  1. candyList를 n사람 만큼 1로 초기화 2. for문을 한번 돌려서 arr[i] 1 2 1 1 2 # 1 2 3 4 3 2 1 -> 1 2 3 4 1 1 1 -> 1 2 3 4 3 2 1 def candies(n, arr): # Write your code here..

  Read More
• [hackerrank] Maximum Perimeter Triangle python

  공부/알고리즘 2021. 9. 10. 11:41

  sticks의 원소들 중 삼각형이 되는 3개의 원소들 중 가장 큰 변을가지고, 중복된 가장 큰 변을 가질때 최소길이의 변이 최대인 3개의 변을 return 해주는 문제이다. 1. sticks를 sort해주자. 2. maxIndex가 1보다 클때까지 while문을 돌려서 후보가 될 3변을 구하자. sort를 한뒤 아래와 같이 while문을 돌리면 문제의 조건과 부합하는 세변의 원소들이 answerList에 쌓이게 된다. 3. answerList의 크기가 0이면 return -1, 그렇지 않다면 answer를 return 해주자. def maximumPerimeterTriangle(sticks): # Write your code here sticks.sort() maxIndex = len(sticks) - ..

  Read More
• [hackerrank] Marc's Cakewalk python

  공부/알고리즘 2021. 9. 10. 03:28

  1. calorie reverse sort해주고 관련 수식을 mileSum에 더해주자 def marcsCakewalk(calorie): # Write your code here calorie.sort(reverse=True) mileSum = 0 for index, cal in enumerate(calorie): mileSum += (2**index * cal) return mileSum

  Read More
• [hackerrank] Grid Challenge python

  공부/알고리즘 2021. 9. 10. 02:48

  그냥저냥 풀었던 무난한 문제였다. 1. 우선 grid상의 각 원소를 ascending order로 정렬하여주고 2. grid[0~n-1][0], grid[0~n-1][1] ... 즉 각 원소의 column이 ascending order인지 확인해 주었다. 작성하고 시간복잡도 때문에 fail하지 않을까 생각했는데 아니였지만 조금 아쉽긴 하다. def gridChallenge(grid): # Write your code here for i in range(len(grid)): convertAsc = list(grid[i]) convertAsc.sort() convertStr = ''.join(convertAsc) grid[i] = convertStr for i in range(len(grid[0])): co..

  Read More
• [hackerrank] Minimum Absolute Difference python

  공부/알고리즘 2021. 9. 9. 16:35

  이번에 시험보는 넥슨 코딩테스트를 hackerrank에서 진행한다고 하여서 hackerrank에 올라와 있는 문제를 쭉 풀어보려한다. Greedy 유형에 포함된 이문제는 list안에 있는 원소 중 2개 간의 절대값의 차이의 최소값을 구하는 문제이다. 1. 절대값의 차이가 최소라면 sort했을때 서로 가장 가까운 거리에 있겠구나! (key point) 2. sort를 하면, for문을 돌릴때 arr[i+1] - a[i]값은 당연히 양수이겠구나! 3. 또한 조금 더 시간을 줄이기 위해 arr[i+1] - a[i]가 0이되면 바로 0을 return 해주자. 4. minDif를 초기값을 무한으로 놓고 Dif와 비교해주며 갱신하자. sort할 생각 못했으면 조금 오래 걸렸을 것 같다.... def minimumA..

  Read More
• [python] Codility Lesson 9-3. MaxDoubleSliceSum

  공부/알고리즘 2021. 9. 9. 12:03

  슬라이싱이 이쁘장하게 되지않고 각각 애매하게 슬라이딩 되서 Y값이 빠지는 부분은 어떻게 하지, 각각을 어떻게 따로 구해서 더하나? 한번에 할방법 없나 이런생각 저런생각하다 "구글링 했습니다..." (출처 : https://curt-park.github.io/2018-09-14/algorithm-max-double-slice-sum/) 1. 좌측 slice를 구해주는데, 저번 문제처럼 l_max_slice_sum[i-1] + A[i] 아래와 같이 보면 이해할 수 있지만 아래와 같이 깔끔하게 생각해 내는게 쉽지 않은 것 같다. 1. l_max_slice_sum 과 r_max_slice_sum을 len(A)크기의 리스트로 생성하자. 2. X,Y,Z 중 Y를 i+1로 두고 for문을 돌려서 l_max_slice..

  Read More
• [python] Codility Lesson 9-2. MaxSliceSum

  공부/알고리즘 2021. 9. 9. 02:10

  문제를 연습할 때, 바로 떠오르는 방법 먼저 시도해보고, 시간복잡도를 생각한 코드를 작성하고 있다. 맨 아래에 맨처음 2중 for문을 통해 풀어본 코드 (88%) 바로 아래 시간 복잡도를 고려한 코드를 첨부했다. 이번 문제는 뭔가 이전 문제와 크게 다르지 않은 것 같다. 음수관련 처리해주는데 생각이 복잡해져서 꽤나 애를 먹었다. 1. maxSum을 마이너스 끝판왕으로 설정해주고, sum을 0으로 초기값을 잡자. 2. for문을 돌면서 sum += a 해주자. 3. maxSum을 max(maxSum, sum)을 통해 갱신해주자 4. 여기서 조금 머리가 많이 아팠다 여러 예외 ( ex) 모두 마이너스일때, 섞여있을때, [3,-1,5]와 같은 경우 등.... ) 결국 sum이 음수만 아니면 sum을 갱신해줄 ..

  Read More