관찰과 질문, 그리고 데이터

[Python] Hackerrank. Hackerland Radio Transmitters (Medium)

https://www.hackerrank.com/challenges/hackerland-radio-transmitters/problem?isFullScreen=false Hackerland Radio Transmitters | HackerRankFind the minimum number of radio transmitters needed to cover all the houses in Hackerland!www.hackerrank.com Greedy 알고리즘 문제. 아래 로직을 반복하면 되는 구조.idx 위치에 transmitter를 설치했을 때, 오른쪽으로 얼마나 도달하는지 확인한다.도달할 수 있는 최대지점에 transmitter를 설치하면, 그 위치에서는 오른쪽으로 얼마나 도달하는지 확인한다.

https://www.hackerrank.com/challenges/flatland-space-stations/problem?isFullScreen=false Flatland Space Stations | HackerRankFind the maximum distance an astronaut needs to travel to reach the nearest space station.www.hackerrank.com nearest space station까지의 거리의 최댓값을 구하는 문제. 인접한 두 station의 거리를 2로 나눈 값 중 최댓값을 찾으면 된다.Edge case는 두 개.첫 번째 도시와 첫 번째 station 사이의 거리마지막 도시와 마지막 station사이의 거리

https://www.hackerrank.com/challenges/lilys-homework/problem Lily's Homework | HackerRankHelp George figure out Lily's homeworkwww.hackerrank.com 문제의 핵심은 arr[i] - arr[i-1] 가 절댓값이라는 것.최솟값 기준 정렬 / 최댓값 기준 정렬했을 때 swap이 더 적은 걸 선택해야 한다. 처음에는 단순하게 이중 for문으로, idx별 최솟값 찾아서 swap하는 방식을 썼을 때 timeout이 발생. "idx별 최솟값 찾기" 를 O(1)으로 바꾸려면이미 정렬이 끝난 배열을 만들어둔다: sorted(arr)swap 과정을 기록할 O(1) 자료구조가 필요하다: dict정렬 문제인데 내장..

https://www.hackerrank.com/challenges/climbing-the-leaderboard/problem Climbing the Leaderboard | HackerRank Help Alice track her progress toward the top of the leaderboard! www.hackerrank.com 전체 scoreboard 값이 주어져 있고, alice의 score가 주어지면 해당 score는 전체 scoreboard에서 몇 등인지를 표시하는 문제. 해커랭크에서 이 문제는 'Implementation'으로 분류돼 있다. 처음 봤을 땐 단순히 'alice의 매 score를 scoreboard에서 binary search해서 풀면 되겠다' 생각했는데, time l..

https://www.hackerrank.com/challenges/sherlock-and-valid-string/problem Sherlock and the Valid String | HackerRank Remove some characters from the string such that the new string's characters have the same frequency. www.hackerrank.com 문자열의 개수를 셌을 때, 문자열 한 개만 지웠을 때 모든 문자열의 개수가 동일하면 YES, 아니면 NO를 출력하는 함수. "문자열 한 개만 지웠을 때" YES가 가능하려면, 세 가지 경우가 있다. 1. 문자열 개수 자체가 1개인 경우 2. 가장 많이 등장한 문자열에서 1개를 제거했을 때,..

https://www.hackerrank.com/challenges/big-sorting/problem Big Sorting | HackerRank Sort an array of very long numeric strings. www.hackerrank.com 난해한 문제는 아니었지만, Python sorting의 특징을 하나 알 수 있었던 문제. 해당 문제 forum을 들어가보면 더 자세히 알 수 있다. Python에서 int -> str, str -> int 형변환은 연산량이 비싼 편이다. 특히 이 문제처럼 숫자값이 클 경우 연산량이 매우 비싸게 작용한다. 따라서 일반적으로 생각하는 문제해결방법인 '문자열을 숫자로 변환 -> 대소비교 -> 정렬' 식의 연산은 time limit에 걸린다. 대안으로 k..

https://www.hackerrank.com/challenges/find-the-nearest-clone/problem Find the nearest clone | HackerRank Find the shortest path length between any two nodes with the given condition. www.hackerrank.com constraint 값이 꽤 커 보여서, 2D Array로 그래프를 구성하는 대신 defaultdict를 사용했다. bfs로 그래프를 순회하면서, 시작점의 color와 순회지점의 color가 일치하는 지점에서 순회 횟수를 반환하면 된다.