TIL 코딩공장

20240307 백준 파이썬 공부
4949번 균형잡힌 세상

1. 문제
세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.

정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.

문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.

모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.

2. 입력
각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다.

입력의 종료조건으로 맨 마지막에 온점 하나(".")가 들어온다.

3. 출력
각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다.

>>> 구상
1. '(' 와 ')'의 개수가 같고 '['와 ']'의 개수가 같아야 한다.
2. ')'로 시작되거나 '('로 끝나면 안된다.

>>>코드1. 실패

while True:
    sentence = input()
    if sentence == '.':
        break
    if sentence.count('(') != sentence.count(')') or sentence.count('[') != sentence.count(']'):
        print('no')
    else:
        if sentence.find('(') > sentence.find(')') or sentence.find('[') > sentence.find(']'):
            print('no')
        else:
            print('yes')

안되는 다른 경우가 존재했다.
만약 개수와 앞뒤가 올바르더라도
ex) [너와나의(연결]고리)
>>> 이건 균형을 이루고 있지 않다.

>>>코드 2. 스택 이용하기

while True:
    # 문장 입력받고 괄호를 검사할 스택 만들기
    sentence = input()
    stack = []
    # 문장이 '.'이면 끝내기
    if sentence == '.':
        break
    # 스택 검사
    for i in sentence:
        if i == '(' or i == '[':
            stack.append(i)
        elif i == ')':
            if len(stack) != 0 and stack[-1] == '(':
                stack.pop()
            else:
                stack.append(i)
        elif i == ']':
            if len(stack) != 0 and stack[-1] == '[':
                stack.pop()
            else:
                stack.append(i)
    #만약 스택의 길이가 0 이면 통과
    if len(stack) == 0:
        print('yes')
    else:
        print('no')

2024/03/06 백준 파이썬 공부
2108번 통계학

1. 문제
수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 
통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 
단, N은 홀수라고 가정하자.

- 산술평균 : N개의 수들의 합을 N으로 나눈 값
- 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값
- 최빈값 : N개의 수들 중 가장 많이 나타나는 값
- 범위 : N개의 수들 중 최댓값과 최솟값의 차이

N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오.

2. 입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 
그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다.

3. 출력
첫째 줄에는 산술평균을 출력한다. 소수점 이하 첫째 자리에서 반올림한 값을 출력한다.
둘째 줄에는 중앙값을 출력한다.
셋째 줄에는 최빈값을 출력한다. 여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력한다.
넷째 줄에는 범위를 출력한다.

>>>코드1 => 실패

l = []
N = int(input())
for _ in range(N):
    l.append(int(input()))
l.sort()
# 산술 평균
print(round(sum(l)/N))
# 중앙값
print(l[N//2])
# 최빈값
c = [0] * (max(l)+1)
n, p = 0, 0
for i in l:
    c[i] += 1
if c.count(max(c)) == 1:
    print(c.index(max(c)))
else:
    for i in range(len(c)):
        if p != 1 and c[i] == max(c):
            p += 1
        elif p == 1 and c[i] == max(c):
            print(i)
            break
# 범위
print(max(l)-min(l))

입력 숫자가 음수일 경우를 생각하지 않았다.

>>>코드 2 => Python3로 하면 시간초과, Pypy3로는 성공

# 숫자 입력받고 저장하기
l = []
N = int(input())
for _ in range(N):
    l.append(int(input()))
l.sort()

# 산술 평균
print(round(sum(l)/N))

# 중앙값
print(l[N//2])

# 최빈값
# 각 숫자의 개수를 저장할 딕셔너리 생성
count = {}
# 딕셔너리 수와 개수 저장
for i in l:
    if i in count:
        count[i] += 1
    else:
        count[i] = 1
# 가장 많이 나온 횟수를 freq에 저장
freq = max(count.values())
# 최빈값들만 저장할 리스트 n
n = []
for key, value in count.items():
    if value == freq:
        n.append(key)
# 만약 최빈값의 수가 1개면 그냥 출력, 아니면 2번째 것 출력
if len(n)==1:
    print(n[0])
else:
    print(sorted(n)[1])
    
# 범위
print(max(l)-min(l))

12/ 13 파이썬 공부
백준 2033번 반올림

1) 문제
정수 N이 주어져 있을 때 이 수가 10보다 크면 일의 자리에서 반올림을 하고, 
이 결과가 100보다 크면 다시 10의 자리에서 반올림을 하고, 
또 이 수가 1000보다 크면 100의 자리에서 반올림을 하고.. (이하 생략) 
이러한 연산을 한 결과를 출력하시오.

2) 입력
첫째 줄에 정수 N이 주어진다. (0 ≤ N ≤ 99,999,999)

3) 출력
첫째 줄에 위와 같은 연산을 한 결과를 출력하시오.

>>>코드1. round 함수 이용: 오답

n = int(input())
i = 1
while True:
    if n > 10 ** i:
        n = round(n, -i)
    else:
        print(n)
        break
    i += 1

>>> 문제 오류
446을 입력 했을 시에 446 -> 450 -> 500 이 아닌 400이 출력된다.

찾아보니 round() 함수에서 두 번째 인자는 음수 값을 사용할 때, 
십진수 자릿수가 아니라 10의 거듭제곱의 자릿수로 해석한다.

예를 들어, round(450, -2)는 450을 가장 가까운 10의 100의 자릿수로 반올림하려는 것이다. 
즉, 소수점 이하에서 두 자리를 반올림하여야 한다.

450을 100으로 나누면 4.5가 되고, 가장 가까운 정수는 4이다. 
따라서 round(450, -2)는 400을 반환하게 된다.

이는 round() 함수에서 두 번째 인자를 음수 값으로 사용할 때, 
해당 값의 음수에 따라 십진수 자릿수가 아닌 10의 거듭제곱의 자릿수로 반올림을 수행하기 때문이다.

>>>코드2. 직접 반올림 함수 만들기

n = int(input())
i = 1
while True:
    if n > 10**i:
        if n % (10**i) >= 5*(10**(i-1)):
            n = (n//(10**i) +1)*(10**i)
        else:
            n = (n//(10**i))*(10**i)
    else:
        print(n)
        break
    i += 1

>>>문제링크
https://www.acmicpc.net/problem/2033

12/ 12 파이썬 공부
백준 파이썬 1816번 암호 키

1) 문제
현대 사회에서 통용되고 있는 많은 종류의 암호 시스템에서는, 
매우 큰 소수의 곱으로 만들어진 수를 암호 키로 이용하는 경우가 많다. 
현실적으로 매우 큰 수를 빠른 시간 내에 소인수분해하는 것은 어려운 일이기 때문이다.

물론 실제 생활에서는 수십만 또는 수백만 자리 이상의 매우 큰 소수가 활용되지만 
그러한 소수를 구하는 것은 매우 어려운 일이므로, 우리는 좀 더 스케일이 작은 경우에 대해서만 생각해 보기로 하자. 
1,000,000=10^6보다 큰 소수이면 매우 큰 소수로 생각하는 것이다.

어떤 수 S가 주어지면, 이 수가 우리가 생각하는 스케일이 작은 경우에서 
적절한 암호 키인지 아닌지를 구하는 프로그램을 작성하시오. 
만일 S의 모든 소인수가 106보다 크다면 그 수는 적절한 암호 키이고, 그렇지 않은 경우는 적절하지 못한 암호 키가 된다.

2) 입력
첫째 줄에는 수의 개수 N ()이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 확인하고자 하는 수 S가 한 줄에 하나씩 주어진다.

3) 출력
N개의 줄에 걸쳐, 입력받은 수가 적절한 암호 키이면 YES, 아니면 NO를 순서대로 출력한다.

>>>코드

a = int(input())
for _ in range(a):
    n = int(input())
    t = 0
    for i in range(2, 1000001):
        m = n % i
        if m == 0:
            t = 1
            break
    if t == 0:
        print('YES')
    else:
        print('NO')

>>>코드 설명
10^6 보다 작은 소인수가 존재한다면 적절하지 못한 암호키다.
따라서 해당 수를 10^6까지의 수들로 나누어보고 

나누어 떨어지는 수가 하나도 없으면 YES를 아니면 NO를 출력하면 된다.

>>>문제 링크
https://www.acmicpc.net/problem/1816

12/ 11 파이썬 공부
백준 파이썬 1834번 나머지와 몫이 같은 수

1) 문제
N으로 나누었을 때 나머지와 몫이 같은 모든 자연수의 합을 구하는 프로그램을 작성하시오. 
예를 들어 N=3일 때, 나머지와 몫이 모두 같은 자연수는 4와 8 두 개가 있으므로, 그 합은 12이다.

2) 입력
첫째 줄에 2,000,000 이하의 자연수 N이 주어진다.

3) 출력
첫 줄에 구하고자 하는 수를 출력한다.

>>>코드

n =int(input())
result = 0
for i in range(1, n):
    result += (i*n + i)
print(result)

>>>코드 설명
나머지와 몫이 같은 경우는 n-1의 경우만 존재한다. 왜냐하면, 나머지가 n보다 같거나 클 수 없기 때문.
따라서 n-1만큼만 반복해서 더하면 된다.

>>>문제링크
https://www.acmicpc.net/problem/1834

12/ 10 파이썬 공부
백준 1356번 유진수

1) 문제
유진수는 어떤 수를 10진수로 표현한 뒤 그 수를 두 부분으로 나눴을 때, 
앞부분 자리수의 곱과 뒷부분 자리수의 곱이 같을 때를 말한다.

예를 들어, 1221은 유진수이다. 
12와 21로 나눴을 때, 앞부분 자리수의 곱 1*2는 뒷부분 자리수의 곱 2*1과 같기 때문이다. 
1236도 마찬가지로 유진수이다. 하지만, 1234는 아니다. 
수를 나눌 때 항상 연속된 자리수를 나눠야하고, 각 부분에 적어도 한자리는 있어야 한다.

예를 들어, 12345는 총 4가지 방법으로 나눌 수 있다. 
1-2345, 12-345, 123-45, 1234-5 어떤 수 N이 주어질 때, 
이 수가 유진수인지 아닌지 구하는 프로그램을 작성하시오.

2) 입력
첫째 줄에 수 N이 주어진다. 이 수는 2,147,483,647보다 작거나 같은 자연수이다.

3) 출력
첫째 줄에 N이 유진수이면 YES, 아니면 NO를 출력한다.

>>> 코드

n = list(input())
t = 0
for i in range(len(n)):
    front, back = 1, 1
    for j in range(i+1):
        front = front * int(n[j])
    for k in range(i+1,len(n)):
        back = back * int(n[k])
    if front == back:
        t = 1
        break
if t == 1 and len(n) != 1:
    print('YES')
else:
    print('NO')

- 숫자를 리스트로 입력받아 하나하나 슬라이싱하고, 처음부터 끝까지 구간을 나누어 곱해본다.

>>> 문제 링크
https://www.acmicpc.net/problem/1356

11/ 28 파이썬 공부
백준 1654번 랜선 자르기

1) 문제
집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 
박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.

이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 
박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 
예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. 
(이미 자른 랜선은 붙일 수 없다.)

편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 
기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 
그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. 
N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 
이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.

2) 입력
첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. 
K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 
그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 
랜선의 길이는 231-1보다 작거나 같은 자연수이다.

3) 출력
첫째 줄에 N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.

>>>코드

import sys
k, n = map(int, sys.stdin.readline().split())
line = []
for _ in range(k):
    line.append(int(sys.stdin.readline()))
def binary_search(start, end, target):
    while start <= end:
        t = 0
        mid = (start+end) // 2
        for i in range(k):
            t += line[i] // mid
        if t >= target:
            start = mid+1
        elif t < target:
            end = mid-1
    return end
print(binary_search(1, max(line), n))

>>>코드 설명
- 이진탐색(binary search)를 변형시킨 문제이다

- 조건에 맞는 숫자중에 가장 큰 수를 반환 시켜야하므로 end를 출력해야됨

- 나누는 과정이 포함되므로 기존의 이진탐색과 반대로 t(랜선의 개수)가 n(목표 개수) 보다 클 때, start가 커져야된다.
그래야 나눠지는 수가 커져 t가 작아진다.

>>>문제 링크
https://www.acmicpc.net/problem/1654

11/ 27 파이썬 공부
1. 백준 10816번 숫자 카드 2

1) 문제
숫자 카드는 정수 하나가 적혀져 있는 카드이다. 
상근이는 숫자 카드 N개를 가지고 있다. 
정수 M개가 주어졌을 때, 
이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

2) 입력
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 
둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 
숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 
넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 
이 수는 공백으로 구분되어져 있다. 
이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

3) 출력 
첫째 줄에 입력으로 주어진 M개의 수에 대해서, 
각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

>>>코드1. 단순히 입력 받은 후 리스트.count() 함수를 이용하여 카드 수 세기 => 실패

import sys
n = int(input())
l1 = list(sys.stdin.readline().split())
m = int(input())
l2 = list(sys.stdin.readline().split())
for i in range(m):
    print(l1.count(l2[i]), end = ' ')

시간 초과로 틀림

>>>코드2. 딕셔너리 이용

import sys
# 숫자 카드 입력받기 및 오름차순 정렬
n = int(input())
card = sorted(list(sys.stdin.readline().split()))
# 카드 개수를 확인할 숫자 입력받기
m = int(input())
check = list(sys.stdin.readline().split())
# 각 숫자의 개수를 저장할 딕셔너리 생성
count = {}
for i in card:
    if i in count:
        count[i] += 1
    else:
        count[i] = 1
# 딕셔너리에서 개수 뽑아내서 출력
for i in range(m):
    if check[i] in count: 
        print(count[check[i]], end = ' ')
    else:
        print(0, end = ' ')

따로 딕셔너리를 만들어서 이용하면 가능하다.

>>>코드3. 이진탐색 이용

import sys
# 숫자 카드 입력받기 및 오름차순 정렬
n = int(input())
card = sorted(list(sys.stdin.readline().split()))
# 카드 개수를 확인할 숫자 입력받기
m = int(input())
check = list(sys.stdin.readline().split())
# 각 숫자의 개수를 저장할 딕셔너리 생성
count = {}
for i in card:
    if i in count:
        count[i] += 1
    else:
        count[i] = 1
# 이진탐색 함수 생성       
def binarySearch(arr, target, start, end):
    if start > end:
        return 0
    mid = (start + end) // 2
    if arr[mid] == target:
        return count.get(target)
    elif arr[mid] < target:
        return binarySearch(arr, target, mid+1, end)
    else:
        return binarySearch(arr, target, start, mid-1)
# 이진탐색 함수를 이용하여 출력
for i in check:
    print(binarySearch(card, i, 0, n-1), end=' ')

찾아보니 문제의 의도가 이거인듯 하여 이렇게도 풀어보았으나
정작 시간은 더 오래 걸린다.

>>>문제 링크
https://www.acmicpc.net/problem/10816