3월 7일 TIL 코드카타

코드카타

코딩테스트 연습 - 숫자 짝꿍 | 프로그래머스 스쿨

쉬운데?

 

def solution(X, Y):

    answer = []

    Y_list = list(Y)

   

    for i in sorted(X, reverse=True):

        if i in Y_list:

            answer.append(i)

            Y_list.remove(i)

           

    if not answer:

        return '-1'

   

   

    result = ''.join(answer)

   

    return "0" if result == "0" * len(result) else result

solution('100','123450') # 10

시간 초과

Y_list.remove(i)

빼면 오답이 생기는 대신 시간은 줄었음 

.remove 대신 딴거 써야하네 ㅡㅡ

내일 다시

 

Y_list.remove(i)는 리스트에서 값을 찾아 제거하는 작업이기 때문에, 해당 작업은 시간 복잡도가 O(n)입니다. 즉, X_list의 모든 문자에 대해 Y_list에서 문자를 찾고 제거하는 작업을 반복하면, 전체 시간 복잡도가 O(n^2)이 되어 속도가 느려질 수 있음

 

Counter는 각 요소의 개수를 세고, 해당 요소의 존재 여부를 O(1)로 체크할 수 있기 때문에, 리스트에서 값을 찾고 제거하는 시간 복잡도를 O(1)로 개선할 수 있음

 

from collections import Counter

def solution(X, Y):

    answer = []

   

    # Y의 문자를 세는 Counter 객체 생성

    Y_counter = Counter(Y)

   

    # X에서 큰 값부터 순차적으로 확인

    for i in sorted(X, reverse=True):

        if Y_counter[i] > 0:

            answer.append(i)

            Y_counter[i] -= 1  # 해당 문자를 하나 사용했으므로, 카운트를 하나 감소시킴

           

    if not answer:

        return '-1'

   

    result = ''.join(answer)

   

    return "0" if result == "0" * len(result) else result

정답 

 

이제부턴 쉬워도 쉬운게 아니네 ㅇㄹ엄나ㅣ러민ㅇ

 

코딩테스트 연습 - 체육복 | 프로그래머스 스쿨

 

전체 학생수 5명 (n) 중에 체육복 잃어버린 학생 번호 2,4번 (lost) 여별의 체육복을 갖고 있는 학생 번호 1,3,5 (reverse)

단, 여벌을 갖고 있는 학생이 도난을 당하면 reverse에 번호가 있어도 빌려줄 수 없음

 

그때, 체육수업을 들을 수 있는 = 체육복을 빌리던 갖고 있는 학생의 수 최댓값 를 구하면 됨

 

코드로 만들려니까 어지럽네

 

1)  wearable 변수를 새로 만든다 

2)  wearable 변수는 n명수만큼 리스트를 형성하고 각 리스트별 상황을 설정한다

ex) n = 3 일 때, wearable = [[1,?],[2,?][3,?]] 

3) reserve=[1] 값을 업데이트 시킨다     wearable = [[1,2],[2,?][3,?]]

4) lost=[3] 값을 업데이트 시킨다 wearable = [[1,2],[2,?][3,0]]

5) 3)4)로 업데이트된 값이 없으면 그냥 1로 본다 wearable = [[1,2],[2,1][3,0]]

6) wearable 에 조건 0 인 경우 양 옆 중 2가 있으면 2 하나를 빼오고 0에 1을 더한다 

!!  6) 개선점 발견 - 최댓값을 구해야 하는데 이렇게 풀면 최댓값을 못품

 

내일 하자 ....