4주차 스터디(23.12.01)

학회 발표 신청을 낸 뒤, 이제 구체적인 결과를 정말 내기 위해 마지막 박차를 가하고 있다보니 ... 

문제를 많이 못 풀게 되었는데, 그래도 틈 나는대로 몇몇 문제들을 풀어보았다.

 

1. Longest Palindromic Substring

https://leetcode.com/problems/longest-palindromic-substring/description/

class Solution:
    def longestPalindrome(self, s: str) -> str:
        t = '#'.join('^{}$'.format(s))
        print(t)
        n = len(t)
        P = [0] * n
        C = R = 0

        for i in range (1,n-1):
            P[i] = (R > i) and min(R-i, P[2*C - i])
            while t[i + 1 + P[i]] == t[i - 1 - P[i]]:
                P[i] += 1
            if i + P[i] > R:
                C,R = i , i + P[i]
        max_len, answer = max((n,i) for i,n in enumerate(P))
        return s[(answer - max_len)//2 : (answer + max_len) // 2]

 

2. 전화번호부

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

def solution(phone_book):
    phone_book.sort()
    N = len(phone_book)
    answer = True
    for i in range (0,N-1):
        if len(phone_book[i]) <= len(phone_book[i+1]) and phone_book[i+1][:len(phone_book[i])] == phone_book[i]:
            answer = False
    return answer

 

 

3. Product of Array Except Self

https://leetcode.com/problems/product-of-array-except-self/

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        ans = 1
        cnt_zero = 0
        for i in range (0,len(nums)):
            if nums[i] == 0:
                cnt_zero += 1
            else:
                ans *= nums[i]
            
        answer = []
        if cnt_zero == 0:
            for i in range (0,len(nums)): 
                t = ans // nums[i]
                answer.append(t)
        elif cnt_zero == 1:
            for i in range (0,len(nums)):
                if nums[i] == 0:
                    answer.append(ans)
                else:
                    answer.append(0)
        else:
            for i in range (0,len(nums)):
                answer.append(0)
        return answer

 

4. 의상

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

def solution(clothes):
    dict = {}
    for i in range (0,len(clothes)):
        if clothes[i][1] not in dict:
            dict[clothes[i][1]] = [clothes[i][0]]
        else:
            dict[clothes[i][1]].append(clothes[i][0])
    a = list(dict.values())
    answer = 1
    for i in range (0,len(a)):
        answer *= (len(a[i]) + 1)
    return answer - 1

 

5. 행렬의 곱셈

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

def solution(arr1, arr2):
    answer = []
    n = len(arr1[0])
    for i in range (0,len(arr1)):
        ans = []
        for j in range (0,len(arr2[0])):
            cnt = 0
            for k in range (0,len(arr1[0])):
                cnt += arr1[i][k] * arr2[k][j]
            ans.append(cnt)
        answer.append(ans)
        
                
    return answer

 

6. 주식가격

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

from collections import deque
def solution(prices):
    answer = []
    prices = deque(prices)
    while prices:
        x = prices.popleft()
        count = 0
        for i in prices:
            if x > i:
                count += 1
                break
            count += 1
        answer.append(count)
    return answer

 

7. A → B

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

from collections import deque
A,B = map(int,input().split())
deq = deque([A])
jud = False
dict = {A:1}
while deq:
    c = deq.popleft()
    if c == B:
        jud = True
        print(dict[c])
        break
    else:
        if 2*c > 10**9:
            continue
        else:
            deq.append(2*c)
            dict[2*c] = dict[c] + 1
        if 10*c + 1 > 10** 9:
            continue
        else:
            deq.append(10*c + 1)
            dict[10*c+1] = dict[c] + 1
if deq == deque([]) and jud == False:
    print(-1)

 

10. 숨바꼭질

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

from collections import deque
N,K = map(int,input().split())
num = [0 for _ in range (0,100001)]
deq = deque()
deq.appendleft(N)
while deq:
    X = deq.popleft()
    if X == K:
        print(num[K])
    else:
        for a in (X-1,X+1,2*X):
            if 0 <= a <= 100000 and num[a] == 0:
                num[a] = num[X] + 1
                deq.append(a)

 

11. 숨바꼭질 3

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

from collections import deque
MAX = 100001
check = [False] * (MAX+1)
dist = [-1] * (MAX+1)

n,k = map(int, input().split())
deq = deque()
deq.append(n)
check[n] = True
dist[n] = 0

while deq:
    now = deq.popleft()
    if 0 <= now*2 <= MAX and check[now*2] == False:
        deq.appendleft(now*2)
        check[now*2] = True
        dist[now*2] = dist[now]
    if 0 <= now*2 <= MAX and check[now*2] == True:
        dist[now*2] = min(dist[now],dist[now*2])
    if 0 <= now + 1 <= MAX and check[now+1] == False:
        deq.append(now+1)
        check[now+1] = True
        dist[now+1] = dist[now] + 1
    if 0 <= now + 1 <= MAX and check[now+1] == True:
        dist[now+1] = min(dist[now+1],dist[now] + 1)
    if 0 <= now - 1 <= MAX and check[now-1] == False:
        deq.append(now-1)
        check[now-1] = True
        dist[now-1] = dist[now] + 1
    if 0 <= now - 1 <= MAX and check[now-1] == True:
        dist[now-1] = min(dist[now] + 1,dist[now-1])
print(dist[k])

 

12. 나는 포켓몬마스터 이다솜

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

import sys
N,M = map(int, input().split())
num = {}
name = {}
for i in range(1,N+1):
    pokemon = input()
    num[i] = pokemon
    name[pokemon] = i

for _ in range (0,M):
    x = input()
    if x.isdigit():
        print(num[int(x)])
    else:
        print(name[x])

 

13. 토마토

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

import copy
from collections import deque
def orangesRotting(m,n,grid):
    checked = [[False for _ in range (0,n)] for _ in range (0,m)]
    deq = deque()
    a = []
    fresh = 0
    for i in range (0,m):
        for j in range (0,n):
            if grid[i][j] == 0:
                fresh += 1
            if grid[i][j] == 1:
                a.append([i,j])
    deq.append(a)
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    day = 0
    #이미 다 상해있는 경우
    if fresh == 0:
        return day
    #그렇지 않은 경우
    while deq:
        k = fresh
        x = deq.popleft()
        rotten_orange = []
        for i in range (0,len(x)):
            for j in range (0,4):
                a = x[i][0] + dx[j]
                b = x[i][1] + dy[j]
                if 0 <= a < m and 0 <= b < n and grid[a][b] == 0 :
                    grid[a][b] = 1
                    fresh -= 1
                    rotten_orange.append([a,b])
        if k == 0:
            break
        if k == fresh:
            return -1
        else:
            day += 1
            deq.appendleft(rotten_orange)
    return day
M,N = map(int,input().split())
A = []
for i in range (0,N):
    a = list(map(int,input().split()))
    A.append(a)
print(orangesRotting(N,M,A))

 

14. 연결요소의 개수

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

from collections import deque
import sys
input = sys.stdin.readline

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

N, M = map(int, input().split()) 
graph = [[] for _ in range(0,N+1)]
for i in range(0,M):
    a,b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

count = 0 
visited = [False] * (N+1)
for i in range(1, N+1):
    if not visited[i]:
        bfs(graph, i, visited)
        count += 1
print(count)

 

15. 회의실 배정

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

import sys
input = sys.stdin.readline
N = int(input())
time = [[0,0] for _ in range (0,N)]
for i in range (0,N):
    a,b = map(int,input().split())
    time[i][0],time[i][1] = a,b

time.sort(key = lambda x:(x[1],x[0]))
cnt = 1
end_time = time[0][1]
for i in range (1,N):
    if end_time <= time[i][0]:
        cnt += 1
        end_time = time[i][1]
print(cnt)

 

16. 쉬운 최단거리

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

from collections import deque
N,M = map(int,input().split())
graph = []
visited = [[False for _ in range (0,M)] for _ in range (0,N)]
dist = [[0 for _ in range (0,M)] for _ in range (0,N)]
for i in range (0,N):
    a = list(map(int,input().split()))
    graph.append(a)
dx,dy = [0,0,1,-1],[1,-1,0,0]
deq = deque()
for i in range (0,N):
    for j in range (0,M):
        if graph[i][j] == 2:
            deq.append([i,j])
            dist[i][j] = 0

while deq:
    x,y = deq.popleft()
    visited[x][y] = True
    for i in range (0,4):
        a,b = x+dx[i],y+dy[i]
        if 0 <= a < N and 0 <= b < M and visited[a][b] == False:
            if visited[a][b] == False and graph[a][b] == 1:
                dist[a][b] = dist[x][y] + 1
                visited[a][b] = True
                deq.append([a,b])
for i in range (0,N):
    for j in range (0,M):
        if graph[i][j] == 1 and visited[i][j] == False:
            dist[i][j] = -1
        if graph[i][j] == 0:
            dist[i][j] = 0
for i in range (0,len(dist)):
    a = " ".join(str(s) for s in dist[i])
    print(a)

 

17. 색종이

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

import sys
input = sys.stdin.readline
N = int(input())
cut_paper = []
n = N
while n > 0:
    A,B = [[0 for _ in range (0,n)] for _ in range (0,n)], [[1 for _ in range (0,n)] for _ in range (0,n)]
    n = n//2
    a = []
    a.append(A)
    a.append(B)
    cut_paper.append(a)
paper = []
for i in range (0,N):
    a = list(map(int,input().split()))
    paper.append(a)
cutted = [[False for _ in range (0,N)] for _ in range (0,N)]
M = len(cut_paper)
cnt_blue = 0
cnt_white = 0
for i in range (0,M): #큰 사각형부터 크기를 쪼개보기
    for x in range (0,N,len(cut_paper[i][0])): 
        for y in range (0,N,len(cut_paper[i][0])):#사각형의 꼭짓점 정하기 (x,y로 셋팅)
            jud1 = True
            jud2 = True
            for j in range (0,len(cut_paper[i][0])):
                for k in range (0,len(cut_paper[i][0])):
                    if cut_paper[i][0][j][k] == paper[x+j][y+k] and cutted[x+j][y+k] == False: #흰색인지 확인
                        continue
                    else:
                        jud1 = False
                        break
            for j in range (0,len(cut_paper[i][0])):
                for k in range (0,len(cut_paper[i][0])):
                    if cut_paper[i][1][j][k] == paper[x+j][y+k] and cutted[x+j][y+k] == False: #파란색인지 확인
                        continue
                    else:
                        jud2 = False
                        break
            if jud1 == True:
                for j in range (0,len(cut_paper[i][0])):
                    for k in range (0,len(cut_paper[i][0])):
                        cutted[x+j][y+k] = True #흰색인지 확인
                cnt_white += 1

            if jud2 == True:
                for j in range (0,len(cut_paper[i][0])):
                    for k in range (0,len(cut_paper[i][0])):
                        cutted[x+j][y+k] = True #파란색인지 확인
                cnt_blue += 1
print(cnt_white)
print(cnt_blue)

 

18. N과 M(5)

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

answer = []
def backtracking(depth,n,m):
    if depth == m:
        answer.append(" ".join(map(str,result)))
    for i in range (0,n):
        if visited[i] == False:
            visited[i] = True
            result.append(A[i])
            backtracking(depth + 1,n,m)
            visited[i] = False
            result.pop()
result = []            
N,M = map(int,input().split())          
A = list(map(int,input().split()))  
A.sort()
visited = [False for _ in range (0,N+1)]
backtracking(0,N,M)
for i in range (0,len(answer)):
    print(answer[i])

 

 

19. 플로이드

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

import sys
import math
input = sys.stdin.readline
N = int(input())
M = int(input())
A = [[math.inf for _ in range (0,N)] for _ in range (0,N)]
for i in range (0,M):
    a,b,c = map(int,input().split())
    if A[a-1][b-1] == math.inf:
        A[a-1][b-1] = c
    else:
        A[a-1][b-1] = min(c,A[a-1][b-1])
for k in range (0,N):
    for i in range (0,N):
        for j in range (0,N):
            if i == j:
                A[i][j] = 0
            else:
                A[i][j] = min(A[i][j], A[i][k] + A[k][j])
for i in range (0,N):
    for j in range (0,N):
        if A[i][j] == math.inf:
            A[i][j] = 0
for i in range (0,len(A)):
    print(" ".join(str(s) for s in A[i]))