Jay's Develop Note

문제 : 

두개의 리스트가 주어지고, 두개의 리스트 안의 같은 값의 인덱스에 대하여, 두 인덱스를 더한 값이 최소가 되는 값을 리스트에 넣어서 반환하는게 문제이다.

일단 보자 마자 해시 테이블이 생각났다. 처음에는 brute force로 이중 for문을 이용해 요소 하나하나씩 돌며 인덱스를 비교하려고 했으나, 리스트에서 원하는 값을 찾으려고 할때마다 검색비용 O(n)이 싫어 해시 테이블을 사용했다. 이 문제는 빈번하게 검색이 자주 일어나기 때문이다(다른 리스트에 현재 리스트에서 검색중인 값이 있나 확인).

아래는 내가 제출해 통과한 코드이다.

class Solution:
    def findRestaurant(self, list1, list2):
        l1 = {}
        result = []
        min_sum = float('inf')

        for idx, item in enumerate(list1):
            l1[item] = idx

        for idx, item in enumerate(list2):
            if item in l1:
                current_sum = l1[item] + idx
                if current_sum < min_sum:
                    result = [item]
                    min_sum = current_sum
                elif current_sum == min_sum:
                    result.append(item)
        return result

- 일단, 첫번째 리스트의 값들을 요소값 : 인덱스 쌍으로 매핑 시켜주었다. 두번째 리스트도 해시 테이블에 값을 매핑 시키려고 했으나 두번째 리스트는 굳이 매핑 할 필요가 없었다.

- min_sum이라는 변수는 비교를 위해 추가한 변수인데, float('inf')를 사용해 최댓값을 일단 넣어 주었다.

- 두번째 리스트를 하나씩 차례대로 순회하며 해시테이블에 그 값이 존재하는지 확인한다.

- 만약 존재한다면, 두 값의 인덱스를 더해 current_sum 안에 저장 해 준다.

- 그 다음, 방금 저장한 current_sum이라는 값이 min_sum보다 작은지 확인한다. 작다면, 결과 배열에 result = [item]을 하여 새로운 최솟값을 찾았을 때 결과 리스트를 초기화하고 새로운 요소를 추가한다. 즉, 현재의 최소 인덱스 합보다 더 작은 합을 찾았을 때 이전의 결과를 모두 지우고 현재의 요소로 새롭게 리스트를 초기화 한다.

하지만, example 3을 보면, 두 요소의 합이 1인 pair들이 2개가 있으므로[current_sum == min_sum](이 경우엔 두 요소를 모두 결과 배열에 추가 해준다.) 이때는 결과 배열 초기화가 아니라 .append를 이용해 배열에 끝에다가 더해준다.

아래는 내가 받은 Runtime, Memory report이다.

• 새롭게 알게된 내용 & 기억할점 : 
  • `enumerate()` 함수는 반복문을 사용할 때 인덱스와 해당 인덱스의 요소를 동시에 얻을 수 있는 유용한 함수이다. 이를 사용하면 반복문 내에서 현재 요소가 몇 번째 요소인지 알 수 있으며, 코드의 가독성을 높이는 데 도움이 된다.
    
    list1 = ["Shogun", "Piatti", "Tapioca Express", "Burger King", "KFC"]
    
    for idx, item in enumerate(list1):
        print(f"Index: {idx}, Item: {item}")
    
    위 코드는 다음과 같이 출력된다:
    Index: 0, Item: Shogun
    Index: 1, Item: Piatti
    Index: 2, Item: Tapioca Express
    Index: 3, Item: Burger King
    Index: 4, Item: KFC
    
    사용 이유
    `enumerate()` 함수는 인덱스와 요소를 동시에 다룰 수 있게 해 주므로, 다음과 같은 상황에서 유용하게 사용된다:
    - 요소의 위치(인덱스)가 필요한 경우
    - 인덱스를 사용하여 특정 조건을 체크하거나 조작할 때
    - 코드의 가독성을 높이고 반복문 내에서 명확하게 인덱스를 참조하고자 할 때
    
    
  • 문제를 다시 잘 생각하자. 내가 몇분동안 막혔던게 뭐였냐면, 맨 처음에는 조건문이 if current_sum < min_sum이면 곧바로 결과 배열에 값을 더했다. 하지만 생각해보면 이건 완전히 틀린 로직이다. 이렇게 되면, 처음 비교되는 값은 그 값이 최솟값이던 아니던무조건 결과 배열에 저장이 될 것이다. 예를들어, 첫번째 비교하는 대상의 두 인덱스의 합이 4이고, 두번째 비교하는 대상의 두 인덱스의 합이 1인 경우에도 결과 배열에는 [4, 1] 이렇게 저장이 될 것이다. 하지만, 이 문제의 목적은 "최솟값"을 찾는 것이다. 즉, 우리는 가장 작은 값만 찾으면 되므로, 배열에 현재 값을 임시로 저장해 두었다가 나중에 더 작은 값이 나오면 result = [item]으로 리스트의 내용을 교체해주면 된다. 
    
  • result = item은 적절하지 않다. 이 문장은 result를 리스트로 초기화하는 것이 아니라 item 값을 그대로 할당하는 것이다. result는 리스트로 유지되어야 하며, 이를 통해 여러 요소를 추가할 수 있어야 한다. 따라서 result = [item]이 맞는 표현이다.
    
    다시 설명하자면, result = [item]은 result를 초기화하고 item을 새로운 리스트의 유일한 요소로 추가하는 역할을 한다. 반면에 result = item은 result를 리스트가 아닌 단일 값으로 설정하여 이후의 추가 작업을 불가능하게 만든다.
    
    

문제 : 

- 문제는 생각보다 간단하다. 정렬되지 않은(또는 정렬된) 리스트가 주어지고, 각 요소의 값을 비교하여 큰 순서대로 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이다. 런타임과 메모리가 상당히 괜찮게 나왔다!

문제 :

처음 보자마자 고민했다. 리스트를 순회하며 검사를 할것인가 아니면 딕셔너리를 이용할것인가...

생각해보니 그냥 리스트를 순회하기엔 너무 값이 비쌌다. 리스트의 검색은 O(n)이 소요되기 때문에 비싸다. 

그리고 이 문제를 보면, 키보드의 첫번째, 두번째, 그리고 세번째로 나뉘어있는데, 보자마자 해시테이블(파이썬의 딕셔너리) 라는 생각이 들었다. 다시한번 복습하지만, 해시테이블의 검색은 O(1)이 소요되어 매우 빠르다.

아래는 내가 제출해 통과한 코드이다.

class Solution:
    def findWords(self, words: List[str]) -> List[str]:
        f = "qwertyuiop"
        s = "asdfghjkl"
        t = "zxcvbnm"

        result = []
        rows = {}
        isSame = False

        for c in f:
            rows[c] = 1
        for c in s:
            rows[c] = 2
        for c in t:
            rows[c] = 3

        for i in words:
            lowerCase = i.lower()
            all_match = True
            for j in range(len(lowerCase) - 1):
                if(rows.get(lowerCase[j]) != rows.get(lowerCase[j+1])):
                    all_match = False
                    break
            if all_match:
                result.append(i)
            
        return result

먼저, 딕셔너리에 키보드의 줄 위치를 기반으로 값들을 넣어준다. 이제 키보드의 모든 문자는 각각의 줄 번호에 맞게 딕셔너리에 잘 삽입 되었다. 그 다음, for문을 사용하여 주어진 words에서 단어를 하나씩 꺼내어 비교한다. 하지만, 방금 내가 만든 딕셔너리에는 소문자값만 있으므로, 파이썬의 소문자 변환 메서드인 .lower()을 사용해 문자열을 소문자로 변경해주고 일일히 하나씩 비교해 키값이 다르다면(즉, 키보드에서 같은 줄에 있지 않다면) break를 이용해 바로 다음 문자로 넘어가고, 만약 문자열을 끝까지 검사했을때 문자열의 문자들이 모두 키보드의 같은 줄에 있다면 결과 배열에 문자열을 더해주고 마지막에 return 해 준다.

하지만 여기서 이중 for문을 쓰면서 불길한 예감이 들었다. 이중 for문은 O(n^2)의 시간 복잡도를 가지기 때문이다. 역시나 런타임은 매우 낮게 나왔다. 

이 코드의 런타임이 긴 이유와 성능을 향상시킬 수 있는 방안은 다음과 같다:

 이유

1. 반복적인 딕셔너리 접근:
   각 단어의 문자를 검사할 때, 매번 `rows.get()` 메서드를 호출하여 딕셔너리에서 값을 가져온다. 이 작업은 각 단어의 길이만큼 반복된다.

2. 이중 반복문:
   외부 반복문은 `words` 리스트의 모든 단어를 순회하고, 내부 반복문은 각 단어의 길이만큼 순회한다. 따라서 전체 시간 복잡도는 최악의 경우 (O(n * m))이다. 여기서 (n)은 `words` 리스트의 길이, (m)은 단어의 평균 길이이다.

성능 향상 방안

1. 집합을 사용하여 더 빠른 검색:
   딕셔너리 대신 집합을 사용하여 각 행에 있는 문자들을 저장하면 더 빠른 검색이 가능하다. 집합은 평균적으로 (O(1)) 시간 복잡도로 검색을 수행할 수 있다.

2. 한 번의 순회로 검사:
   각 단어의 첫 번째 문자의 행을 기준으로 설정하고, 나머지 문자들이 같은 행에 있는지 확인하는 방식으로 변경하면 내부 반복문을 최적화할 수 있다.

class Solution:
    def findWords(self, words: List[str]) -> List[str]:
        # 각 행에 있는 문자들을 집합으로 저장
        row1 = set("qwertyuiop")
        row2 = set("asdfghjkl")
        row3 = set("zxcvbnm")

        result = []

        for word in words:
            lowerCase = word.lower()
            if lowerCase[0] in row1:
                target_row = row1
            elif lowerCase[0] in row2:
                target_row = row2
            else:
                target_row = row3

            all_match = all(char in target_row for char in lowerCase)

            if all_match:
                result.append(word)

        return result

1. 집합 사용:
   각 행에 있는 문자들을 집합으로 저장하여 검색 속도를 향상시켰다.

2. 한 번의 순회로 검사:
   각 단어의 첫 번째 문자를 기준으로 해당하는 행을 설정하고, 나머지 문자들이 같은 행에 있는지 확인한다. `all()` 함수를 사용하여 단어의 모든 문자가 동일한 행에 있는지 확인한다.

이 개선된 코드의 시간 복잡도는 (O(n * m))에서 (O(n * k))로 줄어든다. 여기서 n은 `words` 리스트의 길이, m은 단어의 평균 길이, k는 집합에서의 검색 시간(평균적으로 (O(1))이다. 따라서 이 방법은 성능을 크게 향상시킬 수 있다.

새로 알게된 내용 : 

all() 함수는 파이썬 내장 함수로, 주어진 반복 가능한(iterable) 객체의 모든 요소가 참(True)인지 검사한다. 만약 모든 요소가 참이면 True를 반환하고, 하나라도 거짓(False)이면 False를 반환한다. 빈 반복 가능한 객체에 대해 호출하면 True를 반환한다.

all() 함수의 일반적인 사용 예는 다음과 같다:
리스트의 모든 요소가 참인지 검사:

numbers = [1, 2, 3, 4, 5]
result = all(numbers)
print(result)  # 출력: True (모든 요소가 참)

리스트의 일부 요소가 거짓인 경우:

numbers = [0, 1, 2, 3, 4]
result = all(numbers)
print(result)  # 출력: False (0이 거짓 값이므로)

조건을 만족하는지 검사:
리스트의 모든 요소가 양수인지 확인하는 예제:

numbers = [1, 2, 3, 4, 5]
result = all(n > 0 for n in numbers)
print(result)  # 출력: True (모든 요소가 양수이므로)

문자열이 모두 소문자인지 확인:

words = ["hello", "world", "python"]
result = all(word.islower() for word in words)
print(result)  # 출력: True (모든 단어가 소문자이므로)

- 그리고, 마지막에서 살짝 헷갈렸던 부분이 있다.

for i in words:
            lowerCase = i.lower()
            all_match = True
            for j in range(len(lowerCase) - 1):
                if(rows.get(lowerCase[j]) != rows.get(lowerCase[j+1])):
                    all_match = False
                    break
            if all_match:
                result.append(i)
            
        return result

이 부분을 보면 words문자열에서 문자열을 하나씩 뽑아내 다시 for문을 순회하며 문자를 하나하나씩 가져와 j + 1과같이 다음 문자와 비교하는 구간인데, 위의 조건문처럼 만약 다음 문자의 딕셔너리값이 같지 않다면 break를 통해 빠져나오고, 만약 문자열을 끝까지 검사했는데도 불구하고 문자열 모두가 같은 딕셔너리의 값을 갖고있으면 result에 append를 해야했다. 하지만 "만약 문자열을 끝까지 검사했는데도 불구하고 문자열 모두가 같은 딕셔너리의 값을 갖고있으면" 이 부분을 어떻게 코드로 써낼지 살짝 헷갈렸다. 이럴때는 위처럼 boolean플래그를 사용하면 된다. 물론 if문에 조건(끝까지 검사 했는지)을 추가하면 되지만, if문으로 비교하는것은 비싸다. 그래서 앞으로 이럴땐 boolean 플래그를 쓰도록 하자. 

문제 : 

예시 :

문제는 보기보다 간단하다. 두개의 배열이 파라미터로 주어지고, nums1을 순회하며 nums1[i]보다 큰 값이 nums2[j]의 "오른쪽" 에 있는지 확인하고, 있다면, 결과 리스트에 값을 추가하고, 없다면 -1을 추가한다. 

아래는 내가 제출해 통과한 코드이다.

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        ans =[]
        for i in range(len(nums1)):
            idx = nums2.index(nums1[i])
            found = False
            for j in range(idx + 1, len(nums2)):
                if(nums1[i] < nums2[j]):
                    ans.append(nums2[j])
                    found = True
                    break
            if not found:
                ans.append(-1)
        return ans

- 먼저, 결과값들을 담을 배열 ans를 선언한다.

- 우리의 목적은 nums1에 있는 값들보다 큰 값을 찾아야 하므로, nums1은 무조건 처음부터 끝까지 순회해야 한다.

- 이 문제는 정렬을 할 수도없고, nums1[i]보다 큰 값을 찾기 위해 배열의 처음부터 검색 할 수 없었다. 문제의 조건을 다시 읽어보면 왜 그런지 알 것이다.

- 그래서 idx라는 변수를 선언해 nums1[i]는 nums[j]의 몇번째 인덱스에 있는지 저장한다. 

- 그 인덱스를 찾으면, 그 인덱스 이전의 값은 nums[i]보다 크던 말던 검사 할 필요가 없다. 또한, 우리는 nums2배열의 특정 값의 오른쪽에서만 값이 큰지 아닌지만 확인하면 되므로, 불필요한 검사 1회를 줄이기 위해 idx + 1을 해 주었다.

- 조건을 검사하고, 조건에 부합하면 .append를 이용해 결과 리스트에 값을 담아준다. 그리고 그 다음 요소들은 더 큰 값이 있던 말던 우리는 더 큰 값 하나만 찾으면 되므로 break를 통해 for문을 빠져 나온다.

-마지막으로, 위에서 선언한 found라는 변수를 확인해주고, 만약 배열의 끝까지 도달하더라도 찾지 못했다면 -1을 더해준다.

아래는 내가 받은 report이다.

현재 코드의 시간 복잡도는 nums1의 각 요소에 대해 nums2를 반복해서 검색하기 때문에 O(n * m)이다. 여기서 n은 nums1의 길이, m은 nums2의 길이이다.

여기서 난 어떠한 자료구조도 사용하지 않고 brute force를 사용해 풀었지만, 이 문제는 stack을 활용해도 쉽게 풀릴 문제였다. 스택을 사용한 방법의 시간 복잡도는 O(n + m)이다.

다음은 solution에서 가져온 최적화된 코드이다.

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        next_greater = {}
        stack = []
        
        # Iterate through nums2 to find the next greater elements
        for num in nums2:
            while stack and stack[-1] < num:
                next_greater[stack.pop()] = num
            stack.append(num)
        
        # Use the next_greater dictionary to build the result for nums1
        ans = [next_greater.get(num, -1) for num in nums1]
        
        return ans

- nums2를 순회하며 스택을 사용해 각 요소의 다음 큰 요소를 찾는다.

- while stack은 stack에 요소가 남아있는동안 실행된다. 

- stack[-1] < num은 stack의 맨 위에 있는 요소가 num보다 작을동안 실행된다.
-스택의 상단에 있는 요소가 현재 요소보다 작으면, 스택에서 제거하고 그 요소의 다음 큰 요소로 현재 요소를 저장한다.
-nums2를 다 순회한 후, next_greater 딕셔너리에 각 요소의 다음 큰 요소가 저장된다.
-nums1의 각 요소에 대해 next_greater 딕셔너리에서 값을 찾아 결과 리스트를 만든다.

현재 코드의 시간 복잡도가 비효율적인 이유와 개선된 코드가 더 효율적인 이유는 다음과 같다:

현재 코드의 시간 복잡도
현재 코드는 `nums1`의 각 요소에 대해 `nums2`에서 해당 요소를 찾고, 그 다음에 다음 큰 요소를 찾기 위해 `nums2`의 나머지 부분을 탐색한다. 구체적으로는:

1. `nums1`의 각 요소에 대해 `nums2.index(nums1[i])`를 호출한다. 이 연산은 최악의 경우 O(m) 시간이 걸린다.
2. 그 다음, `nums2`의 나머지 요소를 탐색하여 다음 큰 요소를 찾는다. 이 또한 최악의 경우 O(m) 시간이 걸린다.

따라서 전체 시간 복잡도는 O(n * m)이다. 여기서 `n`은 `nums1`의 길이, `m`은 `nums2`의 길이이다.

최적화된 코드의 시간 복잡도
최적화된 코드는 스택을 사용하여 다음 큰 요소를 찾는다. 이 방법은 각 요소를 한 번씩만 처리하므로 시간 복잡도가 개선된다:

1. `nums2`를 한 번 순회하며 스택을 사용하여 다음 큰 요소를 찾는다. 각 요소는 스택에 한 번 추가되고, 한 번 제거된다. 이 과정은 O(m) 시간이 걸린다.
2. `nums1`의 각 요소에 대해 `next_greater` 딕셔너리에서 값을 조회한다. 딕셔너리 조회는 평균적으로 O(1) 시간이 걸리므로, 이 과정은 O(n) 시간이 걸린다.

따라서 전체 시간 복잡도는 O(m + n)이다.

왜 최적화된 코드가 더 효율적인가?
최적화된 코드는 각 요소를 한 번씩만 처리하고, 다음 큰 요소를 찾기 위해 스택을 사용한다. 이 방법은 요소를 중복해서 탐색하지 않기 때문에 시간 복잡도가 개선된다. `nums1`과 `nums2`의 길이가 클수록 이 차이는 더욱 두드러진다. 

문제 :

예시:

오름차순으로 정렬된 리스트 timeSeries가 주어지고, timeSeries[i]는 티모가 애쉬를 공격하는 당시의 시간이다. 또 다른 파라미터로 주어진 duration은 티모의 독 공격이 지속되는 시간이다. 예를들어, 티모가 1초에 애쉬를 공격했을때 duration이 3초라면, 애쉬는 1 2 3 초의 기간동안 독 공격을 받게 된다. 하지만, 독 공격의 duration이 끝나기 전에 티모가 새로운 공격을 하면, 독 공격의 duration은 초기화 된다.

처음 든 생각 :  사실 어떠한 자료구조를 이용해야겠다는 생각은 들지 않았다. 일단 이 문제는 배열의 요소들로 숫자 장난을 치는 문제이고, 자료구조나 알고리즘을 떠올리기 보단 단순히 수학 + 기본적인 코드정도만 알면 쉽게 풀고 넘어갈 수 있는 문제였다.

아래는 내가 제출해 통과한 코드이다.

class Solution:
    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:

        time = 0

        for i in range(len(timeSeries) - 1):
            if timeSeries[i] + duration - 1 < timeSeries[i + 1]:
                time += duration
            else:
                time += timeSeries[i + 1] - timeSeries[i]

        return time + duration

• 먼저, 결괏값(최종 독에 공격받은 시간)을 담을 변수 time을 선언해 주고, 0으로 초기화 한다.
• for 반복문을 사용한다. 
  • 여기서 range(len(timeSeries) - 1))을 사용한 이유는 다음과 같다.
    - 우리가 이 문제에서 비교해야 할 대상은 딱 두개다. 공격을 가한 '현재 시간(timeSeries[i])' + 'duration'이 '다음에 공격할 시간(timeSeries[i + 1])' 보다 짧은지 긴지만 비교하면 된다.
    - 하지만, 생각해보면 마지막 공격은 어떠한 조건에도 제약받지 않고 duration만큼의 공격을 한다. 왜냐하면 다음에 비교할 대상이 없기 때문! 
    - 하지만 마지막 공격 이전의 공격은 마지막 공격 시간과 조건 비교를 해줘야 하기 때문에 len - 1을 하였다.
• 첫번째 조건문은 현재 시간에 공격을 하고, duration안에 새로운 공격을 하는지 안 하는지 확인하기 위한 조건문이다. 만약, 이 조건문이 True라면, 맨 처음 초기화한 time변수에 duration만큼의 공격을 한 것이므로 time += duration을 해 준다.
• 그렇지 않다면, duration을 더해주는 대신(duration동안 새로운 공격을 하면 이미 돌고있던 duration은 무의미해짐), 다음 시간에서 현재 시간을 뺀 시간만 더해준다. 
  - 예를들어, timeSeries = [1,2,3], duration = [5]라고 가정해보자. 1초에 공격을 가해 5초간 지속된다면, (1, 2, 3, 4, 5)초까지 지속이 될 것이다. 이땐 간단히 time에다가 방금 지난 5초의 시간을 더해주면 되지만, 이 case에선 다음 공격이 바로 다음 2초에 가해지므로, duration은 초기화 되지만, 1초에 공격을 가한 시간(1.00초 ~ 2.00초)까지의 시간에는 공격이 가해졌으므로 단순히 다음 값에서 현재 값을 뺀 값을 시간에 더해준다
• 마지막으로 위에서 언급 했듯, 마지막 공격은 어떠한 제약도 받지 않으므로, 하지만 우리의 for문은 len - 1, 즉, 마지막 요소는 검사 자체를 안 했으므로 마지막 return문에 duration까지 합해 리턴 해 준다.

아래는 내가 받은 런타임 report이다.

엄청 간단한 문제이다. 2개의 배열이 파라미터로 주어지고, 두 배열에서 같은 값을 찾는것이다. 단, 같은 값들을 담은 리스트는 unique해야하며, 즉, 위의 예시처럼 [1,2,2,1]과 [2,2]의 겹치는 부분은 2개이지만(2,2), 결괏값은 [2]여야 한다.

엄청 간단한 문제이다. 뭔가 나도 문제를 보고 brute force가 생각나기 보단, "중복을 허용하지 않는다" 라는점에서 집합(Set)와 해시테이블을 생각했다. 

 - 집합은 중복을 허용하지 않으니, 먼저 리스트를 순회하며 빈 집합에 요소들을 차례로 넣고, 그 다음 두 집합의 교집합을 찾아내면 되지 않을까 생각했다. 

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        
        set1 = set()
        set2 = set()

        for i in nums1 :
            set1.add(i)
        
        for j in nums2 :
            set2.add(j)

        return set1.intersection(set2)

1. set()를 이용하여 빈 집합을 각각 선언해준다.

2. 첫번째 인자로 주어진 nums1을 순회하며 집합에 넣어준다. 위의 예시에 경우엔 set1 = {1,2} 가 담길 것이다(중복 허용X).

3. 두번째 인자로 주어진 nums2를 순회하며 집합에 넣어준다. 위의 예시에 경우엔 set2 = {2}가 담길 것이다.

4. 파이썬의 집합 함수중, .intersection()을 활용해 교집합을 찾아낸다. 

이렇게 간단한 코드이지만, 궁금증이 생겼다. 위 코드의 런타임은 아래와 같다.

- 어떻게 더 런타임을 향상시킬 수 있을까?

제일 빠른 런타임을 가진 다른 사람의 솔루션은 아래와 같다.

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        set1=set(nums1)
        set2=set(nums2)
        inter=set1.intersection(set2)
        return list(inter)

위의 솔루션이 나의 소스코드보다 런타임이 빠른 이유는 다음과 같다.

• set(nums1)와 set(nums2)는 각각의 리스트를 집합으로 변환한다. 이 변환은 한 줄의 코드로 이루어지며, 효율적으로 리스트를 순회하며 집합을 만든다.
  
  • 궁금했던 점 : 근데 set()함수가 리스트를 순회하며 집합을 만드는것이라면, 내가 for문을 사용한것과 같은데 도대체 무슨 차이이지? 어차피 O(n)의 시간이 걸릴텐데...
  • GPT 답변 : 
   

이렇단다! 다음에 또 다시 파이썬의 집합을 써야 할때가 온다면 굳이 반복문을 통해 집합을 업데이트 하는 대신 내장함수를 사용할것!

문제는 위와 같다. 즉,

• 주어진 리스트에서 같은 값의 서로 다른 인덱스가 있고, 그 인덱스의 차를 절댓값 한 값이 k보다 작으면 True, 그렇지 않으면 False 반환.

코드 : 

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        
        dict = {}
        
        for idx in range(len(nums)):
            if nums[idx] in dict and abs(idx - dict[nums[idx]]) <= k:
                return True
            dict[nums[idx]] = idx
        return False

1. 처음 해야 할 일이 뭐지? 같은 값을 가진 서로 다른 두개의 인덱스를 찾는 것. -> 처음 조건문에서 찾고자 하는 값이 이미 딕셔너리 안에 있는지부터 확인한다; 만약 나타난다면, 같은 값이 두번 나타난다는것과 같다(첫번째 조건 nums[i] == nums[j] 만족). 만약, 이미 딕셔너리 안에 추가된 값이 아니라면 dict[nums[idx]] = idx를 통해 딕셔너리 안에 키-값 쌍을 추가해 준다.
2. 일단 이 문제의 조건은 두가지다. 첫번째, 같은 값을 가진 요소가 리스트 안에 두개 이상 존재하는지. 두번째, 그 두개의 인덱스의 값을 빼고, 절댓값을 취했을때 파라미터로 주어진 k보다 작거나 같아야 함.
   
   
3. 그렇다면, 두번째 조건문은 첫번째 조건문이 통과하기 전까진 의미가 없다. 일단 뺄셈을 하려면 우리는 피연산자 2개가 필요하고, 피연산자 2개가 존재하지 않는다면(리스트 안에 중복된 값이 없는 경우), 뒤의 조건은 확인할 필요 조차 없으므로 첫번째 조건을 조건문의 첫번째 조건으로 넘겨준다(첫번째 조건이 fail하면 곧바로 반복문을 빠져나가도록). 
   
   
4. 그 다음, 만약 첫번째 조건문이 통과가 된다면(중복된 요소를 찾았다면, 절댓값 계산을 한후 True or False를 반환한다.

엄청 쉽다. 코드를 보고 설명을 보면 아! 하고 바로 이해하겠지만, 아무런 정보 없이 문제를 풀었다면 어떻게 접근했을지부터 고민을 했을 것이다. 먼저, 중복된 값을 찾는데 딕셔너리(해시맵)를 쓰는 이유부터 알아보자.

- 빠른 조회 시간:
해시맵은 평균적으로 O(1) 시간 복잡도로 키-값 쌍을 조회할 수 있다. 이는 매우 빠른 시간에 특정 값이 해시맵에 존재하는지 확인할 수 있음을 의미한다.(중복값,,,)
배열을 순회하면서 각 요소를 해시맵에 저장하고 조회하면, 중복값을 매우 빠르게 찾을 수 있다.

- 고유한 키 저장:
해시맵은 키-값 쌍을 저장하므로, 각 요소의 인덱스를 값으로 저장하고 요소 자체를 키로 사용할 수 있다. 이를 통해 특정 값이 이미 해시맵에 존재하는지 쉽게 확인할 수 있다.

해시맵 이외에도 중복값을 찾기 위해 사용할 수 있는 몇 가지 자료구조가 있다(내가 처음에 중복된 값을 보자마자 생각난건 집합이다). 각 자료구조의 장단점을 비교해 보겠다.

-집합(Set):
장점: 중복 요소를 자동으로 제거한다. 해시맵과 마찬가지로 O(1) 시간 복잡도로 요소를 추가하고 확인할 수 있다.
단점: 요소의 인덱스를 저장할 수 없다. 인덱스 정보를 필요로 하는 문제에서는 적합하지 않다.(순서 x) 파이썬의 리스트(배열)는 순서(index)가 있는 sequiental 자료구조임. 메모리적인 관점에서 보면 리스트(배열)는 연속된 메모리 공간을 차지한다. 

-정렬된 배열/리스트:
장점: 중복 요소를 찾기 위해 이진 탐색을 사용할 수 있다.
단점: 요소를 추가하거나 정렬하는 데 O(n log n). 특히 실시간으로 데이터가 변경되는 경우 비효율적이다.

-링크드 리스트(Linked List):
장점: 요소를 추가하는 데 O(1) 시간이 소요된다.
단점: 중복 요소를 찾기 위해 전체 리스트를 순회해야 하므로 O(n). 해시맵에 비해 비효율적이다.

문제 : Given an integer array nums where the elements are sorted in ascending order, convert it to a 
height-balanced binary search tree.

여기서 말하는 height-balanced는  이진 트리의 한 종류로, 모든 노드의 왼쪽 하위 트리와 오른쪽 하위 트리의 높이 차이가 1 이하인 트리를 의미한다.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:

        if not nums :
            return None

        mid = len(nums) // 2
        root = TreeNode(nums[mid])

        root.left = self.sortedArrayToBST(nums[:mid])
        root.right = self.sortedArrayToBST(nums[mid+1:])

        return root

처음 생각 : 

- 루트 노드를 어떤 기준으로 정하지? : 루트 노드는 주어진 리스트에서 중간값으로 정해준다. 왜냐하면 주어진 리스트는 오름차순으로 정렬된 리스트이므로 정확히 중간값을 루트로 정해주면, 리스트의 왼쪽 하위 요소들은 left-subtree가 되고, 오른쪽 하위 요소들은 right-subtree가 된다. 

- 자 그러면, 루트를 정했다고 치자. 그러면 왼쪽 서브트리와 오른쪽 서브트리는 어떻게 채워 나가지? 생각해보면 이미 루트값은 맨 처음에 정해지고, 왼쪽, 오른쪽 서브트리를 채워나가면 되므로 뭔가 분할정복 + 재귀가 떠올랐다.

위의 예시 nums = [-10, -3, 0, 5, 9]를 보면, 

1. 최상단 루트노드의 값은 몫 연산자(//)를 사용하여 정수 뒤의 소수점을 버리고 가운데 값을 루트 노드로 정한다. 이 경우, '0'이 루트 노드가 되는것! 그 다음, 0의 왼쪽값 [-10, -3]은 왼쪽 서브트리의 요소들이 될 것이고, 오른쪽 값[5, 9]는 오른쪽 서브트리의 값이 될것이다.

2. 그러면 서브트리에도 똑같은 로직을 취해주면 원하는대로 완성되는가? 예를들어, 리스트의 왼쪽 하위 요소들에 대해 1. 과 같은 로직을 취하면, [-10, -3]의 중간값은 2 // 2 = 1 이므로 -3이다. 또다시 왼쪽 하위요소인 [-10]에 대해 똑같은 로직을 수행하면 mid값은 0이 될것이다(1 // 2). 결국 -10이 루트 노드가 될것이고, 이런 식으로 왼쪽, 오른쪽을 분할정복 + 재귀를 통해 풀어 나갈 수 있다.

※ 몰랐던 내용이나 까먹었었던 내용 : 

파이썬에서 클래스 메서드를 호출할 때 `self`를 사용하는 이유는 그 메서드가 클래스의 인스턴스 메서드임을 나타내기 위해서이다. `self`는 인스턴스 자신을 참조하는 변수로, 클래스 내에서 정의된 메서드나 속성에 접근할 때 사용된다.

`self.`를 사용하는 이유:

1. 인스턴스 메서드 호출:
   클래스 내에서 메서드를 정의할 때, 그 메서드가 인스턴스 메서드임을 나타내기 위해 첫 번째 인자로 `self`를 받는다. 이를 통해 메서드 내에서 인스턴스 속성에 접근하거나 다른 인스턴스 메서드를 호출할 수 있다.

2. 클래스 내에서 재귀 호출:
   인스턴스 메서드가 재귀적으로 자기 자신을 호출하려면 `self`를 사용하여 현재 인스턴스의 메서드를 호출해야 한다. 이렇게 하면 클래스의 다른 인스턴스 메서드와 구분된다.

예를 들어, 주어진 `sortedArrayToBST` 메서드에서 `self.sortedArrayToBST`를 사용하는 이유는 현재 인스턴스의 메서드를 호출하기 위해서이다. 이렇게 하면 재귀 호출이 가능해진다.

예시 : 

class Example:
    def __init__(self, value):
        self.value = value

    def display(self):
        print(self.value)
    
    def increment(self):
        self.value += 1
        self.display()  # self를 사용하여 다른 인스턴스 메서드를 호출

    def recursive_example(self, n):
        if n > 0:
            print(n)
            self.recursive_example(n - 1)  # self를 사용하여 재귀 호출

# 클래스 인스턴스 생성
example = Example(10)

# 인스턴스 메서드 호출
example.increment()  # 출력: 11

# 재귀 메서드 호출
example.recursive_example(5)  # 출력: 5, 4, 3, 2, 1

이 예제에서:
- `self.display()`는 `increment` 메서드 내에서 `display` 메서드를 호출한다.
- `self.recursive_example(n - 1)`은 `recursive_example` 메서드 내에서 재귀적으로 자기 자신을 호출한다.

따라서, `self.`를 사용하는 것은 인스턴스 메서드를 호출할 때 그 메서드가 현재 인스턴스에 속해 있음을 명확히 하기 위해 필요하다.