프로그래머스 181916번 문제인 "주사위 게임 3" Lv.0을 파이썬으로 풀어보도록 하겠습니다.
[프로그래머스] 주사위 게임 3 Lv.0 - [파이썬/python]
💻 문제 설명
1부터 6까지 숫자가 적힌 주사위가 네 개 있습니다. 네 주사위를 굴렸을 때 나온 숫자에 따라 다음과 같은 점수를 얻습니다.
- 네 주사위에서 나온 숫자가 모두 p로 같다면 1111 × p점을 얻습니다.
- 세 주사위에서 나온 숫자가 p로 같고 나머지 다른 주사위에서 나온 숫자가 q(p ≠ q)라면 (10 × p + q)2 점을 얻습니다.
- 주사위가 두 개씩 같은 값이 나오고, 나온 숫자를 각각 p, q(p ≠ q)라고 한다면 (p + q) × |p - q|점을 얻습니다.
- 어느 두 주사위에서 나온 숫자가 p로 같고 나머지 두 주사위에서 나온 숫자가 각각 p와 다른 q, r(q ≠ r)이라면 q × r점을 얻습니다.
- 네 주사위에 적힌 숫자가 모두 다르다면 나온 숫자 중 가장 작은 숫자 만큼의 점수를 얻습니다.
네 주사위를 굴렸을 때 나온 숫자가 정수 매개변수 a, b, c, d로 주어질 때, 얻는 점수를 반환(return) 하는 solution 함수를 작성해 주세요.
🚨 제한사항
a,b,c,d는 1 이상 6 이하의 정수입니다.
!!!정답 주의!!!
🌟 소스 코드
⏱ 시간복잡도
위 코드의 시간 복잡도는 O(n log n)입니다.
- 리스트 생성 및 딕셔너리 초기화: dice = [a, b, c, d]와 abcd = dict()
주사위의 숫자들을 리스트에 저장하고 딕셔너리를 초기화하는 데 O(1)의 시간이 소요됩니다.
- 딕셔너리 생성: for num in dice
주사위의 숫자들을 하나씩 확인하면서 해당 숫자가 딕셔너리에 없다면 새로 추가하고, 있다면 등장 횟수를 1 증가시키는 데 O(n)의 시간이 소요됩니다.
- 딕셔너리 정렬: abcd = sorted(abcd, key=lambda x:abcd[x])
딕셔너리의 키를 등장 횟수에 따라 정렬하는 데 O(n log n)의 시간이 소요됩니다.
- 리스트 개수 구하기: dice.count(abcd[0])
리스트에서 특정 요소의 개수를 세는 데 O(n)의 시간이 소요됩니다.
- 최솟값 계산: min(dice)
리스트에서 최소값을 찾는 데 O(n)의 시간이 소요됩니다.
따라서, 이 코드의 전체 시간 복잡도는 가장 큰 항인 O(n log n)이 됩니다. 이는 입력 크기에 따라 실행 시간이 로그 선형으로 증가함을 의미합니다. 이는 딕셔너리의 키를 등장 횟수에 따라 정렬하는 과정 때문에 발생합니다. 이 과정은 입력 크기 n에 비례하여 로그 선형의 시간이 소요됩니다. 이 방법은 주사위의 숫자들을 한 번씩만 확인하므로, 숫자가 많아도 효율적으로 동작합니다.
🏳🌈 테스트 결과
'코딩테스트' 카테고리의 다른 글
| [프로그래머스] 짝지어 제거하기 - Lv.2 (55) | 2023.10.27 |
|---|---|
| [프로그래머스] 이진 변환 반복하기 - Lv.2 (53) | 2023.10.26 |
| [프로그래머스] 다음 큰 숫자 - Lv.2 (59) | 2023.10.21 |
| [프로그래머스] 겹치는 선분의 길이 - Lv.0 (51) | 2023.10.15 |
| [프로그래머스] 튜플 - Lv.2 (54) | 2023.10.14 |