[알고리즘][Swift] #3. 위장

안녕하세요! caution 입니다. '-'

알고리즘 문제 풀이 세 번째 시간입니다. 이번 문제는 이제까지 풀었던 문제중 가장 짧은 시간내에 풀었어요!

풀면서 고등학교 수학 시간이 떠올랐어요. 그때 외웠던 수학 공식들 다 어디갔지....

마침 이번 주에 2019년 수능이 있었죠. 수험생분들, 수험생 부모님들, 선생님들 모두 고생하셨습니다!!! :)

오늘의 문제는 LEVEL 2 위장 입니다.

문제설명

---

스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.

예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.

종류	이름
얼굴	동그란 안경, 검정 선글라스
상의	파란색 티셔츠
하의	청바지
겉옷	긴 외투

스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

제한 사항

---

스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.

clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.

스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.

같은 이름을 가진 의상은 존재하지 않습니다.

clothes의 모든 원소는 문자열로 이루어져 있습니다.

모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.

스파이는 하루에 최소 한 개의 의상은 입습니다.

이번 문제는 생각보다 빨리 풀었어요. 처음에 문제를 보자마자 고등학교 수학 확률과 통계가 떠올랐습니다.

흔히들 기억하는 빨간 공과 흰 공을 뽑는 문제부터, 원탁에 앉는 문제 등... 다들 기억나시나요?

이 문제는 생각보다 간단합니다. [의상의 이름, 의상의 종류]가 주어지고, 하루에 같은 종류의 의상을 겹치게 입을 수는 없기 때문에 주어진 배열에서 종류 별로 의류가 몇개가 주어지는 지 확인하고 종류별로 조합할 수 있는 경우의 수를 구하면 됩니다. 주어지는 배열이 중복된 의상이 포함된 배열이 아니며, 같은 이름을 가진 의상은 존재하지 않기 때문에 더 이상 의상의 이름을 신경쓸 필요는 없습니다.

이번은 문제를 푸는 논리는 동일했습니다. 하지만 처음부터 문제에서 요구하는 방식으로 풀지는 않았습니다. 그래서 시행착오 또한 함께 적어두겠습니다!

앞서 말씀드렸다시피 로직자체는 다르지 않았습니다. 다만 제가 사용했던 함수들이 달라서 적어봅니다! 코드를 먼저 보시죠!

여기서는 제가 딕셔너리 형태를 사용하지 않고 kind 라는 의상의 종류를 담을 수 있는 String 배열과, 종류별 의상의 수를 저장할 clothesByKind라는 Int 배열을 사용했습니다. 의상배열을 돌면서 kind 배열과 clothesByKind 배열에 같은 위치에 값을 업데이트하도록 설정했습니다.

반복정르오 kind 배열을 돌면서 위치를 찾아내야하기 때문에 비효율적이지만, 동작하는 데에는 문제가 없습니다. 하지만 프로그래머스에서 돌리게 되면 다음과 같은 화면을 보게 됩니다.

저는 xcode 10.1 버전을 쓰고 있습니다.

그리고 swift.org 페이지에서는 제 Xcode 버전에서는 Swift 4.2.1 버전을 쓰고 있다고 알려주네요.

프로그래머스에서는 컴파일 옵션을 확인할 수 있습니다. 오른쪽 상단의 컴파일 옵션을 누르면 확인할 수 있습니다.

swift 버전 차이로 이런 컴파일 오류가 발생합니다. 알고리즘 푸실때 유의하셔야 할 것 같아요!

아무튼, 위의 로직으로 다시 풀어쓴 결과는 이러합니다.

코드가 상당히 길어졌죠? ㅜㅜ 이 방식으로 코드 채점은 통과했지만, 반복문 안에 반복문을 넣는 건 알고리즘에서 매우 좋지 않은 방식입니다. 이렇게 풀어쓰고 나서야 key-value 형태로 저장하는 Dictionary가 생각나서 코드를 다시 고쳐썼답니다.

시행착오 풀이는 여기까지입니다! :)

문제 해결

---

 문제를 푸는 방식은 간단합니다. 종류 1이 n개, 종류 2가 m개 주어진다면 종류 1과 종류 2를 조합하는 경우의 수는 n*m 개 입니다. 다만 주의해야할 점은 이 경우의 수는 모든 종류별로 하나씩 골라야 했을 때의 경우의 수입니다. 하지만 이 문제에서는 종류 1은 고르지 않고 종류 2만 선택하는 경우도 발생할 수 있습니다. (선글라스만 끼고 일하는 노출증 있는 스파이랍니다.) 그렇기 때문에 선택하지 않는다. 라는 선택으로 (n+1) * (m+1) 으로 경우의 수가 나타납니다.

 하지만 아무리 노출증이 있는 스파이라도 의상을 하나라도 걸치고 나가야 하기 때문에, 모든 종류를 선택하지 않을 경우 (종류 1도 선택하지 않음, 종류 2도 선택하지 않음) 의 경우의 수 하나를 빼줍니다. 결국 이 문제에서 경우의 수를 구하는 공식은 (n +1)(m+1) - 1 이 됩니다.

1. clothes에 포함된 의상의 종류와, 종류별 의상의 개수를 저장하는 배열([String:Int]) clothesByKind를 선언하고 빈 배열로 초기화합니다.

2. clothes 배열을 돌면서 이번 의상의 종류를 key로 하여 clothesByKind에서 현재까지의 개수 oldValue를 가져오고, +1을 해줍니다.

2-1. 만약 clothesByKind에 값이 저장되어 있지 않다면 oldValue 를 1로 초기화해줍니다. 해당 종류의 옷을 선택하지 않았을 경우를 생각해서 1을 넣어주는 것입니다.

2-2 이를 통해 clothesByKind에는 의상의 종류와, 종류별 의상 수 + 1 값이 저장되게 됩니다.

3. clothesByKind의 값을 꺼내와서 곱해줍니다.

4. 계산한 결과 값에서 모든 종류의 의상을 선택하지 않았을 경우 1을 빼주고 리턴합니다.

작성된 코드는 다음과 같습니다.

이번 문제를 풀면서, 진짜 다시 수학의 정석이라도 풀어야 하나 싶었답니다. ㅋㅋㅋㅋ

어떠셨나요? 제 풀이가 도움이 됐으면 좋겠습니다.

여기까지, caution이었습니다.

주의하세요!