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

1. 부분합

• 문제 똑바로 읽기.. S 이상이 되는 것임 !!
• S가 아니라

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

n,m = map(int, input().split())
A = list(map(int, input().split()))
number_sum = A[0]
start_index = 0
end_index = 0
set_a = set()

while True :

    if number_sum < m :
        end_index  += 1
        if end_index == n :
            break
        number_sum += A[end_index]

    else :
        set_a.add(end_index - start_index + 1)
        number_sum -= A[start_index]
        start_index += 1



set_a = list(set_a)
set_a.sort()

if len(set_a) == 0 : print(0)
else : print(set_a[0])

 

---

2. Maximum Subarray

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

n = int(input())

for i in range(n) :

    a = int(input())
    A = list(map(int, input().split()))
    dp = [0] * a
    dp[0] = A[0]

    for i in range(1,len(A)) :
        dp[i] = max(dp[i-1] + A[i], A[i])

    print(max(dp))

 

---

3. 로또

• 조합 : from intertools import combinatinos 

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

from itertools import combinations

while True :
    input_word = list(map(int,input().split()))

    if input_word[0] == 0 :
        break

    del input_word[0]

    for combination in  combinations(input_word,6) :
        combination = sorted(combination)
        print(' '.join(map(str,combination)))

    print(" ")

 

 

---

4. 다음순열

• 시간초과
• 모르겟음,, 도통,,,

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

from itertools import permutations
import copy

n = int(input())
A = list(map(int, input().split()))
B = copy.deepcopy(A)
A.sort()
k = 0
answer = []

for i in permutations(A,n) :
    a = list(i)

    if k == 1 :
        answer = a
        break

    if a == B :
        k = 1

if len(answer) == 0 :
    print(-1)
else :
    print(answer)

 

---

5.  케빈 베이컨의 6단계

참 어렵다...

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

# 케빈 베이컨의 6단계 법칙
# 유저의 수(N), 친구 관계의 수 (M)
# 그 다음부터 친구 관계 수가 들어옴

from collections import deque

# bfs 구현
def bfs(start_index, A):
    visited = [False] * (n+1) #방문리스트 만들기
    visited[start_index] = True
    q = deque([(start_index,0)]) #시작유저와 케빈 베이컨 수를 큐에 넣음

    while q : #큐가 빌때까지 반복
        node, kevin_bacon = q.popleft() #큐에서 요소 꺼내고 -> 해당 유저와, 그의 케빈 베이컨 수 가져오기
        for neighbor in A[node] : # 친구관계 한명씩 가져와서
            if not visited[neighbor] : # 방문한적이 없는 경우에만
                visited[neighbor] = True
                q.append((neighbor, kevin_bacon+1))
                bacon[neighbor] += kevin_bacon + 1 # 현재 유저를 거쳐 이웃 유저



# input 값 받기
n,m = map(int, input().split())
A = [[] for _ in range (n+1) ]
bacon = [0] * (n+1) #각 유저의 케빈 베이커 수 저장

# 인접리스트 받기
for i in range(m) :
    a,b = map(int, input().split())
    A[a].append(b)
    A[b].append(a)

for i in range(1,n+1) :
    bfs(i,A)


my_kevin_bacon = min(bacon[1:])
print(bacon.index(my_kevin_bacon))

 

 

---

[ 공부 ] 순열, 조합, 중복순열, 중복조합

• 순열 : from itertools import permutations
• 조합 : from itertools import combinations
• 중복순열 : from itertools import product
• 중복조합 : from itertools import combinations_with_replacement

# 순열, 조합, 중복순열, 중복조합
import itertools

# 1. 순열 (permutation)
from itertools import permutations
sets = [1,2,3]
data = itertools.permutations(sets,2)
for i in data :
    print(i)

# (1, 2)
# (1, 3)
# (2, 1)
# (2, 3)
# (3, 1)
# (3, 2)


# 2. 조합 (combination)
from itertools import combinations
sets = ['A','B','C']
data = itertools.combinations(sets,2)
for i in data :
    print(i)

# ('A', 'B')
# ('A', 'C')
# ('B', 'C')


# 3. 중복순열 (permutation with repetition)
# 순열과는 다르게 같은 숫자를 중복해서 사용할 수 있음
from itertools import product
sets = [1,2,3]

# 2개를 뽑아 일렬로 나열하는 경우의 수 (단, 중복허용함)
data = itertools.product(sets, repeat = 2)
for i in data :
    print(i)

# (1, 1)
# (1, 2)
# (1, 3)
# (2, 1)
# (2, 2)
# (2, 3)
# (3, 1)
# (3, 2)
# (3, 3)


# 4. 중복조합 (combination with repetition)
from itertools import combinations_with_replacement
sets = ['A','B','C']
data = itertools.combinations_with_replacement(sets,2)
for i in data :
    print(i)

# ('A', 'A')
# ('A', 'B')
# ('A', 'C')
# ('B', 'B')
# ('B', 'C')
# ('C', 'C')

 

---

6. 더 맵게

• 문제를 잘 읽어야 한다. 만약 만들 수 없다면 .. -1 을 return 해줘야 함

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

프로그래머스

import heapq
def solution(scoville, K):

    heapq.heapify(scoville)
    min_number = heapq.heappop(scoville)
    count  = 0

    while min_number < K :

        if len(scoville) < 1 :
            return -1

        second_number = heapq.heappop(scoville)
        heapq.heappush(scoville, min_number + (second_number*2))
        min_number = heapq.heappop(scoville)
        count += 1

    heapq.heappush(scoville, min_number)
    return count

---

7. 모음사전

• 단어가 5개밖에 안돼서 중복순열로 구현
• from itertools import product
• 만들 수 있는 문자열을 다 append 해놓고 -> sort 해주기
• input 값의 index 찾아서 index + 1을 리턴해주기

 

• dfs 로 풀 수 있을 것 같긴한데... 인터넷봐도 해석 불가능 ~ ! ! 

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

프로그래머스

from itertools import product

def solution(word):
    word_list = ['A','E','I','O','U']
    answer_list = []

    for i in range(1,6) :
        for j in product( word_list, repeat = i ):
            a = list(j)
            answer_list.append(''.join(a))

    answer_list.sort()

    return answer_list.index(word) + 1




print(solution('AAAE'))

 

---

8. 3차 압축

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

프로그래머스

def solution(msg):
    word = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N',
            'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']
    mag = list(msg)
    start = 0
    end = 1
    answer = []

    while end < len(msg) + 1 :
        S = msg[start:end]

        if S in word :
            end += 1
        else :
            index_number = word.index(S[:-1]) + 1
            answer.append(index_number)
            word.append(S)
            start = end - 1

    # 마지막 담기
    last_index_number = word.index(S) + 1
    answer.append(last_index_number)

    return answer

---

9. 가장 큰 수

• 할튼 내 힘으로 하는게 없어 .. 

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

프로그래머스

• 마지막 테스트 케이스가 통과가 안됨 (9534303 > 9534330) 이 더 크기 때문,,,, 

def solution(numbers):
    number_list = []
    answer = ''

    for i in range(len(numbers)) :
        count_i = len(str(numbers[i]))
        number_list.append([str(numbers[i]) + '0'* (5-count_i),i])

    number_list.sort(reverse=True)

    for i in range(len(numbers)) :
        index_number = number_list[i][1]
        answer = answer + str(numbers[index_number])

    return answer

• numbers의 원소는 1000 이하라는 점을 이용
  • 정렬기준을 문자 원소값에 *3 해준 값으로 내림차순 정렬시켜주기

def solution(numbers):
    answer = ''

    numbers = list(map(str,numbers)) #문자로 바꿔주고
    numbers.sort(key = lambda x : x*3, reverse = True)  #3번씩 반복하면 붙였을 때 큰 수 찾기

    for i in numbers :
        answer += i

    return str(int(answer))

 

---

10. 센티와 마법의 뿅망치

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

• 왜 틀렸는지 진짜 모르겠음 ㅠㅠ 

# 센티와 마법의 뽕망치
import heapq
a,b,c = map(int, input().split())
A = list()
count = 0
TF = True

for i in range(a) :
    input_number = int(input())
    heapq.heappush(A, -input_number)

for i in range(c) :

    max_number = heapq.heappop(A)
    if max_number != -1 :
        max_number = -max_number  // 2
    heapq.heappush(A, -max_number)
    count += 1

    max_number = heapq.heappop(A)
    if max_number > -b :
        print("YES")
        print(count)
        TF = False
        break
    heapq.heappush(A, max_number)

if TF :
    print("NO")
    print(-int(A[0]))

import heapq
a,b,c = map(int, input().split())
A = list()
count = 0

for i in range(a) :
    input_number = int(input())
    heapq.heappush(A, -input_number)

for i in range(c) :
    max_number = heapq.heappop(A)
    if max_number == -1 or -max_number < b:
        heapq.heappush(A, max_number)
        break

    else :
        heapq.heappush(A, -(-max_number // 2))
        count+=1

if -A[0]>=b :
    print("NO")
    print(-A[0])
else :
    print('YES')
    print(count)