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

1. 연속합2 (⭐️ 복습하기)

• 점화식의 정의  : 0에서 N까지의 길이에서 N을 포함하며 연속으로 수를 선택하여 구할 수 있는 최대 합
• 1개의 수를 살제할 수 있음 : 왼쪽 방향에서부터 인덱스를 포함한 최대 연속 합 구하기, 오른쪽 방향에서부터 인덱스를 포함한 최대 연속 합 구하기
• L[N-1] + R[N+] :  N을 1개 제거한 최대값을 구하는 것과 똑같음
• STEP 1. 주어진 수열을 저장하기

0	1	2	3	4	5	6	7	8
10	-4	3	1	5	6	-35	12	21

 

• STEP 2. 점화식을 이용해 왼쪽, 오른쪽 방향과 관련된 인덱스를 포함한 최대 연속 합 배열 채우기
  • L[N] : 왼쪽에서부터 N을 포함한 최대 연속 합
  • R[N] : 오른쪽에서부터 N을 포한한 최대 연속 합
  • L[i] = Math.max(A[i], L[i-1]+A[i])
  • R[i] = Math.max(A[i],R[i-1]+A[i])
• L테이블 vs R테이블

[ L 테이블 ] 

0	1	2	3	4	5	6	7	8	9
10	6	9	10	15	21	-14	12	33	32

 

[ R 테이블 ]

0	1	2	3	4	5	6	7	8	9
21	11	15	12	11	6	-2	33	21	-1

 

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

N = int(input())
A = list(map(int, input().split()))

# 오른쪽 index을 포함한 최대 연속 합 구하기
L = [0] * N
L[0] = A[0]
result = L[0]

for i in range(1,N) :
    L[i] = max(A[i], L[i-1]+A[i])
    result = max(result, L[i])  # L리스트의 최댓값을 정답 변수에 저장

# 왼쪽 index을 기준으로 최대 연속 합 구하기
R = [0] * N
R[N-1] = A[N-1]

for i in range(N-2,-1,-1) :
    R[i] = max(A[i], R[i+1]+A[i])

# L[i-1] + R[i+1] 2개의 구간 합 리스트를 더하면 i번째 값을 제거한 효과를 얻음
for i in range(1,N-1):
    temp = L[i-1] + R[i+1]
    result = max(result,temp)

print(result)

 

 

---

2. 연속합

• 위의 문제에서 왼쪽 리스트만 구현해주면 되는 문제

N = int(input())
A = list(map(int, input().split(" ")))

# 합 배열 만들기
S = [0] * (N)
S[0] = A[0]
result = A[0]

for i in range(1,N) :
    S[i] = max(A[i], S[i-1]+A[i])
    result = max(result, S[i])

print(result)

 

 

---

3. 포도주 시식

• DP 점화식 3가지 조건
  • D[i-1] 
  • D[i-3] + A[i-1] + A[i]
  • D[i-2] + A[i]

N = int(input())
A = [0] * N
for i in range(N) :
    a = int(input())
    A[i] = a


D = [0] * N
D[0] = A[0]
if N>1 : #인덱스에러
    D[1] = A[0] + A[1]
if N>2 :
    D[2] = max(A[2]+A[1],A[2]+A[0],D[1])
for i in range(3,N) :
    D[i] = max(D[i-1], D[i-3]+A[i-1]+A[i], D[i-2]+A[i])

print(D[N-1])

 

 

---

4. 오르막수

• 점화식 아이디어 ! -> 규칙성 발견하고, 어떻게 dp 테이블로 만들 수 있는지 !!

n = int(input())

# 점화식 생성 및 초기화
D = [[0 for i in range(10)]for _ in range(n+1)]
for i in range(10) :
    D[0][i] = 1
for i in range(1,n+1) :
    for j in range(0,10) :
        D[i][j] = sum(D[i-1][j:]) 
        
result = (sum(D[i-1]))%10007
print(result)

 

---

5.  제곱수의 합

• 원래는 아래 방식으로 풀었는데, 통과가 안된다 ㅜ 
• Testcase는 통과하는데 내가 무엇을 잘못한지 모르겠다 ㅜㅜ

import math
n= int(input())
A = [] # 제곱 리스트
for i in range(int(math.sqrt(n))+1) :
    A.append(i*i)

A.sort(reverse=True)
count = 0
while n>0 :
    for i in range(len(A)-1) :
        if n >= A[i] :
            count += n//A[i]
            n = n%A[i]

        if n == 0 :
            break

print(count)

 

• dp을 이용해서 풀기...

	0	1	2	3	4	5	6	7	8	9	10	11
1^2	0	1	2	3	4	5	6	7	8	9	10	11
2^2	0	1	2	3	1	2	3	4	2	3	4	5
3^2	0	1	2	3	4	2	3	4	2	1	2	3

 

• 점화식 도출
  • dp[i][j] = min(dp[i-1][j], if j-i*i >= 0 -> dp[i][j-i*i] + 1

N = int(input())
M = int(N**0.5) # N의 제곱근 (int변환)
dp = [n for n in range(N+1)]

for i in range(2,M+1) :
    for j in range(1,N+1) :
        if j-i*i >= 0 :
            dp[j] = min(dp[j], dp[j-i*i]+1)

print(dp[N])

 

 

• 근데 시간초과,, 진짜 못해먹겟네 ,,

---

6. 서로 다른 부분 문자열의 개수 (⭐️복습하기)

import sys
input = sys.stdin.readline().strip()
a = len(input)

answer = set()
for i in range(a) :
    substr = ''
    for j in range(i,a):
        substr += input[j]
        print(substr)
        answer.add(substr)


print(len(answer))

 

---

7.  숫자카드 2

 

1)  for 문 돌면서 count 함수 사용하기 : 시간초과

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

m = int(input())
B = list(map(int, input().split()))
answer = []

for i in range(m) :
    count = A.count(B[i])
    print(count, end = ' ')

 

 

2) 이진탐색 : 시간초과 

def binary_search(cards, target) :
    start_index = 0
    end_index = len(cards) - 1
    count = 0

    while start_index <= end_index :
        mid = (start_index + end_index) // 2
        if cards[mid] == target :
            count += 1
            # 중복돤 숫자가 있을 수 있음, 왼쪽 & 오른쪽으로 확장하여 같은 숫자 찾기
            temp_left, temp_right = mid-1, mid+1
            while temp_left >= 0 and cards[temp_left] == target :
                count += 1
                temp_left -= 1

            while temp_right < len(cards) and cards[temp_right] == target :
                count += 1
                temp_right += 1
            return count

        elif cards[mid] < target :
            start_index = mid + 1

        else :
            end_index = mid-1

    return count

# 입력받기
n = int(input())
cards = list(map(int, input().split()))
m = int(input())
targets = list(map(int, input().split()))

# 이진탐색을 위한 정렬
cards.sort()

result = []
for target in targets :
    result.append(binary_search(cards,target))

print(' '.join(map(str,result)))

 

3) Counter 사용해서 dict 이용 : 통과 ! 

from collections import Counter

# 입력받기
n = int(input())
cards = list(map(int, input().split()))
m = int(input())
targets = list(map(int, input().split()))

dict_cards = Counter(cards)
answer = list()

for target in targets :
    answer.append(dict_cards[target])

print(' '.join(map(str, answer)))

 

 

---

8.  베스트 셀러

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

from collections import Counter
n = int(input())
answer = list()

for i in range(n) :
    answer.append(input())

dict_count = Counter(answer)
max_count = max(dict_count.values())

best_sellers = sorted([book for book,count in dict_count.items()
                       if count == max_count])

print(best_sellers[0])

 

---

9.  카드

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

from collections import deque

n = int(input())
A = list()

for i in range(n) :
    A.append(i+1)
myque = deque(A)

while len(myque) >= 2 :
    print(myque.popleft())
    number= myque.popleft()
    myque.append(number)

print(myque[0])

 

---

10. 카드 합체놀이

# 카드 합체놀이
n,m = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

for i in range(m) :
    min_number_1 = A[0]
    min_number_2 = A[1]
    sum_number = min_number_1 + min_number_2
    A[0], A[1] = sum_number, sum_number
    A.sort()

print(sum(A))

 

---

11.  영단어 암기는 괴로워

 

1) 반복문으로 풀기 : 시간초과

진짜 시간초과 너무 괴롭다 !!! 

# 카드 합체놀이
import sys
input = sys.stdin.readline
n,m = map(int, input().split())
A = list()

for i in range(n) :
    input_word = input()
    if len(input_word) >= m :
        A.append(input_word)

k = list(set(A))
B = [[0 for i in range(3)] for j in range(len(k))]
for i in range(len(k)) :
    B[i][0] = -A.count(k[i])
    B[i][1] = -len(k[i])
    B[i][2] = k[i]

B.sort()

for i in range(len(k)) :
    print(B[i][2])

 

---

12. 괄호 회전하기

https://school.programmers.co.kr/learn/courses/30/lessons/76502

프로그래머스

# 괄호 확인 함수

def check_input(s) :
    count = 0
    for i in range(len(s)) :
        word = list(s[i:] + s[:i])
        stack = []
        for i in range(len(word)) :
            if len(stack) == 0 :
                stack.append(word[0])
                del word[0]
            else :
                if (stack[-1] == '[' and word[0] == ']') or (stack[-1] == '(' and word[0] == ')')or (stack[-1] == '{' and word[0] == '}') :
                    stack.pop()
                    del word[0]
                else :
                    stack.append(word[0])
                    del word[0]
        if len(stack) == 0 :
            count +=1


    return count

 

---

13. 2 x n 스타일링

https://school.programmers.co.kr/learn/courses/30/lessons/12900

프로그래머스

def solution(n) :
    D = [0] * (n+1)

    D[1] = 1

    if n>=2 :
        D[2] = 2

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

    return D[-1]

 

---