Coding 공부

import math
import sys
input = sys.stdin.readline
def init(node_number,start,end):
    global segement_tree,arr
    if start == end:
        segement_tree[node_number] = arr[start]
        return segement_tree[node_number]
    else:
        mid = (start+end)//2
        segement_tree[node_number] = min(init(node_number*2, start, mid) , init(node_number*2+1, mid+1, end))
        return segement_tree[node_number]

def find_min_number(node_number,start,end,left,right):
    global segement_tree,INF
    if (left > end) or (right<start):
        return INF
    if (left <= start) and (end<=right):
        return segement_tree[node_number]
    mid = (start+end)//2
    return min(find_min_number(node_number*2,start,mid,left,right), find_min_number(node_number*2+1,mid+1,end,left,right))

N,M = map(int,input().split())
INF = float('inf')
segement_tree = [-1]*(N*4+20)
arr = [int(input()) for _ in range(N)]
init(1,0,N-1)

for _ in range(M):
    left,right = map(int,input().split())
    print(find_min_number(1,0,N-1,left-1,right-1))

2042 구간 합 구하기와 동일한 세그먼트 트리 문제였다

동일하지만 구간합을 저장 하는 것이 아닌 최소값을 저장하는 것이 달라진 점이다 그 외에는 동일하게 해주면 된다.

def solution(n, lost, reserve):
    answer = 0
    student = [0]*(n+1)
    for k in lost:
        student[k] = -1
    for k in reserve:
        student[k] += 1

    for i in range(1,n+1):
        if student[i] > 0:
            for new_student in [i-1,i+1]:
                if 1<=new_student <=n:
                    if student[new_student] == -1:
                        student[i] -= 1
                        student[new_student] += 1
                        break
    for i in range(1,n+1):
        if student[i] >=0:
            answer += 1
    return answer

단순하게 풀었다.

stduent 만큼의 배열을 만들어 준 다음 index가 벗어나지 않게 앞에서부터 차근차근 나눠주는걸로했다.

그리고 답은 0 이상의 개수를 구해서 출력해주었다.

def solution(n, lost, reserve):
    answer = 0
    student = [0]*(n+1)
    for k in lost:
        student[k] = -1
    for k in reserve:
        student[k] += 1
    
    for i in range(1,n+1):
        if student[i] > 0:
            for new_student in [i-1,i+1]:
                if 1<=new_student <=n:
                    if student[new_student] == -1:
                        student[i] -= 1
                        student[new_student] += 1
                        break
                        
    answer = student.count(0) + student.count(1) -1
    return answer

 이런식으로 카운트 method를 써주어도 된다.

def solution(answers):
    ans = []
    person3 = [3,3,1,1,2,2,4,4,5,5]
    person2 = [2,1,2,3,2,4,2,5]
    result = [0,0,0]
    for ind,answer in enumerate(answers):
        if answer == (ind)%5+1:
            result[0] += 1
        if answer == person2[ind%len(person2)]:
            result[1] += 1
        if answer == person3[ind%len(person3)]:
            result[2] += 1

    max_result = max(result)
    for k in range(3):
        if result[k] == max_result:
            ans.append(k+1)
    return ans

반복되는 수들을 list로 만들어준다음 modulo 계산을 통해 해당위치의 값과 비교를 해주면 된다.

import collections
def solution(participant, completion):
    answer = collections.Counter(participant) - collections.Counter(completion)
    return list(answer)[0]

Couter를 이용해 쉽게 풀 수 있다. 

from itertools import combinations
def solution(numbers):
    answer = []
    answer = set(answer)
    for k in combinations(numbers,2):
        answer.add(sum(k))
    answer = list(answer)
    answer.sort()
    return answer

콤비네이션을 이용해 쉽게 풀었다.

그리고 sort를 해주었다.

def check(t,result):
    if len(result):
        if result[-1] == t:
            result.pop()
            return 2
        else:
            result.append(t)
            return 0
    else:
        result.append(t)
        return 0


def solution(board, moves):
    answer = 0
    lens = len(board)
    result = []
    for k in moves:
        for t in range(lens):
            if board[t][k-1]:
                answer += check(board[t][k-1],result)
                board[t][k-1] = 0
                break
            
    return answer

시뮬레이션을 통해 해주면 간단한 문제이다.

가장 끝에 있는 경우와 아닌경우를 비교해서 해주면 된다.

import math
import sys
input = sys.stdin.readline
def init(node_number,start,end):
    global segement_tree,arr
    if start == end:
        segement_tree[node_number] = arr[start]
        return segement_tree[node_number]
    else:
       segement_tree[node_number] = init(node_number*2, start, (start+end)//2) + init(node_number*2+1, (start+end)//2+1, end)
       return segement_tree[node_number]

def update(node_number,start,end,index,diff):
    global segement_tree
    if (index < start) or (index > end):
        return
    segement_tree[node_number] = segement_tree[node_number] + diff
    if (start != end):
        update( node_number*2, start , (start+end)//2,index,diff)
        update(node_number*2+1, (start+end)//2+1,end,index,diff)

def sum_range(node_number,start,end,left,right):
    global segement_tree
    if (left > end) or (right<start):
        return 0
    if (left <= start) and (end<=right):
        return segement_tree[node_number]
    return sum_range(node_number*2,start,(start+end)//2,left,right) + sum_range(node_number*2+1,(start+end)//2+1,end,left,right)

N,M,K = map(int,input().split())
height = math.ceil(math.log2(N))
tree_size = 2**(height+1)-1
segement_tree = [0]*tree_size
arr = [int(input()) for _ in range(N)]

init(1,0,N-1)
cnt = M+K
while cnt:
    command,number1,number2 = map(int,input().split())
    if command == 1:
        diffrence = number2 - arr[number1-1]
        arr[number1 - 1] = number2
        update(1,0,N-1,number1-1,diffrence)
    else:
        print(sum_range(1,0,N-1,number1-1,number2-1))
    cnt -= 1

세그먼트 트리를 활용한 문제이다.

범위의 값을 저장하는 트리를 만들어두는 방식이고, 그걸 통해, 값이 변경 시 반복횟수를 줄이는 방식이다.

세그먼트 트리에 대해서 공부하면서 푼 문제라 아직 익숙하지 않다.

일단 기억하고 있는 세그먼트 트리의 기준은

세그먼트 트리로 만들고 싶은 원본 배열의 길이가 N이라고 할때

세그먼트 트리의 길이는 주어진 N보다 크거나 같은 2^k를 구하고, 이것의 2배를 하면 세그먼트 트리의 사이즈가 된다.

루트노드는 무조건 1이고,

루트노드의 왼쪽 노드는 2, 오른쪽 노드는 3이 된다.

세그먼트 트리에서 부모노드 A가 있을 때에 

A노드의 왼쪽 자식 노드는 A*2의 크기가 되고,

오른쪽 자식 노드는 A*2 + 1이 된다.

그리고 여기서 또 중요한 것은 범위이다.

특정 부모노드의 범위가 [left , rigiht] 이라고 할때, 

이 부모노드의 왼쪽 자식노드는 [left , (left+right)//2]가 되고

오른쪽 자식 노드는 [(left+right)//2 + 1, right] 가 된다.

이렇게 만들어주면 세그먼트 트리의 초기화가 가능하다.

이렇게 한뒤 특정 값의 갱신은 그 값이 갱신된 위치를 찾아, 그 변화량 만큼 바꿔주면 된다.

특정 범위 합은 범위를 벗어났을때, 범위안에 완전히 들어왔을때, 범위에 일부분 겹쳤을때로 나뉠수 있다.

이걸 이용해서 풀면된다.

위와 같이 세그먼트 트리를 위와 같이 주어진 조건에 맞춰서 만들고, 그 범위조차 원리에 맞게 만들어도 되지만, 쉽게 풀기 위하여, N 이 12라고 해도 N이 16일때와 같이 2의 제곱수의 크기만큼의 배열이 있다고 가정하고 만들어도 괜찮다.

import sys
import math
def init():
    global tree_size

    for i in range(tree_size-1,0,-1):
        segement_tree[i] = segement_tree[i*2] + segement_tree[i*2+1]


def update(index,diff):
    while index >= 1:
        segement_tree[index] += diff
        index//=2

def sum_range(node_number,start,end,left,right):
    if left > end or start > right:
        return 0
    if (left <= start) and (end <= right):
        return segement_tree[node_number]
    return sum_range(node_number*2,start,(start+end)//2,left,right) + sum_range(node_number*2+1,(start+end)//2+1,end,left,right)
input = sys.stdin.readline

N,M,K = map(int,input().split())

height = math.ceil(math.log2(N))
tree_size = 2**height
total_size = 2**(height+1)

segement_tree = [0]*total_size

for i in range(N):
    segement_tree[tree_size + i] = int(input())

init()
for i in range(M+K):
    command = list(map(int,input().split()))
    if command[0] == 1:
        diff = command[2] - segement_tree[tree_size + command[1] - 1]
        update(command[1]+tree_size-1,diff)
    else:
        print(sum_range(1,0,tree_size-1,command[1]-1,command[2]-1))

세그먼트 트리 자체를 2의 제곱수의 크기일때로 생각하고  넣어주는 방식으로 푸는 방식이다.

import heapq
import sys

input = sys.stdin.readline
N = int(input())
arr = []
for _ in range(N):
    temp = list(map(int,input().split()))
    for number in temp:
        heapq.heappush(arr,number)
    while len(arr) > N:
        heapq.heappop(arr)



result = heapq.heappop(arr)
print(result)

N번째 큰수를 구하는 거였고, N의 최대값이 1500이므로, 전체 input을 받아서 행렬을 만드는게 아닌, 

한 행이 들어올때마다 판별을 해줘야한다고, 생각했다.

그리고 우리가 구하고 싶은 것은 N번째 이므로, 저장할 칸은 N 칸만 있으면 된다고 생각했고, 이걸 heapq를 이용해서 구현했다.

처음 구현한 방식은 일단 한 행을 전부 집어넣고, 리스트의 길이가 N이 될때까지 heappop을 계속 해주었다. 

그리고 마지막으로 heappop을 해서 원하는 결과를 얻었다.

import heapq
import sys

input = sys.stdin.readline

N = int(input())
arr = []

for i in range(N):
    input_list = map(int,input().split())
    if i == 0 :
        for number in input_list:
            heapq.heappush(arr,number)
    else:
        for number in input_list:
            if number > arr[0]:
                heapq.heappushpop(arr,number)
big_list = heapq.nlargest(N,arr)
print(big_list[N-1])

두번째 방법은 heapq 모듈을 좀 더 활용하는 방법이다.  무조건 넣고 길이 N이 될때까지 계속 pop 하는 것이 아닌.

heappushpop을 쓰는 것이다. 이것은 heap에 먼저 push를 한뒤에 가장 작은 값을 pop 하는 것으로,

heappush와 heappop을 쓰는 것보다 실행속도가 더 빠르다.

그리고 마지막으로 heapq.nlargest를 쓰는 것이다. 이 메소드는 정의된 요소에서 가장 큰 순서대로 n개로 구성된 리스트를 반환해주는 메소드이다. 이걸 이용하면, 정렬을 한 효과와 동일하다.

# stkang9409 풀이 해석

def find_max_value(x):
    return arr[max_row_list[x]][x]

import sys

input = sys.stdin.readline


N = int(input())
arr = [list(map(int,input().split())) for _ in range(N)]

max_row_list = [N-1]*N
# 각 열마다 가장 큰 값은 N-1번 행에 있는 값이다.
# 매번 돌면서 각 열마다 가장 큰값들을 비교해, 가장 큰 값이 있는 열의 index 값을 하나씩 줄여나간다.
# 그렇게 하면 마지막 N번째에 가장 큰 값을 가지는 열의 값이 N번째로 큰 수의 열값이 되고
# 그 때 저장된 위치의 값이 행이된다.
for cnt in range(N):
    max_col_index = 0
    for col in range(N):
        max_col_index = max(col,max_col_index,key= find_max_value)
    if cnt == N-1:
        print(arr[max_row_list[max_col_index]][max_col_index])
    max_row_list[max_col_index] -= 1

마지막 풀이는 stkang9409님 코드를 보고 분석하것이다.

이 방법은 heapq를 쓴 것이 아닌, 문제의 조건을 보고 푼 방식이다.

위의 heapq를 쓴다면 신경 안 쓸 조건이지만, 문제에 주어진 조건을 보면

각 열의 값들은 그 다음행의 값보다 작다는 것이다. 즉 A열의 B행의 값은 B+1행보다는 무조건 작다는 것이다.

이 점을 이용해 N번째로 큰 값을 알 수 있다.

만약 조건 N이 주어진다면

각 열마다 가장 큰 행의 위치는 N-1일것이다. (0행부터 시작한다)

이걸 하나의 리스트로 구성하면

max_row_list = [N-1, N-1,.... N-1]

일것이고, 이 리스트의 인덱스는 arr의 열의 값이 될것이고, 해당 index의 값은 행이 될것이다.

각 열에서의 최대값을 비교해서 가장 큰 값을 구해준다.

각 열의 최대값은 arr[ max_row_list[ind] ] [ ind ] 가 될 것이다.

이렇게 하면 가장 큰 값이 있는 열의 값을 구할 수 있다. 그 열의 값이 있는 max_row_list의 값을 1을 낮춰준다.

이런 식으로 반복 하면 N번 반복하면 N번째로 큰 수를 알 수 있다.

예시 ) 

12 7 9 15 5

13 8 11 19 6

21 10 26 31 16

48 14 28 35 25

52 20 32 41 49

위와 같이 주어지면 

max_row_index = [4,4,4,4,4] 가 될 것이다.

--  1번째  --

arr[4][0],arr[4][1],arr[4][2],arr[4][3],arr[4][4] 의 값을 비교해보면 arr[0][4]가 가장 작다.

그러면 max_row_index 의  0번 인덱스의 값을 1 줄여준다,

max_row_index = [3,4,4,4,4] 가 된다.

-- 2번째 --

arr[3][0],arr[4][1],arr[4][2],arr[4][3]arr[4][4] 의 값을 비교해보면 arr[4][4]의 49가 가장 크다.

그러면 4번 인덱스이고 해당 max_row_index의 값을 줄여준다.

max_row_index = [3,4,4,4,3]

-- 3번째 --

arr[3][0],arr[4][1],arr[4][2],arr[4][3]arr[3][4] 의 값을 비교해보면 arr[3][0]의 48이 가장 크다.

그러면 0번 인덱스이고 해당 max_row_index의 값을 줄여준다.

max_row_index = [2,4,4,4,3]

-- 4번째 --

arr[2][0],arr[4][1],arr[4][2],arr[4][3]arr[3][4] 의 값을 비교 해보면  arr[4][3]의 41이 가장 크다.

그러면 3번 인덱스이고 해당 max_row_index의 값을 줄여준다.

max_row_index = [2,4,4,3,3] 

--5번째 (마지막) --

arr[2][0],arr[4][1],arr[4][2],arr[3][3],arr[3][4] 의 값을 비교 해보면 arr[3][3]의 35이 가장 크다

그리고 우리가 구하던 N번째로 큰 값이므로 이 값을 그대로 출력해주면 된다.

설명이 많이 부족하겠지만, 최대한 자세히 설명을 했다.

마지막 풀이는 문제의 조건을 활용해 각 열을 기준으로 하는 최대 행을 저장해주는 리스트를 만들어두고

각 열의 최대값을 갱신해주면서 하는 방식으로 보면 된다.