프로그래머스 체육복(Lv1)

문제

https://programmers.co.kr/learn/courses/30/lessons/42862

초기코드

 def solution(n, lost, reserve):
 
    answer = 0
    lost.sort()
    reserve.sort()

    for i in range(len(reserve)):
      for j in range(len(lost)):
        if reserve[i] == lost[j]:
          reserve.pop(i)
          lost.pop(j)
          break

    for i in range(len(lost)):
      for j in range(len(reserve)):
        if abs(lost[i]-reserve[j]) == 1:
          lost.pop(i)
          reserve.pop(j)
          break
          
    answer = n - len(lost)
    return answer
    

결과

solution(5,[2,4],[1,3,5])

터졌다...

for문이 도는 중에 pop연산으로 인해 인덱스에 변화가 생겨서 문제가생겼다.

1차수정

def solution(n, lost, reserve):
  answer = 0
  lost.sort()
  reserve.sort()

  ##중복값제거
  for i in range(len(reserve)):
    for j in range(len(lost)):
      if reserve[i] == lost[j]:
        lost.pop(j)
        reserve.pop(i)
        break

  for i in range(len(reserve)):
    for j in range(len(lost)):
      if reserve[i]-1 == lost[j]:
        lost.pop(j)
        break
      elif reserve[i]+1 == lost[j]:
        lost.pop(j)
        break
  answer = n - len(lost)
  return answer

1차수정 결과

주어진 테스트케이스는 2개는 모두 통과하였지만, 터지는값들이 많다.

도난배열과 여분배열의 중복값을 제거하는부분에서 for문 내 pop연산때문에 문제가 생겼을것이다.
아래쪽 단락의 for문의 경우 실질적인 계산에는 lost 배열만 있으면 되기에
reserve 인덱스로 for문을 돌리며 lost값만 pop처리를 해줘서 계산하는부분은 for문 index가 변하지않게 해결했는데 초기 중복값 제거하는 for문의경우 두 배열 모두에서 pop처리를 해줘야하므로 난감해졌다..
물론 배열하나 더만들어서 중복값 저장후 처리를 해주면 되기야 하겠지만, 이렇게 귀찮고 복잡하게 풀라고 냈을리가 없기에 다른방법을 찾아보았다.

새로 공부한부분: SET (in python)

set 이란?

https://wikidocs.net/16044 참고!

list나 dict의 경우 대괄호나 중괄호로 선언할 수 있었다만,
set은 dict타입과 동일한 중괄호를 사용하므로, 반드시 set 생성자를 이용해야함!!

>>> s = {}
>>> type(s)
<class 'dict'>
>>> s = set()
>>> type(s)
<class 'set'>

>>> s = set([1,3,5,7])
>>> s
{1, 3, 5, 7}

중복된 값은 자동으로 중복이 제거 된다.

>>> s = {1, 5, 1, 1, 1, 3, 7}
>>> s
{1, 3, 5, 7}

set(집합)은 순서가 없다. 어떤 값이 먼저 나올지 알 수 없다.

>>> for i in {1, 2, 4, 8, 16,32}:
...     print(i)
... 
32
1
2
4
8
16

원소 추가는 add 메소드를 이용,

>>> k = {100, 105}
>>> k.add(50)
>>> k
{105, 50, 100}

여러개 추가는 update 메소드

k = {1, 2, 3}
>>> k.update([3, 4, 5])
>>> k
{1, 2, 3, 4, 5}

remove(item) : item에 해당하는 원소를 제거하고, 없으면 KeyError 발생

>>> k = {1, 2, 3}
>>> k.remove(3)
>>> k
{1, 2}
>>> k.remove(3)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
KeyError: 3

discard(item) : item에 해당하는 원소를 제거하고, 없어도 에러발생하지 않음

>>> k = {1, 2, 3}
>>> k.discard(3)
>>> k
{1, 2}
>>> k.discard(3)
>>> k
{1, 2}

이외에도 차집합, 교집합, 합집합 등 집합간의 연산이 가능
중복제거도 차집합을 통해 빠르게 가능하다.

주어진 문제의 경우 학생수 30명 이하이기에
O(n) 연산이면 아주 충분.

Set 시간복잡도:

정답코드

def solution(n, lost, reserve):
   answer = 0

  # 중복값 제거
   set_lost = set(sorted(lost)) - set(sorted(reserve))
   set_reserve = set(sorted(reserve)) - set(sorted(lost))


   for i in set_reserve:
     if i-1 in set_lost:
       set_lost.remove(i-1)

     elif i+1 in set_lost:
        set_lost.remove(i+1)

   answer = n - len(set_lost)

   
   return answer

Set 공부 끝!!