항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬하는 효율적인 알고리즘
A : 7 2 5 3 4 5 3 5
0~9 숫자가 각각 몇 개씩 있는가?
cnt = [0] * 10
for x in A:
cnt[x] += 1
제한 사항
정수나 정수로 표현할 수 있는 자료에 대해서만 적용 가능
각 항목의 발생 횟수를 기록하기 위해, 정수 항목으로 인덱스되는 카운트들의 배열을 사용하기 때문
시간복잡도
O(n + k): n은 리스트 길이, k는 정수의 최대값
[0, 4, 1, 3, 1, 2, 4, 1]을 카운팅 정렬하는 과정
서로 다른 것 중 몇 개를 뽑아서 한 줄로 나열하는 것
{1, 2, 3}을 포함하는 모든 순열을 생성하는 함수
동일한 숫자가 포함되지 앗아쓸 때, 각 자리 수 별로 루프문을 이용해 구현
해 선택 > 실행 가능성 검사 > 해 검사
연속적으로 1 이상인 애가 나타나면 run, 한자리가 3 이상이면 triplet
run 먼저 조사하면 안되는 경우가 있다
따라서 triplet 을 먼저 검사 후 데이터 완전 삭제
*인덱스 구분하는 것보다 두 칸 더 만들어놓고 쓰는게 좋다 (run과 triplet 검사할 때를 위한 여분의 칸)
*붙어서 들어온 숫자 입력받는 방법
for i in range(6):
c[num % 10] += 1 # 일의 자리 알아내기
num //= 10 # 일의 자리 날리기
i = 0
tri = run = 0
while i < 10:
if c[i] >= 3: # triplete 조사 후 데이터 삭제
c[i] -= 1
tri += 1
continue; # i 증가 없이 반복문 건너뜀
if c[i] >= 1 and c[i+1] >= 1 and c[i+2] >= 1: # run 조사 후 데이터 삭제
c[i] -= 1
c[i + 1] -= 1
c[i + 2] -= 1
run += 1
continue
i += 1
if run + tri == 2 : print('Baby Gin')
else: print('Lose')
*그자리 다시 조사하는 경우 만약 123123이면 다시 조사해야 run을 두 번 이상 알아낼 수 있다
contiue로 뒷부분 건너뛰어서 증가시키는 작업 안함