[Swift] 프로그래머스 연습 문제(Level 1) : 체육복

실제 코딩테스트의 문제를 통하여 알고리즘 분석과 코딩 능력을 향상시킵니다.

 

 

#. 구독 대상

• 기본 알고리즘을 코딩 테스트 문제를 통하여 학습하고 싶으신 분
• 취업 및 이직을 준비하고 계신 개발자
• Swift를 통하여 코딩 테스트 문제를 살펴보고 이해를 하고 싶으신 분
• 코딩 테스트에 대한 거부감을 없애기 위하여 기초부터 하나씩 공부해보고 싶으신 분
• 기타 알고리즘과 문제 해결 능력에 대해서 관심이 있는 모든 개발자분

참고 사항

본 코딩 테스트 문제에 대한 설명 및 해결 방안은 최적의 답이 아닐 수 있습니다.

본 강의에서 지향하는 목표는 바로 특정 문제에 대한 최적의 해결 방법을 찾기보다는 특정한 문제에 대해서 충분히 이해할 수 있고 다양한 방법을 통하여 해결하는 방법을 찾고 향상시키는데 그 목적이 있습니다.

좀 더 좋은 알고리즘 및 코드가 있으시다면 언제든지 본 게시물의 댓글을 통해서 제시해주시면 감사하겠습니다.

 

 

 

---

 

 

 

코딩 테스트 문제

 

먼저 오늘 살펴볼 문제에 대해서 먼저 살펴보겠습니다.

 

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

코딩테스트 연습 - 체육복

 

 

---

 

 

 

문제 설명

 

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

 

 

 

---

 

 

 

제한 조건

 

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

 

 

 

 

 

 

---

 

 

 

 

입출력 예

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

 

입출력 예 설명

 

입출력 예 #1

 

• 1번 학생이 2번 학생에게 체육복을 빌려주고, 3번 학생이나 5번 학생이 4번 학생에게 체육복을 빌려주면 학생 5명이 체육수업을 들을 수 있습니다.

 

입출력 예 #2

 

• 3번 학생이 2번 학생이나 4번 학생에게 체육복을 빌려주면 학생 4명이 체육수업을 들을 수 있습니다.

 

 

 

 

---

 

 

문제 분석

 

문제는 체육복을 잃어버린 학생 번호와 여벌의 체육복을 가진 학생 번호를 입력값으로 주어집니다.

그 상황에서 체육복을 잃어버린 학생은 자신의 번호보다 -1(앞), +1(뒤) 상태의 번호를 가진 학생 중 한 명에게 체육복을 빌려서 수업에 참가할 수 있습니다. 최종적으로 체육복을 읽어버린 학생들이 체육복을 빌려서 수업에 참가할 수 있는 최대 학생 수를 구하는 문제입니다.

 

 

 

 

---

 

 

 

알고리즘

 

위의 내용을 기반으로 하여 본 문제를 해결하기 위한 알고리즘을 살펴보면 아래와 같습니다.

 

• 학생들의 체육복을 수를 저장할 배열로 준비합니다.
• 해당 배열 초기값은 0으로 모두 채워줍니다.(모든 학생이 1벌의 체육복이 있는 경우 0으로 가정)
• 그런다음 체육복을 잃어 버린 학생의 경우는 -1, 여벌이 있는 학생은 1 로 채워넣습니다.
• 체육복 수를 저장한 배열을 설정한 후 전체 배열을 하나씩 돌면서 -1(체육을 잃어 버린 경우)로 설정된 배열에서 앞(-1), 뒤(+1) 번호(인덱스)를 가지는 학생 중에서 여벌의 체육복이 있는 경우(값이 1인 경우) 해당 학생에게 체육복을 빌린다.
• 체육복을 빌린 경우는 빌려준 학생의 체육복 수를 -1을 더해주고 빌린 학생의 체육복 수는 +1을 해준다.
• 최종 체육복 수를 저장한 배열에서 0보다 큰 경우의 수를 가지는 배열의 갯수를 센 후 반화하면 최종 정답이 된다.

 

 

 

 

---

 

 

 

코드 설명

 

그렇다면 위의 알고리즘에 대해서 하나씩 살펴보면서 코드로 작성을 해보도록 하겠습니다.

 

 

• 학생들의 체육복을 수를 저장할 배열로 준비합니다.
• 해당 배열 초기값은 0으로 모두 채워줍니다.(모든 학생이 1벌의 체육복이 있는 경우 0으로 가정)

// 체육복애 여별의 수를 저장하는 배열, 초기값은 0
var clothCount = Array(repeating: 0, count: n)

 

 

• 그런다음 체육복을 잃어 버린 학생의 경우는 -1, 여벌이 있는 학생은 1 로 채워넣습니다.

// 체육복을 읽어 버린 경우 -1로 설정
for i in lost { clothCount[i-1] = -1 }
    
// 여벌 체육복이 있는 경우 1로 설정
for j in reserve { clothCount[j-1] = 1 }

 

 

• 체육복 수를 저장한 배열을 설정한 후 전체 배열을 하나씩 돌면서 -1(체육을 잃어 버린 경우)로 설정된 배열에서 앞(-1), 뒤(+1) 번호(인덱스)를 가지는 학생 중에서 여벌의 체육복이 있는 경우(값이 1인 경우) 해당 학생에게 체육복을 빌린다.
• 체육복을 빌린 경우는 빌려준 학생의 체육복 수를 -1을 더해주고 빌린 학생의 체육복 수는 +1을 해준다.

// 전체 학생의 여벌 체육복 배열을 인덱스와 값을 하나씩 비교하면 순회
for (index, k) in clothCount.enumerated() {
	// 현재 학생이 체육복을 읽어 버린 경우
	if k == -1 {
		// 앞의 학생이 여벌 체육복이 있는지(== 1) 비교한 후 있으면 빌림
		if index > 0 && clothCount[index-1] == 1 {
			clothCount[index] += 1
			clothCount[index-1] += -1
		}
		// 뒤의 학생이 여벌 체육복이 있는지 비교한 후 있으면 빌림
		else if index < clothCount.count - 1 && 
				clothCount[index+1] == 1 {
			clothCount[index] += 1
			clothCount[index+1] += -1
		}
	}
}

 

 

• 최종 체육복 수를 저장한 배열에서 0보다 큰 경우의 수를 가지는 배열의 갯수를 센 후 반화하면 최종 정답이 된다.

// 최소 체육복이 있는 경우(>= 0)의 학생의 수를 최종 반한
return clothCount.filter{ $0 >= 0 }.count

 

 

 

위의 코드들을 모두 조합하여 최종 코드를 완성하면 아래와 같습니다.

 

 

최종 코드

import Foundation

func solution(_ n:Int, _ lost:[Int], _ reserve:[Int]) -> Int {
    // 체육복애 여별의 수를 저장하는 배열, 초기값은 0
    var clothCount = Array(repeating: 0, count: n)
    
    // 체육복을 읽어 버린 경우 -1로 설정
    for i in lost { clothCount[i-1] = -1 }
    
    // 여벌 체육복이 있는 경우 1로 설정
    for j in reserve { clothCount[j-1] = 1 }
    
    // 전체 학생의 여벌 체육복 배열을 인덱스와 값을 하나씩 비교하면 순회
    for (index, k) in clothCount.enumerated() {
        // 현재 학생이 체육복을 읽어 버린 경우
        if k == -1 {
            // 앞의 학생이 여벌 체육복이 있는지(== 1) 비교한 후 있으면 빌림
            if index > 0 && clothCount[index-1] == 1 {
                clothCount[index] += 1
                clothCount[index-1] += -1
            }
            // 뒤의 학생이 여벌 체육복이 있는지 비교한 후 있으면 빌림
            else if index < clothCount.count - 1 && 
                    clothCount[index+1] == 1 {
                clothCount[index] += 1
                clothCount[index+1] += -1
            }
        }
    }
    
    // 최소 체육복이 있는 경우(>= 0)의 학생의 수를 최종 반한
    return clothCount.filter{ $0 >= 0 }.count
}

 

 

 

 

---

 

 

 

이상으로 오늘 제시한 문제에 대해서 분석 및 코드를 작성해 보았습니다.

 

 

 

감사합니다.

 

 

 

 

---

[참고 자료(References)]

 

[1] 프로그래머스 - 체육복 : programmers.co.kr/learn/courses/30/lessons/42862