알고리즘 D-21

About this offer

1번문제 : 배열 만들기 6 #### (1) 내 풀이 def solution(arr): stk = [] i = 0 while i < len(arr) : if stk == []: stk.append(arr[i]) i = i+1 elif stk[-1] == arr[i]: del stk[-1] i = i+1 else: stk.append(arr[i]) i = i+1 return [-1] if stk == [] else stk 문제에서 설명한걸 있는 그대로 코드로 옮겨담은 상태 (2) 다른 사람 풀이 def solution(arr): stk = [] for i in range(len(arr)): if stk and stk[-1] == arr[i]: stk.pop() else: stk.append(arr[i]) return stk or [-1] 문제를 보면 실행해야 하는 실제 행동은 총 3가지 i + 1 stk.append(arr[i]) : arr[i] 를 stk 에 추가 stk.pop() : stk 의 마지막 원소를 제거 for 문을 이용하면 i 가 자동으로 1씩 증가하기 때문에 i + 1 을 직접 작성할 필요가 없다. if stk and stk[-1] == arr[i] stk 에 값이 존재하고, stk 의 마지막 값이 arr[i] 와 같은 경우 stk 가 비어 있으면 False 로 판단된다. 따라서 stk 에 값이 있고 마지막 값까지 같으면 True 가 된다. True 일 경우 stk.pop() 을 실행하여 마지막 원소를 제거한다. else stk 가 비어 있거나 stk[-1] != arr[i] 인 경우 stk.append(arr[i]) 를 실행하여 arr[i] 를 stk 에 추가한다. return stk or [-1] 파이썬에서는 값이 있는 리스트는 True , 빈 리스트 [] 는 False 로 판단한다. stk 에 값이 있다면 stk 가 True 이므로 stk 를 반환한다. stk 가 빈 리스트라면 False 이므로 or 뒤의 [-1] 을 반환한다. 2번문제 : 무작위로 K개의 수 뽑기 #### (1) 내 풀이 def solution(arr, k): answer = [] for i in arr: if not i in answer and len(answer) < k: answer.append(i) while len(answer) < k: answer.append(-1) return answer len(answer) < k 조건을 추가했지만 break 가 없기 때문에, answer 가 이미 k 개가 된 후에도 for 문은 arr 의 나머지를 계속 확인함 while len(answer) < k 를 사용하여 answer 의 길이가 k 보다 작을 경우 -1 을 추가함 (2-1) 다른 사람 풀이 def solution(arr, k): ret = [] for i in arr: if i not in ret: ret.append(i) if len(ret) == k: break return ret + [-1] * (k - len(ret)) 내 풀이와 다르게 ret (내 풀이에서는 answer )의 길이가 k 와 같아지면 break 를 사용하여 for 문을 바로 종료함 (k - len(ret)) : 현재 ret 에서 부족한 길이의 개수를 구함 [-1] * 2 : 리스트에 * 를 사용하면 리스트의 요소를 지정한 횟수만큼 반복할 수 있음 [-1] * 2 → [-1, -1] ret + [-1] * (k - len(ret)) : ret 의 부족한 길이만큼 -1 을 추가하여 반환함 (2-2) 다른 사람 풀이 def solution(arr, k): res = list(dict.fromkeys(arr)) res.extend([-1] * max(0, k - len(res))) return res[:k] res = list(dict.fromkeys(arr)) : arr 에서 중복을 제거하고 순서를 유지해서 리스트로 만듦 dict.fromkeys(arr) → {1: None, 2: None, 3: None} 딕셔너리는 같은 key를 중복해서 가질 수 없기 때문에 중복이 제거됨 Python 3.7 이상에서는 딕셔너리가 입력된 순서를 유지함 res.extend([-1] * max(0, k - len(res))) : res 의 길이가 k 보다 작을 경우 부족한 만큼 -1 을 추가함 max(0, k - len(res)) : 부족한 개수가 음수가 되지 않도록 최소값을 0 으로 설정함 res[:k] : res 에서 앞에서부터 k 개까지만 잘라서 반환함 3번문제 : 배열의 길이를 2의 거듭제곱으로 만들기 #### 정수 배열 arr이 매개변수로 주어집니다. arr의 길이가 2의 정수 거듭제곱이 되도록 arr 뒤에 정수 0을 추가하려고 합니다. arr에 최소한의 개수로 0을 추가한 배열을 return 하는 solution 함수를 작성해 주세요. (1-1) 내 풀이 def solution(arr): i = 1 while len(arr) != 2 ** i: i = i + 1 if 2 ** i > len(arr): arr.extend([0] * (2 ** i - len(arr))) return arr len(arr) 과 정확히 같은 2의 거듭제곱을 찾도록 != 를 사용했기 때문에 문제가 발생함 arr 의 길이가 5처럼 2의 거듭제곱이 아닌 경우 2 ** i 가 5와 같아질 수 없기 때문에 반복이 끝나지 않음 따라서 arr 의 길이보다 크거나 같은 2의 거듭제곱을 찾아야 함 (1-2) 내 풀이 def solution(arr): i = 0 while 2 ** i < len(arr): i = i + 1 arr.extend([0] * (2 ** i - len(arr))) return arr arr 의 길이보다 크거나 같은 가장 작은 2의 거듭제곱 을 찾아야 함 따라서 2 ** i 가 len(arr) 보다 작은 동안 i 를 1씩 증가시킴 2 ** i 가 len(arr) 보다 크거나 같아지면 반복을 종료함 이후 2 ** i - len(arr) 으로 부족한 길이를 구하고, 그만큼 0 을 추가함 i 를 0 부터 시작하면 20 = 1 도 포함할 수 있기 때문에 arr 의 길이가 1 인 경우에도 올바르게 처리할 수 있음