(프로그래머스 with python) 완주하지 못한 선수
완주하지 못한 선수 (Level1)
처음 문제를 풀때 참여한 수를 for문을 통해 루프를 돌면서
그 중 완주한 선수가 존재하면 완주한 선수 리스트와 참여한 선수 리스트에서
해당 선수를 remove로 각각 빼내는 방법으로 접근하였다..
(동명이인을 고려해서 두개의 리스트에서 각자 빼주었다.)
다른 조건을 하나도 생각하지 못한 로직이였다.
특히 IndexError: list index out of range 의 에러가 왜 나는지 알 수가 없었다. remove 함수에서 에러가 있는것을 보고 for문과 remove에 대해서 찾아보았다.
def solution(participant, completion):
answer = ''
for i in range(len(participant)):
if participant[i] in completion:
participant.remove(participant[i])
completion.remove(participant[i])
print(participant)
return answer
몇몇개의 블로그에서 for문에서 remove 쓸때 주의점 과 같이 remove의 주의점에 대해 설명을 하고 있었다. 설명을 하자면 remove는 원본을 훼손하는 함수 이다. 코드를 보고 이해하는게 빨랐기 때문에 아래의 코드를 봐보자.
for문을 통해 nums안의 값이 차례대로 제거되는 상황을 기대했지만 2와 4는 제거되지 않고 그대로 nums안 리스트에 남아있는것을 보았다. 왜그런가하니 for문은 루프를 돌때 1번째 루프에서는 0번째 원소에 접근하고 이후 1번째,,2번째,, 순차적으로 접근을 하게 된다. 이때 첫번째 루프가 돌때 0번째 원소인 1이 제거되고 nums=[2,3,4] 로 변경된다. 0번째 인덱스에는 2가 존재하게 되는셈이다.
for문이 2번째 돌때 1번째 원소에 접근하게 되는데 이때 1번째 인덱스에는 3이 존재하게 된다. 그렇기 때문에 2는 건너뛰고 3이 제거되게 되고 nums=[2,4]가 된다. 이후 0번째 인덱스에는 2가 존재하고 1번째 인덱스에는 4가 존재하게 된다. 이후 for문이 3번째 돌때 2번째 인덱스는 없기 때문에 for문이 루프를 빠져나오게 되는 것이다.
nums = [1,2,3,4]
for num in nums:
print('제거전 nums',nums)
nums.remove(num)
print('제거후 nums',nums)
'''
제거전 nums [1, 2, 3, 4]
제거후 nums [2, 3, 4]
제거전 nums [2, 3, 4]
제거후 nums [2, 4]
'''
이후 remove를 사용하기 위해서는 복제된 리스트를 사용해야 된다는 것을 알게되었다. 내가 아는 방법으로 복제를 한 후 다시 로직을 실행시켜보았지만 똑같은 결과가 나왔다.. 그래서 이번에는 리스트 복제 라는 키워드로 구글링을 해보았다
nums = [1,2,3,4]
numss = nums
for num in numss:
print('제거전 nums',nums)
nums.remove(num)
print('제거후 nums',nums)python
print(id(numss), id(nums)) # 140503555416648 140503555416648
다행히 나와 똑같은 생각으로 로직을 구현했다가 문제가 발생한 몇몇의 블로그글이 있었다. 위의 로직을 보면 별 문제없이 복사가 되었다고 생각했지만 정확히 말하면 numss와는 nums의 메모리 주소값을 복사한 것 이라고 한다. 즉 같은 메모리를 참조하고 있는것이다. 그렇기 때문에 둘 중 하나의 리스트가 수정이 되면 두개의 리스트 모두 수정이 된다. 결국엔 원본값을 훼손한거나 마찬가지라는 소리이다. id를 통해서 똑같은 주소를 가리키고 있다는 것을 확인해보면 된다. 다른 메모리를 참조하는 복사를 하고 싶을때는 어떻게 하는가.. 정말 생각보다 많은 방법이 존재하고 있었다…!! (아직도 python 초보자라는것을 다시한번 느끼고 깨닫는 문제였다…)
복사하는 4가지 방법 (해당부분은 넘어가도 좋다 -!)
슬라이싱
슬라이싱을 이용해 모든 변수를 정의하면 새로운 객체가 만들어진다.
nums = [1,2,3,4]
for num in nums[:]:
print('제거전 nums',nums)
nums.remove(num)
print('제거후 nums',nums)
'''
제거전 nums [1, 2, 3, 4]
제거후 nums [2, 3, 4]
제거전 nums [2, 3, 4]
제거후 nums [3, 4]
제거전 nums [3, 4]
제거후 nums [4]
제거전 nums [4]
제거후 nums []
'''
list()
list 함수를 이용해 복사하고자 하는 리스트 객체를 다시 선언하면 두개의 리스트는 서로 다른 메모리를 참조하게 된다
nums = [1,2,3,4]
for num in list(nums):
print('제거전 nums',nums)
nums.remove(num)
print('제거후 nums',nums)
'''
제거전 nums [1, 2, 3, 4]
제거후 nums [2, 3, 4]
제거전 nums [2, 3, 4]
제거후 nums [3, 4]
제거전 nums [3, 4]
제거후 nums [4]
제거전 nums [4]
제거후 nums []
'''
copy()
copy 함수를 이용하면 마찬가지로 다른 리스트에 복사하는 기능이기 때문에 다른 메모리를 참조하게 된다 (가독성을 따졌을때 해당 방법을 추천한다고 한다)
nums = [1,2,3,4]
for num in nums.copy():
print('제거전 nums',nums)
nums.remove(num)
print('제거후 nums',nums)
'''
제거전 nums [1, 2, 3, 4]
제거후 nums [2, 3, 4]
제거전 nums [2, 3, 4]
제거후 nums [3, 4]
제거전 nums [3, 4]
제거후 nums [4]
제거전 nums [4]
제거후 nums []
'''
list 연산
빈 리스트에 새롭게 복사할 리스트를 더하면 새로운 리스트 객체에 nums의 요소들이 더해져 서로 다른 메모리를 참조하는 리스트로 복사가 가능하다
nums = [1,2,3,4]
numss = [] + nums
for num in numss:
print('제거전 nums',nums)
nums.remove(num)
print('제거후 nums',nums)
print(id(numss), id(nums))
'''
제거전 nums [1, 2, 3, 4]
제거후 nums [2, 3, 4]
제거전 nums [2, 3, 4]
제거후 nums [3, 4]
제거전 nums [3, 4]
제거후 nums [4]
제거전 nums [4]
제거후 nums []
140503555509384 140503555133064
'''
이후 문제를 다시 풀어 정확성 테스트에서는 100이 나왔지만 효율성 테스트에서는 0이 나오는 결과 를 받게 되었다.. remove함수는 list자료형에서는 시간복잡도 o(n)을 가지고 있었다..
for문 또한 o(n)을 가지고 있었기 때문에 o(n^2)이라는 시간복잡도를 가지게 되는 로직이였다.. 최소한 o(n)으로 만들어줘야 하였다. 해당 문제를 해시를 이용해 풀라는 이유가 있었나보다.. 그래서 다시 돌아와 파이썬 해시 에 대해 찾아보았다.
# 효율성 테스트 x - 시간초과
def solution(participant, completion):
answer = ''
par = participant
com = completion
for i in participant[:]:
if i in completion:
par.remove(i)
com.remove(i)
else:
answer += i
return answer
해시 (= dict)
파이썬에서 해시 구현은 딕셔너리 구현이라고 생각하면 된다. 즉 딕셔너리를 사용하여 해당 문제를 풀어나가야 했다. 새로운 딕셔너리 변수값을 하나 지정한후 참여자를 for문을 통해 루프를 돌리면서 참여자의 이름을 키로 제공해 딕셔너리의 키값에 해당 이름이 존재하지 않으면 새롭게 데이터를 딕셔너리에 추가하였고 딕셔너리 키값에 이름이 존재하면 해당되는 값에 1을 추가해주었다.
def solution(participant, completion):
answer = {}
for i in participant:
if i in answer:
answer[i] += 1
else:
answer[i] = 1
return answer
a = ["marina", "josipa", "nikola", "vinko", "filipa"]
b = ["josipa", "filipa", "marina", "nikola"]
result = solution(a, b)
print(result)
'''
{'marina': 1, 'josipa': 1, 'nikola': 1, 'vinko': 1, 'filipa': 1}
'''
이후 해야 할 일은 참여한 사람중 완주한 사람들을 빼주어야 한다. 즉 completion의 이름을 딕셔너리에서 빼주어야한다 함수 안에 아래 로직을 추가해주었다
for i in completion:
if i in answer:
answer[i] -= 1
'''
{'marina': 0, 'josipa': 0, 'nikola': 0, 'vinko': 1, 'filipa': 0}
'''
마지막으로 할 일은 값이 존재하는 키값을 뽑아내야 한다. 동명이인이 1명이상일 경우를 생각해 key에 대한 값이 0이상인 값들을 리스트에 담아주었다. 하지만 문제에서는 항상 한명의 값이 나오는듯 하다.. 그래서 인덱스 [0]을 붙여 나온 값을 return해주었다
def solution(participant, completion):
answer = {}
for i in participant:
if i in answer:
answer[i] += 1
else:
answer[i] = 1
for i in completion:
if i in answer:
answer[i] -= 1
return [k for k in answer.keys() if answer[k] > 0][0]
lambda함수를 사용하면 좀더 간단하게 return값을 추출할 수 있다
answer = max(answer.keys(),key=(lambda k: answer[k]))