프로그래머스 LV1. 체육복 - 그리디

 

프로그래머스

 

프로그래머스 LV1. 체육복 - 그리디 문제입니다.

코딩테스트를 오랜만에 준비하는 관계로 LV1 구현부터 차근차근 풀이를 올릴 생각입니다.

 

인터넷에 검색하면 저보다 훨씬 효율적인 풀이가 많이 나오겠지만.. 저만의 감자식 무지성 풀이를 올릴 예정입니다.

def solution(n, lost, reserve):
    # 체육복 있으면 1, 없으면 0으로 설정
    student = [1]*n
    
    # 잃어버린 애들 체육복 뺏어주고
    for l in lost:
        student[l-1] = 0
        
    # 여벌 체육복 가져온 애들 체육복 개수 더해주고
    for r in reserve:
        student[r-1] += 1

    # 이제 없는 애 탐색하면서 옆에 2개인 애 있으면 빌려오기
    for i in range(n):
        if student[i] == 0:
            # 인덱스 0일 때는 왼쪽에서 못 빌려오니까 예외처리 해주고 오른쪽만 빌릴 수 있는지 체크
            if i > 1 and student[i - 1] > 1:
                student[i] += 1
                student[i - 1] -= 1
            # 인덱스 n일 때 오른쪽에서 못 빌려오니까 왼쪽에서 빌려올 수 있나
            elif i < n and student[i + 1] > 1:
                student[i] += 1
                student[i + 1] -= 1
    
    answer = 0
    for x in student:
        if x >= 1:
            answer += 1
    
    return answer

 

맨 처음 1트. 샘플 테스트 케이스도 맞고, 논리적으로 맞았다 생각했는데 틀렸습니다

 

머지? 왜 런타임 에러가 뜨는거지?!?!?!? 라는 생각이 들었죠. 그 이후 디버깅 과정을 거쳤습니다.

뭔가 일부분이 에러가 발생하는 걸 보면 아마도 리스트 끝 쪽 같은 케이스에서 오류가 날 것이라 예상했습니다.

 

그리고 보통 런타임 오류는 인덱스 참조를 넘어가거나 할 때 생기더군요. 그리고 코드를 보다보니 오류가 있습니다.

    # 이제 없는 애 탐색하면서 옆에 2개인 애 있으면 빌려오기
    for i in range(n):
        if student[i] == 0:
            # 인덱스 0일 때는 왼쪽에서 못 빌려오니까 예외처리
            if i > 1 and student[i - 1] > 1:
                student[i] += 1
                student[i - 1] -= 1
            # 인덱스 n일 때 오른쪽에서 못 빌려오니까 왼쪽에서 빌려올 수 있나
            elif i < n and student[i + 1] > 1:
                student[i] += 1
                student[i + 1] -= 1

 

이 부분에서 elif 구분의 student[i+1] 접근에 오류가 있는 것 같더군요.

 

만약 i가 n인 경우, 예를 들어 n=5이고 i가 4일 때 리스트 크기가 5이기 때문에 i+1이라는 인덱스 접근이 안됩니다.

따라서 i<n 이 아니라 i<n-1 로 설정해주어야 되는 거죠.

 

위에서 인덱스 오류가 났던 경우는 쉽게 말해 마지막 학생도 0이고, 왼쪽에서도 못 빌려와서 오른쪽을 점검할 때 오류가 났었을 겁니다. 예를 들어 이런 경우죠

 

n=5, lost = [1, 3, 5], reserve = [2, 4]

 

이 테스트 케이스를 넣게 되면 아래와 같은 로직을 거칩니다.

 

student = [1,1,1,1,1] 로 만든 이후

student = [0,1,0,1,0] 으로 lost 가 반영되겠죠.

그 다음 reserve 가 반영되면 student = [0,2,0,2,0] 가 됩니다.

 

그 이후 로직에 따르면 0 인 경우 왼쪽부터 점검을 하게 됩니다.

 

i = 0일때 멈춰서 왼쪽 점검했는데 못빌려오고, elif 문에서 오른쪽을 점검하며 하나 뺏어오고 이렇게 바뀝니다.

student = [1,1,0,2,0]

 

비슷하게 i=3일 때 왼쪽에서 못 가져오니까 오른쪽에서 가져오게 될 것이고, 이렇게 리스트가 바뀌겠죠.

student = [1,1,1,1,0]

 

그 다음, i=4일 때 점검이 이루어지는데 elif 문에서 index 5를 참조하기 때문에 오류가 발생하는 겁니다.

 

그냥 elif 조건문을 i<n에서 i<n-1로 바꿔주면 해결되는 문제입니다. 라고 생각했으나

 

런타임 오류가 사라졌고 테스트케이스 통과 개수는 많아졌으나 여전히 실패하는 경우가 일부 생기더군요.

 

 

그런데 대부분 맞는 거 보면 로직은 맞는거고, 뭔가 조건문 경계 실수 같은 걸 했겠죠.

            # if i > 1 and student[i - 1] > 1:
            # 이건 생각해보니 3번째부터 체크하는 거더군요
            if i > 0 and student[i - 1] > 1:

 

실제로 그러했습니다.. 왼쪽에서 볼 때 2번째부터 보면 되는데 3번째부터 보고 있었습니다.

제가 쓴 정답 코드는 아래에 전체를 올립니다.

def solution(n, lost, reserve):
    # 체육복 있으면 1, 없으면 0으로 설정
    student = [1]*n
    
    # 잃어버린 애들 체육복 뺏어주고
    for l in lost:
        student[l-1] = 0
        
    # 여벌 체육복 가져온 애들 체육복 개수 더해주고
    for r in reserve:
        student[r-1] += 1

    # 이제 없는 애 탐색하면서 옆에 2개인 애 있으면 빌려오기
    for i in range(n):
        if student[i] == 0:
            # 인덱스 0일 때는 왼쪽에서 못 빌려오니까 예외처리
            if i > 0 and student[i - 1] > 1:
                student[i] += 1
                student[i - 1] -= 1
            # 인덱스 n일 때 오른쪽에서 못 빌려오니까 왼쪽에서 빌려올 수 있나
            elif i < n-1 and student[i + 1] > 1:
                student[i] += 1
                student[i + 1] -= 1
    
    answer = 0
    for x in student:
        if x >= 1:
            answer += 1
    
    return answer

 

 

아주아주 비효율적이지만, 원초적이고 야생에 가까운 코딩으로 LV1 문제를 힘겹게 구현했습니다.

 

코테... 포기하고 인적성이나 준비할까라는 생각이 마구마구 드네요.

 

다른 분들은 어떻게 구현했는지 한 번 훔쳐보도록 하겠습니다.

def solution(n, lost, reserve):
    answer = 0
    for i in range(1, n+1):
        if i not in lost: #안 잃어버린 학생
            answer += 1
        else:
            if i in reserve: #잃어버렸지만 여분도 있는 학생
                answer += 1
                reserve.remove(i)
                lost.remove(i)

    for i in lost: #잃어버리고 여분도 없어서 빌려야 하는 학생
        if i-1 in reserve:
            answer += 1
            reserve.remove(i-1)

        elif i+1 in reserve:
            answer +=1
            reserve.remove(i+1)

    return answer

 

첫번째 루프에서는 모든 학생을 순회하며

1) 안 잃어버린 걸 더하고

2) 아닌 경우 = lost 에 있는 경우. 즉 잃어버린 학생들 중에서

    i) 여분을 가져온 경우, answer에 1을 더하고 reserve와 lost에서 그 인덱스를 삭제한다.

    ii) 여분 없는 경우는 그냥 넘어갔음.

 

두 번째 루프에서

3) 잃어버린 학생 중 여분도 없어서 빌려야하는 학생을 찾는 과정

    저와 비슷한 로직으로 앞 번호에서부터 체크하고, 뒷 번호에서 체크하며 순회를 하는 과정입니다.

 

 

다른 분들 풀이 보면 더 깔끔하긴 한데, 제가 한 풀이도 틀리지는 않은? 느낌이네요.

 

 

코테에 정답이 어딨습니까 답만 맞으면 되죠 하하.

아무튼 프로그래머스 체육복 문제 풀이를 여기까지 마치도록 하겠습니다. 2주간 열심히 달려볼게요!