[Python] Section2. 코드 구현력 기르기

인프런의 파이썬 알고리즘 문제풀이 강의를 공부합니다

1. K번째 약수

#1. 두개의 값을 입력 N, K
n, k= map(int, input().split())
#2. 입력받은 값만큼 돌려서 나눠 약수를 구한다
cnt =0
for i in range(1, n+1): #약수는 1부터 존재 
    if n%i==0: # 나머지가 0이면 약수
        cnt += 1
    if cnt == k:
        print(i)
        break
else: #정상적으로 끝날경우
     print(-1)

• 두개의 값을 나란히 입력받을 때 n, k= map(int, input().split())
• 범위 for i in range(1, n+1):
• 약수 구하기 if n%i==0:
  약수는 1부터 존재함으로 범위는 1부터 인덱스값을 포함하기위해 +1을 한다

2. K번째 수

# 1. 테스트 케이스 입력받 T
# 2. 테스트 케이스만큼 돌리면서 n, s, e, k 입력받기
# 3. n개만큼의 리스트 입력받기

T = int(input()) #입력받으면 문자열이기 때문에 int변환
for t in range(T): #케이스별로 입력받기
    n, s, e, k = map(int, input().split())
    a= list(map(int, input().split()))
    a=a[s-1:e] # s~e번째 = [s-1:e]idx
    a.sort() #오름차순 정렬
    print("#%d %d" %(t+1, a[k-1])) # k번째 = [k-1]idx

• 리스트 입력받기 map(int, input().split())
• 항상 n번째는 idx로 n-1
  s~e 번째 = [s-1:e] Index
• 오름차순 정렬 a.sort()

3. K번째 큰 수

# n, k 입력받기 
# n개만큼 카드값 입력받기
# 3개를 뽑을 경우 + 중복 제거(set())

n, k = map(int, input().split())
a = list(map(int, input().split()))
res=set()
for i in range(n):
    for j in range(i+1, n):
        for m in range(j+1, n):
            res.add(a[i] + a[j] + a[m]) # 중복을 제거하면서 res =set() 자료구조에 저장
res=list(res) #set()은 sort()가 불가능하여 list로 변경후 세우기
res.sort(reverse=True) #내림차순은 reverse
print(res[k-1])

• 3개를 뽑아서 중복을 제거하는 방법
  • 중첩 for문 사용하기
  • set()
    • 리스트 자료형을 set(리스트)를 통해서 set 타입으로 변경하면서 중복을 제거합니다.
      그 후에list(set(리스트)) 다시 리스트로 감싸주어서 리스트 타입으로 데이터를 변경
• 내림차순 res.sort(reverse=True)
• 오름차순 sort(default = false)

[ + ] 최솟값 구하기

# 최솟값 구하기1
arr = [5,3,7,9,2,5,2,6]
arrMin = float('inf') #파이썬의 무한대값으로 넣어 초기값이 들어오도록 한다
for i in range(len(arr)):
    if arr[i]<arrMin:
        arrMin=arr[i]
print(arrMin)

# 최솟값 구하기2
arrMin2 = float('inf') 
for i in range(len(arr)):
    if arr[i]<= arrMin2: #만약 같다 <= 를 하게되면 같은 값이 올 경우 뒤의값이 선택된다 
        arrMin=arr[i]

# 최솟값 구하기3
arrMin3 = arr[0] #무한대가 아닌 idx0으로 초기화
for i in range(len(arr)):
    if arr[i]< arrMin3: 
        arrMin=arr[i]

# 최솟값 구하기4
arrMin4 = float('inf')
for x in arr: #향상된 for문
    if arr[i]< arrMin4: 
        arrMin=arr[i]

• 무한대 값 float('inf')

4. 대표값

# 입력: n명의 학생과 n명 만큼의 list받기
# 평균 구하기
# for문으로 idx=학생번호, x=성적
# tmp변수를 만들어 평균과 실제학생의 값을 구함 abs() 절댓값
# 평균거리값이 가장 작은 학생이 정답

n = int(input())
a = list(map(int, input().split()))
ave=round(sum(a)/n)
ave=ave+0.5
ave=int(ave)
min=2147000000 #최댓값을 설정해 첫째값이 들어오도록 함
for idx, x in enumerate(a): # a리스트를 탐색할때 idex, x값을 쌍으로 가져올 수 있음
     tmp=abs(x-ave) #절댓값 abs()
     if tmp<min:
        min=tmp
        score=x #성적 저장
        res=idx+1 #번째를 구하기 때문에 +1
     elif tmp == min: #같은 거리일 경우
        if x>score: #저장된 값
            score=x
            res=idx+1
print(ave, res)

• 절댓값 abs()
• idx, 값을 쌍으로 가져오기 enumerate()
  

5. 정다면체

# cnt라는 리스트에 경우의수로 나온 합의 값들을 인덱스에 저장 한다
# cnt 리스트의 인덱스 번호가 나온 합이고 같은 값이 나올때마다 count증가
# 확률이 높다 = 인덱스 번호에 count가 높은것 

n, m =map(int, input().split())
cnt=[0]*(n+m+3) #정다면체 두개의 합 이상의 값이 나올리가 없음
max=-214700000 #max는 가장 작은값으로 초기화

for i in range(1, n+1): #n번째 까지 임으로 n+1
    for j in range(1, m+1): #주사위는 중복이 나올 수 있고 카운트 해야함
        cnt[i+j]+=1 #주사위 눈의 합 == idx
for i in range(n+m+1): #두 눈의 합이 최대 idx이며 ~까지라 +1
    if cnt[i]>max: #cnt[i = 합]이고 이것의 값이 확률, 값인 확률을 비교하여 max에 저장
        max=cnt[i] 
for i in range(n+m+1):
    if cnt[i]==max: #i가 출력되도록 해야함  
        print(i, end=' ')

• 줄바꿈 없이 일자로 출력: end=' '
  

6. 자릿수의 합

• 숫자로 해결

n = int(input())
a = list(map(int, input().split()))

def digit_sum(x): #함수를 만들때는 def
    sum=0
    while x>0:
        sum += x%10 #(%)나머지 일의 자리를 sum에 합하기
        x = x//10 #(//)몫을 다시 저장
    return sum

max=-2147000000
for x in a:
    tot=digit_sum(x) #sum을 리턴받는다 tot에 저장
    if tot>max:
        max=tot #합의 값이 큰게 max에 저장
        res=x
print(res)

• 문자열로 해결

n = int(input())
a = list(map(int, input().split()))

def digit_sum(x): #함수를 만들때는 def
    sum=0
    for i in str(x): #str()문자열화 - 문자 하나하나를 접근하게 됨
        sum+=int(i)
    return sum

max=-2147000000
for x in a:
    tot=digit_sum(x) #sum을 리턴받는다 tot에 저장
    if tot>max:
        max=tot #합의 값이 큰게 max에 저장
        res=x
print(res)

• 함수 정의 def()
• 나머지 %
• 몫 //

7. 에라토스테네스 체

# 배열을 0으로 초기화하여 idx를 소수라고 생각한다
# 소수는 1이 아님으로 for는 i= 2~n까지 돈다 
# cnt 소수를 카운트
# 나온 소수값은 배수를 체크해줌(약수는 1과 자기자신만 가능) => 1로 체크되면 소수가 아니다 즉 0이 소수
n = int(input())
ch = [0]*(n+1) 
cnt=0

for i in range(2, n+1):
    if ch[i]==0: #0으로 체크 되면(소수)
        cnt+=1 #cnt+=1증가
        for j in range(i, n+1, i): #(start, end, step-숫자의 간격*배수)
            ch[j]=1
print(cnt)

• 배수들을 다 제거 range(start, stop, step)

8. 뒤집은 소수

#뒤집는 함수
def reverse(x): 
    res=0 #초기화
    while x>0: 
        t= x%10 #x의 일의자리를 t로 변경
        res= res*10+t
        x=x//10 #10으로 나눈 몫
    return res 

#소수판별 함수
def isPrime(x):
    if x==1:
        return False
    for i in range(2, x//2+1):
        if x%i==0:
            return False
    else:
        return True

n = int(input())
a =list(map(int, input().split()))
for x in a:
    tmp = reverse(x) #뒤집어진 수를 tmp에 저장
    if isPrime(tmp):
        print(tmp, end=' ')

9. 주사위 게임

n = int(input())
res=0

for i in range(n):
    tmp = input().split() #한줄씩 띄어서 입력된다 
    tmp.sort() #오름차순 정렬
    a, b, c =map(int, tmp) #문자열을 숫자화로 변경
    
    if a==b and b==c: #가장 좋은것을 먼저 넣어야 한다(전체가 충족되는것)
        money= 10000+a*1000
    elif a==b or a==c:
        money= 1000+(a*100)
    elif b==c:
        money= 1000+(b*100)
    else:
        money= c*100
    if money>res:
        res=money
print(res)

• elif는 참이되면 밑으로 내려가지 않기 때문에 모두 충족이 필요한것 (좋은 조건은 가장 위로 설정)

10. 점수계산

n = int(input())
a = list(map(int, input().split()))
sum=0
cnt=0

for x in a:
    if x==1:
        cnt+=1
        sum+=cnt
    else:
        cnt=0