[Leetcode] #506 Relative Ranks

문제 : 

- 문제는 생각보다 간단하다. 정렬되지 않은(또는 정렬된) 리스트가 주어지고, 각 요소의 값을 비교하여 큰 순서대로 1등부터 3등은 각각 Gold, Silver, Bronze를 주고, 그 이후의 숫자들에 대해선 4, 5, 6... 과 같이 순서대로 순위를 매겨준다. 단, 원래 주어진 배열의 순서에 맞게 순위를 매겨야 한다. 

 

다시말해, 두번째 예시처럼 주어진 score가 [10, 3, 8, 9, 4]라면, 순위는 현재 요소에 맞게 매핑되어야 한다. 아래는 내가 제출한 코드이다.

class Solution:
    def findRelativeRanks(self, score: List[int]) -> List[str]:
        size = len(score)
        result = [0] * size
        map = {}
        rank = 4
        for i in range(len(score)):
            map[score[i]] = i

        sortedList = sorted(score, reverse=True)

        for i in range(len(score)):
            if i == 0:
                result[map.get(sortedList[i])] = "Gold Medal"
            elif i == 1:
                result[map.get(sortedList[i])] = "Silver Medal"
            elif i == 2:
                result[map.get(sortedList[i])] = "Bronze Medal"
            else:
                result[map.get(sortedList[i])] = str(rank)
                rank += 1
        return result

• 처음에 문제를 겪던 부분이 있었다. 나는 맨 처음에 빈 결과배열을 선언해주고(result = []과 같이), result.insert(idx, obj)를 하여 인덱스에 맞게 결괏값을 넣어주려고 했으나 내가 잘못 알고있던 사실이 있었다. 파이썬의 리스트는 처음에 크기가 정해져있지 않으면 내가 insert를 이용해 result.insert(100, 'a')를 하던, result.insert(1000, 'a')를 하던 리스트의 마지막 자리에 값이 추가되는 것이였다. 나는 빈 리스트에 insert를 하면 그 자리를 찾아가 값을 넣는줄 알았다. 예를들어, 빈 배열에 result.insert(2, 'a')를 하면, 
  result = [null, null, 'a'] 이렇게 알아서 위치를 찾는줄 알았다. 하지만 아니였다! 그래서 빈 배열이 아니라, 주어진 배열과 같은 사이즈의 배열을 선언해주고, 모든 요소를 0으로 초기화 해 주고 insert를 해줘야지 했다. 이렇게 되면 이미 배열은 5칸이고, insert를 할때는 알맞은 인덱스를 찾을 수 있으므로 괜찮을 줄 알았다. 하지만, 파이썬의 insert는 단순히 값을 삽입하는것이 아니라 값을 그 자리에 삽입함과 동시에 원래 있던 값을 뒤로 밀어내는 메서드였다. 예를들어, result = [0,0,0,0,0]가 있고, 여기에 result.insert(0, 'a')를 하면 result = ['a',0,0,0,0] 가 되는것이 아니라 result = ['a',0,0,0,0,0] 이렇게 되는 것이였다.
  
  
• 그래서 단순히 배열안의 값을 "swap"해주기 위해 결과 배열을 주어진 score의 길이만큼 선언하고, 절대 쓰이지 않을 '0'으로 초기화 하였다.
• 다음으로, 이 문제를 풀기 위해 내가 생각한 첫번째 자료구조는 해시맵이였다. 하지만, 문제의 Topic을 봤을땐 해시테이블이 없길래 뭐지 했다. 하지만 해시테이블 말고는 다른 자료구조는 생각해내지 못했고, 해시 테이블이 가장 효율적이고 makes sense하기 때문에 해시맵을 사용하였다.
• 해시맵에는 처음 주어진 score배열안의 요소의 값과 인덱스를 키-값으로 매핑해주었다. 이렇게 되면 해시맵(딕셔너리)안에는 이러한 식으로 매핑이 되어있을것이다. map = {10 : 0, 3: 1, 8: 2, 9: 3, 4: 4}. 이미 원래 인덱스의 값은 저장했으므로, 이젠 순서를 매기기 위해 배열을 정렬 해 준다 앞에서부터 편하게 순위를 매기기 위해 reverse = True를 이용해 배열을 내림차순으로 정렬해주었다.
• 내림차순으로 정렬하게 되면, 당연하게도 맨 처음 인덱스 0부터 Gold, Silver, Bronze, 4, 5, 6... 이렇게 될 것이다.(내림차순 정렬을 해준 이유)
• 다음은 for문을 이용해 결괏값을 결과 배열에 넣어준다. 사실 for문이 돌때마다 i는 자동으로 증가하기 때문에 i == 0인지 체크가 무의미 할 수도 있겠지만, 여기서는 gold, silver, bronze를 구별 해 주기 위해 인덱스를 체크 해 주었다.
• 여기서 이제 딕셔너리를 쓰는 이유가 나온다. 예시를 보면 배열을 내림차순으로 정렬하면 [10, 9, 8, 4, 3]이다. 하지만 우리는 이 순서대로 순위를 매기면 안되고, 처음에 주어진 score의 인덱스를 지켜야 한다. 이 score의 인덱스를 키-값 쌍으로 묶은것이 해시맵이다. 
• 단순히 그 자리에 "Gold Medal"을 넣으면 안되고, 현재 요소의 value값을 딕셔너리에서 찾아(원래 주어진 배열의 인덱스) insert가 아닌 "교체"를 해 주었다. 그리고 Bronze이후의 등수는 숫자이고, 이 숫자들은 단순히 하나씩 더하면서 넣어주면 됐다. 하지만, 이 문제에서는 리스트의 모든 값의 type이 string이기때문에 str()을 이용해 형 변환을 해 주었다. 

문제는 단순하지만 내가 몰랐던 부분이 있었어서 좀 오래 걸렸던 문제이다. 사실 1학년때 배웠지만, 너무 오랜시간이 지나 다 까먹었다...

다시 한번 기억할 부분은...

 

- 파이썬의 insert는 그 자리에 값을 삽입하고 나머지 값들을 뒤로 밀어낸다. 또한, 빈 리스트에 insert를 하면 그 자리를 찾아 insert를 하는게 아니라 리스트의 마지막 자리에 값을 추가한다.

- 형 변환

- 파이썬은 자바와 다르게 배열을 초기화할때 명시적으로 크기를 선언해 줄 수 없다. 자바는 int[] arr = new int[5]; 와 같이 5칸짜리 배열을 선언 해 줄 수 있으나, 파이썬에서 5칸짜리 null리스트를 초기화 하려면 arr = [None] * 5 처럼, 5번을 넣어주어야 한다.!

 

아래는 내가 받은 report이다. 런타임과 메모리가 상당히 괜찮게 나왔다!