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

 
오늘부터 코딩테스트 벼락치기 합니다.
 

1. 설탕배달

• While - else 문으로 구현, 
  • N 이 0보다 작아질 때까지, 5로 나누거나 3으로 나누거나, 
  • 만약 N = 4 인 경우, -3 연산이 수행되어서 1 -> -2로 계산이 됨. 따라서 if N%5==0 이 수행될 수가 없고, 카운트 출력도 안됨. else 문으로 감

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

# input 값 받기
N = int(input())
count = 0


while N > 0 :
    if N%5 == 0 :
        count += N//5
        print(count)
        break

    N -= 3
    count += 1

else  :
    if N<0 :
        print(-1)

    elif N==0:
        print(count)

 

---

 

2. 이장님의 초대

• 쉬우니깐 pass

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

# 이장님의 초대

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
for i in range(len(A)) :
    A[i] = A[i] + i+1

print(max(A)+1)

 
 

---

 

3. 라디오

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

n,m = map(int, input().split())
result = abs(n-m)

for _ in range(int(input())) :
    k = int(input())
    if result > abs(k-m) :
        result  = abs(k-m) + 1


print(result)

 

---

 

4. 연결요소의 개수

• 전형적인 DFS 문제 
• Input 값을 받을 때, 인접리스트로 구현
• DFS 함수 재귀의 방법으로 구현하고, visited 리스트 업데이트
• DFS 함수가 실행되는 횟수가 연결요소의 갯수임

 
재귀함수 구현할 때, 주의해야 할 것  -> 계속해서 런타임에러(RecursionError) 나는 이유 

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

 

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline
n,m = map(int, input().split())
A = [[]for _ in range(n+1)]
visitied = [False] * (n+1)

# 리스트 만들기
for i in range(m) :
    s,e = map(int, input().split())
    A[s].append(e)
    A[e].append(s)

# DFS 함수 구현
def DFS(v) :
    visitied[v] = True
    for i in A[v] :
        if not visitied[i] :
            DFS(i)

# 연결요소 갯수 구하기
count = 0
for i in range(1,n+1) :
    if not visitied[i] :
        count += 1
        DFS(i)

print(count)

 
 

---

 

5. 신기한 소수 찾기 (⭐️복습하기)

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

# 신기한 소수
import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline
N = int(input())

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

# DFS 함수
def DFS(number) :
    if len(str(number)) == N :
        print(number)

    else :
        for i in range(1,10) :
            if i%2 == 0 :
                continue #짝수는 안됨

            if prime(number*10 + i) :
                DFS(number*10 + i)


DFS(2)
DFS(3)
DFS(5)
DFS(7)

 
 

---

 

6. 요세푸스 문제

 

• 스택 개념 이용해서 풀려니깐, 시간초과 발생함.. 할튼 시간초과 짜증나 죽겟네

N,M = map(int,input().split())
A = list()
answer = []
for i in range(N) :
    A.append(i+1)

while len(A) > 0 :
    for i in range(M-1) :
        A.append(A[0])
        del A[0]

    answer.append(A[0])
    del A[0]

answer = str(answer)
answer=answer.replace('[','<').replace(']','>')
print(answer)

 

• 따라서 매번 인덱스 M 번쨰 요소 구해서 삭제하는 방법으로 구현하기

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

index = 0
answer = []
while len(A) > 0 :
    index = ( index + m - 1 ) % len(A)
    answer.append(A.pop(index))

print(str(answer).replace('[','<').replace(']','>'))

 
 

---

 

7. 세로읽기

• input 값 다차원리스트로 받고, 인덱스 값으로 아래로 읽어 나가기
• 한 줄에 4가지 문자가 들어오는 경우 -> IndexError 발생, 그래서 인덱스 예외 처리 해줌...

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

A = list()
for i in range(5) :
    input_word = list(input())
    A.append(input_word)
answer = []


for i in range(15) :
    for j in range(5) :
        try :
            answer.append(A[j][i])
        except :
            continue

print(''.join(answer))

 
 

---

 

8.  덩치

• 자신보다 몸무게, 키 큰 사람의 수 +1 이 자신의 등수임
• 이 아이디어만 떠올리면 엄청 쉬운데,,,

n = int(input())
A = [[0 for i in range(2)] for _ in range(n)]

for i in range(n) :
    k,l = map(int, input().split())
    A[i][0] = k
    A[i][1] = l

ans = []
for i in range(n) :
    count = 0
    for j in range(n) :
        if A[i][0] < A[j][0] and A[i][1] < A[j][1] :
            count += 1

    ans.append(count+1)

ans = map(str, ans)
print(' '.join(ans))

 
 
 

---

9. 블로그

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

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

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

# 최댓값 만들기
max_list = []
for i in range(m,n+1) :
    max_list.append(S[i]-S[i-m])

max_number= max(max_list)

if max_number == 0 :
    print('SAD')
else :
    print(max_number)
    print(max_list.count(max_number))

 
 
 
오전에 한 거 삭제되서 ㅠㅠ