The HackerRank Interview Preparation Kit

• 문제
• 코드

sorting - Fraudulent Activity Notifications

파이썬 성공
자바 실패 (정수 범위의 문제인지 실패한다)😥

배운 것, 푼 것

처음에 매번 sort()를 해줬다가 시간 초과가 났다.
다른 분들 글을 보고 이진탐색으로 해결한 방법과 Countring Sort를 이용한 방식이 있다는 것을 알게 되었고 두가지 방법을 이용해서 풀어봤다

계수정렬에 대해 아래에 새롭게 배운 내용을 정리했으나 막상 문제를 풀 때에는 누적 인덱스에 대한 배열을 새로 만들지 않고 기존 동빈북에서 배웠던 방식을 활용했다.

계수정렬

계수 정렬을 공부하다가 https://www.youtube.com/watch?v=OKd534EWcdk 이것을 보고 헷갈렸다. 기존에 내가 알던 계수정렬과 달랐기 때문

• 동빈북에서 계수정렬을 학습했을 때에는 단순히 특정 범위 (ex. 시험 점수 1~100)위를 값으로 갖는 값들을 정렬할 때 해당 점수가 몇 번 등장했는지에 대한 별도의 리스트를 만들어 해당 리스트 값대로 순차적으로 나열한다고 알고 있었다.
• 저 유튜브를 보면서는 몇번 등장했는지 만들어둔 배열의 데이터를 누적합으로 다시 새로운 배열을 만들면 특정 값이 몇 번째 인덱스에 들어갈지 알 수 있다는 것이다.
• 이번에 새로 학습한 것은 아래와 같다.
  • 1) 그렇게 각 값에 대해 몇 번 등장했는지로 배열 값으로 저장하고
  • 2) 그 값을 누적해서 다시 저장한다. 예를들어 0~1의 값을 갖는 데이터라고 했을 때 0이 1번 등장했다면 arr[0] = 1, 이고 1이 2번 등장했다면 arr[1] = 1 + 2 = 3 이다
  • 3) 이렇게 누적된 배열의 각 값이 나타내는 의미는 이 데이터를 정렬할 때 해당 값이 몇 번째 인덱스에 들어갈 것인지다.
    • arr[0] = 1 이므로 '0'이라는 값은 새롭게 정렬 때 배열의 첫번째 인덱스에 들어간다. sortedArray[0] = 0
    • arr[1] = 3 이므로 세번째 인덱스에 들어가게 된다. sortedArray[2] = 1 (세번째 인덱스는 2)
    • 그리고나서 다음 1이 들어올 인덱스를 위해 arr[1] = 2로 바꿔준다
    • 실제로 다음 1이 들어올 때는 sortedArray[1] = 1이 된다. sortedArray = {0, 1, 1}
  • 결국 누적된 배열에서 값이 의미하는 것은(arr 배열에서 각 값들) 해당 데이터가 들어갈 수 있는 가장 마지막 인덱스가 된다.

enumerate()

https://docs.python.org/3/library/functions.html#enumerate

• 파이썬 enumerate
• enumerate(순회할자료, start) 에서 start는 해당 처음 인덱스가 몇번부터 시작할지를 나타낸다.

number = [2,3,4,5]
for i, v in enumerate(number, 2):
    print(i, v)

결과

2 2
3 3
4 4
5 5

bisect.insort(순회할자료, 넣을 값)

해당 자료에 알맞은 위치에 값을 넣어준다
https://docs.python.org/3/library/bisect.html