[240503] 코딩테스트 문제풀이

 

광기의 벼락치기임... 진짜 더 이상 인적성탈은 없다....

 

1. 팩토리얼 0의 갯수

• for문으로 팩토리얼 만들고
• 뒤에서부터 하나씩 읽어와 0의 갯수 카운트하기

https://www.acmicpc.net/problem/1676

# 팩토리얼 0의 갯수

number = int(input())
fac_number = 1

for i in range(1,number+1) :
    fac_number *= i

fac_number = list(str(fac_number))
fac_number.reverse()
count_zero = 0

for i in range(len(fac_number)) :
    if fac_number[i] != '0' :
        break
    else :
        count_zero += 1

print(count_zero)

 

 

---

2. 약수들의 합

• 약수들 구하고 -> 약수들의 합을 구해서 -> 합과 input 값이 일치하는지 판별

def number(n) :
    ans = []
    for i in range(1,n) :
        if n%i == 0:
            ans.append(i)

    return ans


while True :
    n = int(input())
    if n == -1 :
        break
    else :
        k = number(n)
        if sum(k) == n :
            k = map(str, k)
            print(n, "=", ' + '.join(k))

        else :
            print(n,'is NOT perfect.')

 

---

3. 피보나치 수

• 0처리 안해주니깐 IndexErrror 발생함

https://www.acmicpc.net/problem/10870

# 피보나치 수
n = int(input())
arr = [0]*(n+1)

if n== 0 :
    arr[0] = 0

else :
    arr[0] = 0
    arr[1] = 1

    for i in range(2,n+1) :
        arr[i] = arr[i-1]+arr[i-2]

print(arr[-1])

 

 

---

4. 달팽이는 올라가고 싶다.

https://www.acmicpc.net/problem/2869

• 반복문 돌리면 시간초과 발생함

n,m,v = map(int, input().split())
count = 1
sum_number = n
day_climb = n-m

while sum_number < v :
    count += 1
    sum_number += day_climb
print(count)

• 연산으로 해결해주기
• 올림함수 
  • import math
  • math.ceil(숫자)

import math

n,m,v = map(int, input().split())
day_climb = n-m
day_count = 1

day_count = math.ceil((v-m)/day_climb)

print(day_count)

 

---

5.  과제 안내신 분

https://www.acmicpc.net/problem/5597

ans = []
for i in range(28) :
    ans.append(int(input()))

ans.sort()

for i in range(1,31) :
    if i not in ans :
        print(i)

 

 

---

 

6. 너의 평점은

• 리스트로 구현하면 더 깔끔할텐데 

https://www.acmicpc.net/problem/25206

ans = list()
for i in range(20) :
    ans.append(input().split())

def turn_grade(n) :
    if n == "A+" : return 4.5
    elif n =='A0': return 4.0
    elif n =='B+': return 3.5
    elif n == 'B0':return 3.0
    elif n =='C+': return 2.5
    elif n =='C0': return 2.0
    elif n == 'D+':return 1.5
    elif n == 'D0':return 1.0
    else : return 0.0

sum_grade = 0
count_grade = 0

for i in range(20) :
    if ans[i][2] != 'P' :
        sum_grade += float(turn_grade(ans[i][2]))*float(ans[i][1])
        count_grade += float(ans[i][1])

print( sum_grade / count_grade)

 

---

7. 2n 타일링

• DP 이용해서 푸는 문제
  • D[i] = D[i-1] + D[i-2]

n=int(input())
D= [0] * (1001)
mod = 10007

D[1] = 1
D[2] = 2

for i in range(3,n+1) :
    D[i] = (D[i-1] + D[i-2]) % mod

print(D[n])

 

 

---

8. 정수삼각형

• 점화식을 도출하는 기준은 세 가지임
  • 왼쪽 대각선이 없는 경우 (j==0) -> D[i][j] = D[i-1][j] + A[i][j]
  • 오른쪽 대각선이 없는 경우 (j==i) -> D[i][j] = D[i-1][j-1] + A[i][j]
  • 그 외 나머지 경우, D[i][j] = max(D[i-1][j], D[i-1][j-1]) + A[i][j]

https://www.acmicpc.net/problem/1932

# 정수삼각형
n = int(input())
A = list()

for i in range(n) :
    A.append(list(map(int, input().split())))

D = [[0 for i in range(n)] for _ in range(n)]
# 점화식 초기화
D[0][0] = A[0][0]

for i in range(1,n) :
    for j in range(0,i+1) :
        if j==0 :
            D[i][j] = D[i-1][j] + A[i][j]

        elif j==i :
            D[i][j] = D[i-1][j-1] + A[i][j]
        else :
            D[i][j] = max(D[i-1][j],D[i-1][j-1]) + A[i][j]

print(max(D[n-1]))

 

 

---

9.  소수

• 소수 판별 함수에서, 1 소수 아니라고 False 값 줘야하는데, 계속 안그래서 Error 떴음

https://www.acmicpc.net/problem/2581

import math
def number_tf(n) :
    for i in range(2,int(math.sqrt(n))+1) :
        if n%i == 0 :
            return False
            break
    if n == 0 or n == 1:
        return False

    return True


# input 값 받기
n = int(input())
m = int(input())
A = list()
for i in range(n,m+1) :
    if number_tf(i) :
        A.append(i)

if len(A) == 0:
    print(-1)

else :
    print(sum(A))
    print(min(A))

 

---

10. 나머지 합 구하기

https://www.acmicpc.net/problem/10986

 

n,m = map(int, input().split())
A = list(map(int, input().split()))
S = [0] * len(A)
S[0] = A[0]

# 합 배열 저장
for i in range(1,n+1) :
    S[i] = (S[i-1] + A[i])


# 나머지 값 배열 저장
answer = 0
C = [0]*m
for i in range(n) :
    remainder = S[i] % m
    if remainder == 0 :
        answer += 1

    C[remainder] += 1

for i in range(m) :
    if C[i] > 1 :
        answer += (C[i] * (C[i]-1) // 2)

print(answer)

 

 

---

11. 풍선 터트리기

https://www.acmicpc.net/problem/2346

from collections import deque
n = int(input())
A = list(map(int, input().split()))
B = deque()

for i in range(n) :
    B.append((A[i],i+1))

while len(B) >= 1 :
    pop_number = B[0][0]
    print(B[0][1],end = ' ')
    B.popleft()

    if pop_number > 0 :
        for i in range(pop_number-1) :
            if len(B) == 0 :
                break
            else :
                B.append(B.popleft())

    elif pop_number < 0 :
        for i in range(abs(pop_number)) :
            if len(B) == 0 :
                break
            else : B.appendleft(B.pop())

 

---

12. 괄호 끼워넣기

https://www.acmicpc.net/status?user_id=minjucindy&problem_id=11899&from_mine=1

A = list(input())
stack = []

while len(A) > 0 :
    if len(stack) == 0 :
        stack.append(A[0])
        del A[0]

    elif stack[-1] == '(' and A[0] == ')' :
        stack.pop()
        del A[0]

    else :
        stack.append(A[0])
        del A[0]


print(len(stack))

 

 

---

13.  BFS와 DFS

• 인접리스트 만들기
• 작은 노드부터 탐색해야 하기 때문에, 인접리스트 정렬 시켜줌
• DFS 구현 : 방문한 노드를 출력하고, 방문리스트 업데이트 해줌 -> 인접리스트를 하나씩 방문하면서, 방문리스트 업데이트
• BFS 구현 : 덱을 활용해서 구현, 덱에 저장, 출력 -> 인접리스트 큐에 추가해주기 

# DFS와 BFS
from collections import deque
N,M,Start = map(int, input().split())
A = [[]for _ in range(N+1)]

for _ in range(M) :
    s,e = map(int, input().split())
    A[s].append(e)
    A[e].append(s)

for i in range(N+1) :
    A[i].sort()  #번호가 작은 노드부터 탐색해야 하기 때문에

def DFS(v) :
    print(v,end =' ')
    visited[v] = True
    for i in A[v] :
        if not visited[i] :
            DFS(i)
visited = [False] * (N+1)
DFS(Start)

def BFS(v) :
    queue = deque()
    queue.append(v)
    visited[v] = True
    while queue :
        now_Node = queue.popleft()
        print(now_Node, end = ' ')
        for i in A[now_Node] :
            if not visited[i] :
                visited[i] = True
                queue.append(i)


print()
visited = [False] * (N+1)
BFS(Start)

 

 

---

14. 촌수계산 (⭐️복습하기)

• 인접리스트 만들어서 BFS로 해결하는 문제임
• dfs 함수에서 파라미터를 2개를 받음, num 변수를 카운트해서 촌수계산을 할 수 있도록
• 만약 계산해야 하는 촌수를 만났다면 v==B -> result.append 해주기

https://www.acmicpc.net/problem/2644

n = int(input())
a,b = map(int, input().split())
m = int(input())
A = [[] for _ in range(n+1)]
visited = [False] * (n+1)
result = []


for i in range(m) :
    k,l = map(int, input().split())
    A[k].append(l)
    A[l].append(k)

# dfs 구현
def dfs(v,num) :
    num += 1
    visited[v] = True

    if v == b :
        result.append(num)

    for i in A[v] :
        if not visited[i] :
            dfs(i,num)

dfs(a,0)

if len(result) == 0:
    print(-1)
else :
    print(result[0]-1)

 

---

15. 바이러스 

• 전형적인 DFS 문제
• 마지막에 True 값이 몇 개 있는지를 -> sum 하기

n = int(input())
m = int(input())
A = [[] for _ in range(n+1)]
visited = [False] * (n+1)

for i in range(m) :
    a,b = map(int, input().split())
    A[a].append(b)
    A[b].append(a)

def dfs (v) :
    visited[v] = True
    for i in A[v] :
        if not visited[i] :
            dfs(i)


dfs(1)
print(sum(visited)-1)

 

---

16. 먹을 것인가 먹힐 것인가 (⭐️복습하기)

• 이분탐색 라이브러리 -> bisesct_left 사용하면 쉽게 풀 수 있음

https://www.acmicpc.net/problem/7795

from bisect import bisect_left

def solution(a,b,c,d) :
    count = 0
    c.sort()
    d.sort()

    for i in c :
        count += bisect_left(d,i)

    return count

n = int(input())
for i in range(n) :
    a,b = map(int,input().split())
    c = list(map(int, input().split(" ")))
    d = list(map(int, input().split(" ")))
    print(solution(a,b,c,d))

 

---

17. 합 구하기 (⭐️복습하기 - Input 부분)

• 시간초과가 발생함. 인터넷을 참고해서 해결한 방법은 input 값 받는 법
  • import sys
  • input = sys.stdin.readline
  • 출력할 때 -> sys.stdout.write(str(xx)) -> str 형태이어야 함 !!

import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int, input().split()))
S = [0] * (n)
S[0] = A[0]

# 합 배열 구하기
for i in range(1,n) :
    S[i] = S[i-1] + A[i]

S.insert(0,0)

question = int(input())
for i in range(question) :
    k,l = map(int, input().split())
    answer = S[l]-S[k-1]
    sys.stdout.write(str(answer)+'\n')