알고리즘; 해싱 #2, 스택, 정렬

• 2월 4일 목요일 알고리즘 스터디에서 진행한 프로그래머스 문제 풀이다.
• 브레인스토밍과 채점이 끝나고 다른사람의 코드 보기를 보면 파이써닉한 코드가 많은데 그렇게까지 해야 할 필요가 있나 싶다..

---

프로그래머스 해시 #3

코드 및 알고리즘 해설

1. 같은 카테고리로 dictionary를 만든다
2. dictionary key의 길이를 구한다 (총 카테고리의 개수)
3. n개의 카테고리중 1개만 입는 경우를 구한다 → 각 카테고리의 원소 개수를 전부 합한다.
4. 2~n개 까지는 combinations 함수를 통해 구한다 → 각 카테고리 원소 개수를 곱한다.
5. 3과 4에서 구한 경우의 수를 모두 합한다.

이렇게 할 경우 카테고리에 1개의 원소만 있는 edge case에서 통과 할 수 없었다.

정답코드 설명 (외부)

1. 각 카테고리의 원소에 공집합을 더한다 (공집합 → 옷을 입지 않는 경우)
2. 공집합 포함한 원소의 개수를 서로 곱한다 → 경우의 수
3. 곱해진 모든 경우의 수에서 옷을 하나도 입지 않는 경우 1가지를 뺀다. → 진부분집합 (부분집합의 개수 – 1)

---

프로그래머스 스택/큐 #1

코드 및 알고리즘 해설

1. 주식가격의 상태를 추적하는 것이므로 i로 피벗을 지정한다.
2. j는 원소를 지나가면서 주식가격이 떨어지는 경우 증가한 카운트를 중단하고 배열에 반환한다.

---

프로그래머스 스택/큐 #2

코드 및 알고리즘 해설

1. 프로젝트 진척도 progresses[]에서 남은 프로젝트 양을 구한다.
2. 각 원소 위치에 맞춰 작업 속도 speed[]를 반영해 남은 일수를 구해 progresses[]에 반영한다 (재활용)
3. 피벗을 start로 정하고 end로 인덱스를 밀어간다.
4. 남은 일수가 피벗보다 작은 경우 프로젝트가 반환되는 갯수를 answer에 반환한다.
5. 피벗을 end+1에 다시 반영해 인덱스를 밀어간다.

---

프로그래머스 정렬 #1

코드 및 알고리즘 해설

1. commands 원소를 각 i,j,k로 뜯어 각각 split의 시작부분, 끝부분 그리고 split된 배열에서 찾아낼 인덱스로 설정한다.
2. 인덱싱한 원소를 answer에 반환한다.

---

프로그래머스 정렬 #2

1차 시도 코드 및 알고리즘 : 삽입정렬을 사용한 풀이

1. 삽입정렬의 알고리즘을 활용하되 string으로 반환한 원소를 join하여 우위를 비교해 원소를 정렬한다.
2. 테스트 케이스는 통과하나 채점에서 시간초과로 사용 불가능

2차 시도 코드 및 알고리즘 : 순열을 사용한 풀이

1. 중복을 허용하는 조합(순열)을 사용하여 모든 원소에서 나올 수 있는 조합의 목록을 구한다
2. sort()로 내림차순하여 가장 큰 수를 반환한다.
3. 테스트 케이스는 통과하나 채점에서 시간초과로 사용 불가능

3차 시도 코드 및 알고리즘 : 거꾸로된 Radix 정렬의 풀이 (작업중)

1. 원소의 수에서 가장 앞자리 수를 가지고 카테고리를 만든다.

numbers = [9,5,94,939,30,3,300]
number_dictionary = {'9':[9,94,939], '5':[5], '3':[30,3,300]}

2. 만들어진 dictionary를 순회하며 리스트를 1의 자리부터 큰 수로 정렬한다 → 거꾸로된 Radix 정렬
3. 정렬된 원소를 string으로 join한다
4. 원소가 모두 0인 경우 조합을 시도하지 않고 0으로 반환한다. → 예외처리

---