알고리즘

124의 나라의 숫자

문제

124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다.

124 나라에는 자연수만 존재합니다.
124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다.
예를 들어서 124 나라에서 사용하는 숫자는 다음과 같이 변환됩니다.

10진법	124 나라	10진법	124 나라
1	1	6	14
2	2	7	21
3	4	8	22
4	11	9	24
5	12	10	41

해설

1부터 10까지 124를 통해 구성되어 있는 것을 보게 되면 1,2,4로 구성이 되어 있습니다. 그리고 십의자리에는 1,2,4 가 반복이 되어 있어 반복문, 재귀를 사용해서 풀 수 있는데 재귀를 사용했습니다.

재귀(recursive function)

어떤 함수에서 자신을 다시 호출하여 작업을 수행하는 방식의 함수를 의미합니다. 다른 말로는 재귀호출, 되부름 이라고도 합니다.

재귀함수를 작성할때에는 함수 내에서 다시 자신을 호출 한 후 그 함수가 끝날때 까지 함수 호출 이후의 명령문이 수행되지 않는 다는 사실과 종료조건이 꼭 포함되어야 한다는 부분을 인지하고 작성하면 무한 루프를 방지할 수 있습니다.

ex)

def countdown(n):
    if n == 0:
      print('boom')
    else:
      print(n)
      countdown(n-1)

countdown(10)

결과값 - > 10 9 8 7 6 5 4 3 2 1 boom

이런식으로 나오게 됩니다.

숫자가 작아지면서 함수를 지속적으로 재귀하다가 n이 1이 되면서 더이상 재귀하지 않을 때 print가 됩니다!!

재귀함수를 보게 되면 함수가 더이상 실행 되지 않게 하는 조건부와, 실행되게하는 조건부가 존재한다는 것을 알 수있습니다.

---

이런 재귀함수를 사용해서 문제를 풀어보면

이런식으로 재귀 함수가 가능하다.
1,2,4가 반복이 되므로 n이 3보다 작을 경우에는 1,2,4 를 하면 되지만 3 이 넘어가게 될 경우에는 몫 과 나머지를 구하고 몫이 3보다 클 경우 계속 재귀적으로 처리하는 방식으로 풀어줬다.

---

위장

문제

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

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

종류 이름
얼굴 동그란 안경, 검정 선글라스
상의 파란색 티셔츠
하의 청바지
겉옷 긴 코트
스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
• 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.
• 같은 이름을 가진 의상은 존재하지 않습니다.
• clothes의 모든 원소는 문자열로 이루어져 있습니다.
• 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.
• 스파이는 하루에 최소 한 개의 의상은 입습니다.
• 프로그래머스에서 해쉬를 사용해 풀어야 한다고 적혀 있어서 해쉬를 사용했다.

나의 코드 - 실패

결론을 말하자면, 테스트 코드로 나온 두 개는 맞았지만 제출하기를 눌렀을 때는 실패했다.

해시를 사용한 코드

다른 고수님들의 코드가 있었지만 가장 해시 스럽게 풀었던 코드를 보고 공부를 했다.

우선 clothes_type 인 해시테이블을 만들어 주었다.

내가 알고리즘을 해결하기 위해서 각 부위 별로 리스트로 정리를 하고, 그 리스트 간의 조합의 갯수를 구하는 방향으로 하다보니 시간도 오래걸리고, 제대로 구현 되지도 않은 것 같다. 정작 필요한 것은 단순히 조합의 개수만 구하면 됬었는데

그리고 키가 없을 때 2를 추가 해주는 것도 생각지도 못한 방법이었다.

마지막에 -1을 해주는 이유는
조합이 'None' 인 경우를 제외 해야 하기 때문에 -1을 해주었다.