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

1. n^2 배열자르기

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

프로그래머스

 

시간초과 발생함

def solution(n, left, right):
    A = list()
    for i in range(n) :
        for j in range(n) :
            max_number = max(i,j)
            A.append(max_number + 1)

    answer = A[left:right+1]

    return answer

• 대각선을 기준으로 위아래 값이 다른 같이 경우가 발생하면 -> i%n, i//n을 사용할 수 있는지 살펴보기 ! 

def solution(n, left, right):
    A = []
    for i in range(left, right+1) :
        a = i%n
        b = i//n
        A.append(max(a,b) + 1)

    return A

 

---

2. 행렬의 곱셈

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

프로그래머스

• 인덱스 설정 중요 -> 런타임에러 나는 주요 원인

def solution(arr1, arr2):
    n = len(arr1)
    m = len(arr2)
    r = len(arr2[0])
    answer = [[0 for i in range(r)] for _ in range(n)]

    for i in range(n) :
        for j in range(r) :
            number = 0
            for k in range(m) :
                answer[i][j] += arr1[i][k] * arr2[k][j]


    return answer

 

---

3. 그림

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

from collections import deque
directions = [(1,0),(-1,0),(0,1),(0,-1)]

def dfs(n,m,A) :
    queue = deque()
    count = 0
    answer = list()
    for row in range(n) :
        for col in range(m) :
            if A[row][col] == 1 :
                width = 0
                queue.append((row,col))
                A[row][col] = 0
                while queue :
                    curr_x,curr_y = queue.popleft()
                    width += 1
                    for dx,dy in directions :
                        next_x,next_y = curr_x+dx,curr_y+dy
                        if 0<=next_x<n and 0<=next_y<m and A[next_x][next_y] == 1 :
                            queue.append((next_x,next_y))
                            A[next_x][next_y] = 0

                count += 1
                answer.append(width)



    return count, answer


n,m = map(int, input().split(" "))
A = list()
for i in range(n) :
    A.append(list(map(int,input().split())))

count, answer = dfs(n,m,A)

if count == 0 :
    print(0)
    print(0)
else :
    print(count)
    print(max(answer))

 

---

4. 음식물 피하기

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

from collections import deque
n,m,k = map(int, input().split(" "))
A = [[0 for i in range(m)] for j in range(n)]

for i in range(k) :
    a,b = map(int,input().split(" "))
    A[a-1][b-1] = 1

direction = [(1,0),(-1,0),(0,1),(0,-1)]

def dfs(n,m,A) :
    queue = deque()
    answer = list()
    for row in range(n) :
        for col in range(m) :
            if A[row][col] == 1 :
                queue.append((row,col))
                A[row][col] = 0
                count  = 0
                while queue :
                    curr_x, curr_y = queue.popleft()
                    count += 1
                    for dx,dy in direction :
                        next_x,next_y = curr_x+dx, curr_y+dy
                        if 0<=next_x<n and 0<=next_y<m and A[next_x][next_y] == 1 :
                            queue.append((next_x,next_y))
                            A[next_x][next_y] = 0

                answer.append(count)

    return max(answer)

print(dfs(n,m,A))

 

 

---

5.  주지수

• dp, 누적합의 개념을 이용해서 풀어야, 시간초과 안걸림
• 누적합 구하는 공식
  
  • dp[i][j] = area[i][j] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] 
• 출력값 공식
  • dp[i][j] - dp[x-1][j] - dp[i][y-1] + dp[x-1][y-1] 

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

import sys
input = sys.stdin.readline

n,m = map(int, input().split())
area = [list(map(int,input().split())) for _ in range(n)]

dp = [[0] * (m+1) for _ in range(n+1)]
for i in range(1,n+1) :
    for j in range(1,m+1) :
        dp[i][j] = area[i-1][j-1] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]


for _ in range(int(input())) :
    x,y,i,j = map(int,input().split())
    print(dp[i][j] - dp[x-1][j] - dp[i][y-1] + dp[x-1][y-1])

 

---

6. 이건 꼭 풀어야 해 !

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

import sys
input = sys.stdin.readline
n,m = map(int,input().split(" "))
A = list(map(int, input().split(" ")))
A.sort()

S = [0] * (n)
S[1] = A[1]

for i in range(n) :
    S[i] = A[i] + S[i-1]

S.insert(0,0)


for j in range(m) :
    a,b = map(int, input().split(" "))
    print(S[b]-S[a-1])

 

---