로봇이 아닙니다

문제

KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.

같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다.

예를 들어, 주어진 용액들의 특성값이 [-2, 4, -99, -1, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액이 특성값이 0에 가장 가까운 용액이다. 참고로, 두 종류의 알칼리성 용액만으로나 혹은 두 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.

산성 용액과 알칼리성 용액의 특성값이 주어졌을 때, 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성하시오.

입력

첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.

출력

첫째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액의 특성값을 출력한다. 출력해야 하는 두 용액은 특성값의 오름차순으로 출력한다. 특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다.

풀이

from sys import stdin 
from bisect import bisect_right, bisect_left

N = int(stdin.readline())
liq = list(map(int, stdin.readline().split()))
liq.sort() 

ans1 = 0
ans2 = 0
minMix = 2000000000

for i in range(N-1):
    tmp1 = liq[i]
    bigIdx = bisect_right(liq, abs(tmp1))
    smallIdx = bigIdx-1
    if smallIdx==i :
        smallIdx += 1
    if bigIdx>=N:
        bigIdx -=1

    tmp2 = liq[smallIdx]
    tmp3 = liq[bigIdx]

    if abs(tmp1+tmp2) < abs(tmp1+tmp3):
        mixLiq = tmp1+tmp2
    else:
        mixLiq = tmp1+tmp3 

    if abs(minMix) > abs(mixLiq):
        minMix = mixLiq 
        ans1 = tmp1  
        ans2 = minMix-tmp1
print(ans1, ans2)

• 이분탐색 활용
• 다른 풀이는 보지 않아 잘 모르겠지만 내가 사용한 해결법은 다음과 같다
  • 리스트를 정렬한 후 리스트의 개수 N 만큼 반복한다.
  • i 번째 반복문에서 용액 리스트 liq의 i 번째 요소를 가져와 그 값의 절대값을 가지고 이분탐색을 수행한다.
    • i 번째 요소의 절댓값과 차이가 가장 작은 값을 얻기 위함
  • 이분탐색하여 얻은 인덱스와 그 값에서 1을 뺀 값(bigIndex, smallIndex) 총 두 개의 인덱스 값을 얻는다.(i 번째 요소보다 작은 값과 작거나 큰 값)
    • 이 때 가장 큰 값이어서 인덱스값이 N이 나오는 경우가 있으므로 그런 경우 1을 빼주는 작업이 필요하다.
  • 두 인덱스 자리의 값과 모두 더해본 뒤 가장 작은 값을 섞인 용액의 특성값으로 취한다.
  • 혼합 용액의 특성값은 그 이전 반복문에서 저장한 값과 비교하여 더 작은 값을 취한 후 두 용액 특성값을 ans1, ans2에 저장한다.
• 투 포인터를 사용하는 문제라고는 하는데 사실 투 포인터가 뭔지 모르고 풀었다~~;; 나중에 제대로 공부하고 다시 풀어봐야지

문제

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

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

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

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

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

입력

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

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

출력

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

풀이

from sys import stdin 

while True:
    flag = 'yes'
    paren = []
    msg = stdin.readline().rstrip()
    if msg == '.':
        break 
    for i in msg :
        if i == '('or i=='[':
            paren.append(i)
        elif i==')':
            if len(paren)==0:
                flag = 'no'
                break 
            elif paren.pop() != '(':
                flag = 'no'
                break
        elif i==']':
            if len(paren)==0:
                flag = 'no'
                break 
            elif paren.pop() != '[':
                flag = 'no'
                break
    if len(paren)!= 0:
        flag = 'no'
    print(flag)

• stack 활용
• 열린 괄호인 경우 괄호를 스택에 넣고, 닫힌 괄호를 만날 때 마다 스택에서 빼내도록 한다.
• 스택이 비었는데 닫힌괄호를 만나거나, 문자열이 끝났는데도 스택에 괄호가 남아있다면 짝이 맞지 않은 것이다.
• 이 문제는 괄호의 종류가 두 개 이므로 스택에서 빼낼 때 괄호가 어떤 괄호인지도 중요하다
  • 닫힌 괄호를 만나 스택에서 pop 한 괄호가 같은 종류인 경우: 알맞게 짝지어진 괄호이다.
  • pop 한 괄호가 다른 종류인 경우 : 짝이 맞지 않은 괄호이다.

문제

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

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

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

입력

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

출력

첫째 줄에는 산술평균을 출력한다. 소수점 이하 첫째 자리에서 반올림한 값을 출력한다.

둘째 줄에는 중앙값을 출력한다.

셋째 줄에는 최빈값을 출력한다. 여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력한다.

넷째 줄에는 범위를 출력한다.

풀이

from sys import stdin 
from bisect import bisect_left, bisect_right
from statistics import mode, mean, median

def myMode(arr):
    mmode = 0
    mmode = mode(arr)
    if len(arr)==1:
        return mmode
    modeCnt = bisect_right(arr, mmode)-bisect_left(arr, mmode)
    del arr[bisect_left(arr, mmode):bisect_right(arr, mmode)]
    temp = mode(arr)
    if modeCnt == bisect_right(arr, temp)-bisect_left(arr, temp):
        mmode = temp
    return mmode 

N = int(stdin.readline())
arr = []
sum = 0
for i in range(N):
    arr.append(int(stdin.readline()))
    sum += arr[i]

arr.sort()
mmean = mean(arr)
mmedian = median(arr)
minMax = arr[-1]-arr[0]
mmode = myMode(arr)

print(int((mmean+0.5)*10//10))
print(mmedian)
print(mmode)
print(minMax)

• statistics 모듈
  • 산술평균, 중앙값, 최빈값은 모두 statistics 모듈의 mean(), median, mode()로 구할 수 있다.
• 그러나 평균의 경우 소수점에서 반올림하고 최빈값은 두번 째 값을 출력해야 한다.
  • 소수점에서 반올림 하는 연산은 평균값+0..5 *10 //10 연산으로 해결
    • print(”%.0f” %mmean) 을 사용해도 좋지만 만약 -0.3 같은 값인 경우 -0이라는 결과가 출력되므로 오답으로 처리된다.
• 최빈값의 경우 : statistics 모듈에서는 최빈값이 여러개인 경우 가장 먼저 찾은 최빈값을 출력한다.
  • 이를 이용하기 위해 리스트를 정렬해준다(문제에서는 여러개인 경우 두 번째로 작은 값을 출력해야 하므로 )
  • 정렬 한 리스트에서 mode() 할 때, 최빈값이 여러개인 경우 가장 먼저 찾은 가장 작은 값을 찾게 된다.
  • 첫 번째로 찾은 최빈값과 그 개수(bisect 모듈 활용)를 저장해 두고, 해당 최빈값들을 리스트에서 삭제한다.(del)
  • 삭제한 리스트에서 다시 mode() 사용하여 최빈값을 찾는다.
    • 두번째 최빈값 개수가 첫번째 개수와 다른 경우 첫번째로 찾은 최빈값을 선택한다.
    • 두번째로 찾은 최빈값의 갯수가 첫 번째 최빈값 개수와 같은 경우, 두번째로 찾은 최빈값을 선택한다. (최빈값이 여러개인 경우 두 번째로 작은 최빈값을 찾아야 하므로)

문제

상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다.

목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고, 상근이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다. (총 7미터를 집에 들고 간다) 절단기에 설정할 수 있는 높이는 양의 정수 또는 0이다.

상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.

출력

적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

풀이

from sys import stdin 

N, M = map(int, stdin.readline().split())
tree= list(map(int, stdin.readline().split()))

start= 0
end = max(tree)
result = 0

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


    for i in range(len(tree)):
        if tree[i] - mid >0:
            sum += tree[i]-mid
    if sum < M:
        end = mid-1
    else :
        result = mid
        start = mid+1
print(result)

• 이진 탐색 알고리즘을 사용한다.
  • 범위 내에서 중간 값을 찾은 후 타겟이 되는 값이 그보다 큰지, 또는 작은지를 확인 한다.
    • 크면 중간값 부터 최댓값 사이를 범위로 하여 중간값을 다시 찾는다.
    • 작으면 최소값 부터 중간값 사이를 범위로 하여 중간값을 다시 찾는다
• 나무를 자르는 적절한 길이를 반복해서 찾아야 하는데, 이 때 단순히 선형적으로 높이를 찾는 것 보다 이진 탐색 알고리즘으로 높이를 찾는 것이 훨씬 빠르다.
• 반복할 수록 M만큼 자를 수 있는 최대 높이와 가까워진다.