99클럽 코테 스터디 4일차 TIL - 그리디 알고리즘

오늘의 학습 키워드

그리디 알고리즘

오늘 공부한 내용

리스트에서 요소 삭제 / 예외적인 상황 찾아보기

오늘의 회고

오늘은 재귀함수가 아닌 가장 최적의 해를 찾는 탐욕법 알고리즘을 풀어보았다.

처음에 문제를 읽었을 때는 전체 리스트를 1로 초기화 한 후, 도둑이 체육복을 뺏어가면 0으로 만들고, 교복 여벌이 있다면 2로 바꾼다음

체육복을 빼앗긴 사람 중 왼쪽과 오른쪽을 체크해서 체육복 여벌이 있다면 여벌이 있는 사람은 1로 갱신하고 빼앗긴 사람은 체육복을 받아 1로 갱신하는 로직을 생각했다.

그 후 리스트 안의 데이터가 1이상인 것만 확인하여 갯수를 새면 해결될 것이라고 생각했다.

문제를 작성 후 테스트 케이스를 실행하는데 테스트 통과라고 해서 바로 채점을 받았다.

결과는 실패였다. 정확성이 53프로였다..

테스트 케이스 검증에 실패 한 후 내가 찾지 못한 반례(=예외케이스)를 찾아보기 시작했다.

찾아보니 반례 중 체육복을 빼앗긴 사람의 순서가 마지막이거나 첫번째인 사람이 있었다.

왼쪽과 오른쪽을 체크하는 부분에서 체육복을 빼앗긴 사람의 순서는 고려하지 않아 런타임에러가 난것이였다 (=배열의 사이즈보다 작거나 큰 경우를 체크 안함).

위의 경우를 고려하여 반영 후 다시 체점을 시작했다.

이번에는 통과 할 수 있을 것이라 생각했다. 하지만 내 예상과 달랐다. 결과는 실패였다. 이번에는 정확성이 83프로였다..

두번의 실패를 겪고 다시 반례를 찾기 시작했다. 테스트 케이스 중 틀린 테스트 케이스 번호를 보고 질문하기 커뮤니티에 들어가 반례를 찾기 시작했다.

틀린 테스트 케이스의 번호별로 반례를 들어준 사례들이 많이 있었다. 그 중 하나는 체육복을 빼앗긴 사람과 체육복의 여벌을 갖고온 사람이 중복적으로 있다는 것이였다.

내가 생각한 로직에 의하면 만약, (5, [4, 5], [3, 4]) 라는 데이터가 들어온다면

1. 5명의 사람이 처음 초기화 단계에서는 [1 1 1 1 1]
2. 체육복을 빼앗긴 사람을 -1 시켜주고 [1 1 1 0 0]
3. 체육복의 여벌을 갖고온 사람을 +1 시켜주고 [1 1 2 1 0]
4. 현재 체육복을 빼앗긴 사람의 입장(4, 5)에서 왼쪽과 오른쪽을 체크하여 여벌을 갖고 왔는지 (=2)인지 판단하는 로직을 세웠다.
5. 리스트 안에 1이상인 것들의 갯수를 샌다.

4번 로직을 구현하는 부분이 문제였던 것 같다.

디버깅을 통해서 차근 차근 살펴보니 3번까지는 내가 의도한대로 [1 1 2 1 0]으로 맞아떨어졌다.

하지만 다음 4번의 상황을 살펴보니 체육복을 빼앗긴 4번이 왼쪽이 체육복의 여벌을 갖고왔다고 판단하여(=2) +1을 해주는 것이였다. => [1 1 1 2 0]

그 다음 상황을 다시 지켜보니 체육복을 빼앗긴 5번이 4번에게 체육복의 여벌을 갖고왔다고 판단하게되어 +1을 해주는 상황이 일어났다. => [1 1 1 1 1]

그 결과 결과값은 5가 되어 테스트 케이스가 실패하고 말았다.

이 경우 생각해보니 4번이 체육복을 빼앗겼는데, 체육복 여벌을 갖고 왔다면 결국 아무일도 일어나지 않는 상황이였다.

즉, 중복을 제거하면 되겠구나 생각하여 중복을 제거하고 다시 제출을 했다.

하지만 이번에도 실패하고 말았다.. 이번에는 정확성이 93프로였다.

여기에서 반례를 찾아봤지만 아무리 찾아도 찾을 수 없어 결국 다른 사람들이 작성한 코드를 보고 말았다 ㅠㅠ

체육복을 잃어버린 사람 리스트와 체육복 여벌을 갖고온 사람의 리스트를 정렬해야하는 것이였다. ㅠㅠ

어제 저녁 늦게까지 고민하고 반례를 찾아보고 했기 때문에 리스트를 왜 정렬하는지에 대해서는 다시 찾아봐야할 것 같다.

너무 성급하게 해서 일까 고민을 많이 하지 않아서 일까.. 문제가 쉽게 풀리지 않는 느낌이다.

다음번에는 조금 더 여유를 가지고 풀 수 있도록 해야겠다.

결과물

문제내용

체육복을 갖고온 사람 중 몇 명이 체육복을 도둑맞았다. => lost리스트

여벌의 체육복을 갖고온 사람이 있다. => reverse리스트

여벌의 체육복을 가져온 사람은 체육복을 도둑맞은 사람에게 빌려줄 수 있다.

단, 만약 5명 중 3번째 사람이 도둑 맞았다면 2번째 사람과 4번째 사람 즉, 양옆에 있는 사람들에게만 빌릴 수 있다.

전체 학생의 수 2 <= x >= 30 : 2명 이상 30명 이하 :: n^2의 스케일도 풀 수 있는 문제 30^2 = 900

풀이방법

1. 체육복을 명 수 만큼 초기화한다. (일단, 전부 체육복을 가지고 왔기 때문에 예시)[1 1 1 1 1]로 초기화)
2. 체육복을 잃어버린 사람, 체육복 여벌을 갖고 온 사람들을 정렬한다.
3. 체육복을 잃어버린 사람과 체육복의 여벌을 갖고 온 사람 중 같은 사람이 있다면 제거한다 (중복제거).
4. 체육복을 잃어버린 사람 중 왼쪽과 오른쪽에 체육복의 여벌을 갖고온 사람이 있는지 체크한다. (예시 : [1 2 0 2 1] : 3번의 입장에서는 2,4번이 체육복을 갖고옴)
   • 있다면 : 체육복의 여벌을 갖고온 사람에게 빌린다. -1 / 체육복을 잃어버린 사람이 체육복을 얻는다. +1 => [1 1 1 2 1]
   • 없다면 : 아무것도 하지 않는다.
5. 체육복을 갖고 있는 리스트에서 1이상인 데이터의 갯수를 샌다.

def solution(n, lost, reserve):

    uniform = [1] * n
    lost.sort()
    reserve.sort()

    for i in reserve[:]:
        if i in lost:
            reserve.remove(i)
            lost.remove(i)

    for index in reserve:
        uniform[index - 1] += 1

    for index in lost:
        uniform[index - 1] -= 1
    
    for index in lost:
        if index - 2 >= 0 and uniform[index - 2] == 2:
            uniform[index - 2] -= 1
            uniform[index - 1] += 1
        elif index <= len(uniform) - 1 and uniform[index] == 2:
            uniform[index] -= 1
            uniform[index - 1] += 1
       
    
    answer = 0
    for i in uniform:
        if i >= 1:
            answer += 1
    
    return answer

result = solution(5, [4, 5], [3, 4])
print(result)