[프로그래머스] 이모티콘 할인행사 (Lv2)

date

Jul 27, 2023

slug

programmers-emoticon-discount

author

status

Public

category

🧩 Problem Solving

tags

프로그래머스

summary

완전탐색 중복순열 구현

type

Post

thumbnail

문제 링크

문제 설명

제한사항

• 1 ≤ users의 길이 = n ≤ 100
• users의 원소는 [비율, 가격]의 형태입니다.
• users[i]는 i+1번 고객의 구매 기준을 의미합니다.
• 비율% 이상의 할인이 있는 이모티콘을 모두 구매한다는 의미입니다.
• 1 ≤ 비율 ≤ 40
• 가격이상의 돈을 이모티콘 구매에 사용한다면, 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입한다는 의미입니다.
• 100 ≤ 가격 ≤ 1,000,000
• 가격은 100의 배수입니다.

• 1 ≤ emoticons의 길이 = m ≤ 7
• emoticons[i]는 i+1번 이모티콘의 정가를 의미합니다.
• 100 ≤ emoticons의 원소 ≤ 1,000,000
• emoticons의 원소는 100의 배수입니다.
 

문제 해설

1. 아이디어

• 완전탐색

• 모든 이모티콘(m개)에 대해 10, 20, 30, 40 중복순열 만들기 => 각 이모티콘의 할인율 저장할 int[] 필요
• 10 20 10 40 10 20
• for (사용자들)
• 구독 여부, 구매액
• 구독자수, 총판매액을 갱신

• 중복순열 : 각 이모티콘에 대해서 10, 20, 30, 40 호출, 마지막 단계에서 확인

2. 시간복잡도

• 순열 만들기 O(4^m) = O(4^7)

• 각 사람에 대해 조사 O(n)= O(100)

• 각 사람마다 모든 이모티콘에 대해 조사 O(m) = 7 => O(4^7 * 100 * 7)

3. 자료구조

• 각 이모티콘의 할인율 저장 int[], 할인율 설정을 위한 enum int[]

• 정답 이모티콘 가입자수, 판매액 (static)

• 현재 이모티콘 가입자수, 판매액 (local)