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

 

1. 블로그 2

• dict. : B를 칠할 횟수와, R을 칠할 횟수를 저장함
• 처음 값을 무조건 색칠해야 함으로 +1 해주기
• 이전에 칠한 값이랑, 현재 칠한 값이랑 같다면 dict에서 업데이트를 해주지 않아도 됨
•  min(answer['B'], answer['R']) + 1 은, 두 개 중에 칠할 값이 더 적은 것을 들고 오겠다는 뜻

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

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

answer = {'B' : 0, 'R' : 0 }
answer[A[0]] += 1

for i in range(1,n) :
    if A[i-1] != A[i] :
        answer[A[i]] += 1

min_number = min(answer['B'], answer['R']) + 1

print(min_number)

 

 

---

2.  일곱난쟁이

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

from itertools import permutations

A = list()

for i in range(9) :
    A.append(int(input()))


for p in permutations(A,7) :
    if sum(p) == 100 :
        answer = list(p)
        break

answer.sort()
for i in answer :
    print(i)

 

---

3.  유레카 이론

import sys
input = sys.stdin.readline
from itertools import combinations_with_replacement
N = int(input())

for i in range(N) :
    n = int(input())

    answer = []
    for i in range(1,n) :
        answer.append((i*(i+1))//2)

    TF = False
    for i in combinations_with_replacement(answer,3) :
        if sum(i) == n :
            TF = True
            break

    if TF :
        print(1)
    else :
        print(0)

 

 

---

4. 예산

N = int(input())
need_list = list(map(int, input().split()))
avail_cost = int(input())

if sum(need_list) <= avail_cost:
    print(max(need_list))
    exit()

answer = 0
start, end = 0, avail_cost

while start <= end :
    mid = (start + end ) // 2
    tmp = 0

    for need in need_list :
        tmp += need if need < mid  else mid

    if tmp <= avail_cost :
        answer = max(answer, mid) # 기준값 
        start = mid + 1
        
    else :
        end = mid - 1
        
print(answer )

 

 

---

5. 햄버거

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

n,m = map(int, input().split())
A = list(input())
visited = [False] * (n)
count = 0

for i in range(n) :
    if A[i] == 'P' :
        min_index = i-m
        max_index = i+m
        if min_index < 0 : min_index = 0
        if max_index > n-1 : max_index = n-1
        for j in range(min_index, max_index+1) :
            if A[j] == 'H' and visited[j] == False :
                visited[j] = True
                count += 1
                break

print(count)

 

 

---

6. 주식

• 이건 뒤에서 부터 내려와서 max 값(팔아야하는 시점)을 업데이트 해주기

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

import sys
input = sys.stdin.readline

N = int(input())

for _ in range(N) :
    n = int(input())
    A = list(map(int, input().split()))
    dp = [0] * n
    max_number = A[-1]
    answer = 0

    for i in range(n-2,-1,-1) :

        if max_number < A[i] : # 팔아야되는 시점임
            max_number = A[i]

        else :
            answer += (max_number - A[i])

    print(answer)

 

---

7. 영화감독 숌

• '666' in str(number) 이렇게 해야하는데 멍청하게 str(number) in '666' 이렇게 하고 있었음 🥲

n = int(input())
number = 666
count = 0

while True :
    if '666' in str(number) :
        count += 1

    if count == n :
        print(number)
        break

    number += 1

 

---

8. 제곱수의 합

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

from itertools import combinations_with_replacement
n = int(input())
answer = list()
number = 1

while True :
    if number*number > n :
        break

    answer.append(number * number)
    number += 1

TF = True

for i in range(1,n+1) :
    if TF :
        for j in combinations_with_replacement(answer, i) :
            number_list = list(j)
            if sum(number_list) == n:
                print(len(number_list))
                TF = False
                break

 

---

9.  타노스

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

N = list(input())
zero_count = N.count('0') // 2
one_count = N.count('1') // 2
answer = []
final_answer = []

# 1 제거하기 : 앞에서부터 제거
for i in range(len(N)) :
    if N[i] == '0' :
        answer.append(N[i])
    elif N[i] == '1' and one_count <= 0 :
        answer.append(N[i])
    else :
        one_count -= 1

# 0 제거하기 : 뒤에서부터 제거
for i in range(len(answer)-1,-1,-1) :
    if answer[i] == '1' :
        final_answer.append(answer[i])
    elif answer[i] == '0' and zero_count <= 0 :
        final_answer.append(answer[i])
    else :
        zero_count -= 1

final_answer.reverse()
print(''.join(final_answer))

 

 

---

10. 빈도정렬

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

import heapq
from collections import Counter
n,m = map(int, input().split())
A = list(map(int, input().split()))
dict_A = Counter(A)

# 인덱스 저장 리스트
index_list = []
for i in list(dict_A.keys()) :
    index_list.append(A.index(i))

value_list = list(dict_A.values())
dict_list = list(dict_A.keys())

heap = []
for i in range(len(dict_A)) :
    heapq.heappush(heap, (-value_list[i],index_list[i],dict_list[i]))

answer = ''
for i in range(len(heap)) :
    a,b,c = heapq.heappop(heap)
    answer += (str(c) + ' ') * -a

print(answer)

 

---

11.  단어공부

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

from collections import Counter

A = (input())
A = A.upper()
A_count = Counter(A)
A_items = list(A_count.items())
A_items.sort(key = lambda x : x[1], reverse = True)

# value 값 만 꺼내서보기
A_values = list(A_count.values())
max_A_values = max(A_values)

if A_values.count(max_A_values ) > 1 :
    print('?')
else :
    print(A_items[0][0])

 

---

12. 올림픽

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

import heapq
n,m = map(int, input().split())
heap = []

for i in range(n) :
    a,b,c,d = map(int, input().split())
    heapq.heappush(heap, (-b,-c,-d,a))

count = 0
plus_list = []

while True :
    a,b,c,d = heapq.heappop(heap)
    plus_list.append((a,b,c))
    count += 1

    if d == m :
        minu = plus_list.count((a,b,c))
        print(count - minu + 1)
        break