코딩테스트 언어 Java->Python 변경 기록

목차 LIST

 

 

코딩 테스트에서 사용하는 언어를 Java에서 Python으로 바꿔보려고 한다.

그래서 가벼운 문제들 풀면서 감잡는 과정 기록

 

 

1) 백준 2606번 바이러스

import sys
from collections import deque

n = int(input())
m = int(input())

table = [[0 for _ in range(101)] for _ in range(101)]

for _ in range(m):
    x, y = map(int, input().split())
    table[x][y] = 1
    # 이부분! 때문에 처음에 틀렸었음
    table[y][x] = 1

result = 0
visited = [0] * 101

stack = deque()
stack.append(1)
visited[1] = 1

while stack:
    target = stack.pop()
    for i in range(1, n+1):
        if table[target][i] == 1 and visited[i] == 0:
            stack.append(i)
            result += 1
            visited[i] = 1

print(result)

 

 

2) 백준 2667번 단지번호붙이기

import sys
from collections import deque

n = int(input())

# 상, 하, 좌, 우 방향 정의
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

table = [[0 for _ in range(n+1)] for _ in range(n+1)]
visited = [[False for _ in range(n+1)] for _ in range(n+1)]

for i in range(n):
    numbers = list(map(int, input()))
    table[i] = numbers

result = []

stack = deque()

for i in range(n):
    for j in range(n):
        if table[i][j] == 1 and visited[i][j] == False:
            visited[i][j] = True
            stack.append((i,j))
            size = 1
            while stack:
                x, y = stack.pop()
                
                for dx, dy in dirs:
                    new_x, new_y = x + dx, y + dy
                    if new_x >= 0 and new_y >= 0 and new_x < n and new_y < n and not visited[new_x][new_y] and table[new_x][new_y] == 1:
                        stack.append((new_x, new_y))
                        visited[new_x][new_y] = True
                        size += 1
            
            result.append(size)

result.sort()
print(len(result))
for r in result:
    print(r)

 

 

3) 백준 11724번 연결 요소의 개수

 

입력받을 때 그냥 input() 사용하면 시간초과 떴는데,

input = sys.stdin.readline 사용하니까 통과했음

 

sys.stdin.readline()은 줄단위로 입력을 빠르게 하는데 최적화되어 있어 입력 처리가 훨씬 빠르다고 함

그래서 알고리즘이나 성능에 민감한 애플리케이션에서는 sys.stdin.readline() 사용하는 것이 좋을 것 같음

import sys
from collections import deque

# 빠른 입력을 위해 sys.stdin.readline() 사용
input = sys.stdin.readline

n, m = map(int,input().split())

table = [[0 for _ in range(n+1)] for _ in range(n+1)]
point = [0] * (n+1)

for i in range(m):
    x, y = list(map(int, input().split()))
    table[x][y] = table[y][x] = 1

result = 0
stack = deque()

for i in range(1, n+1):
    if point[i] == 0:

        stack.append(i)
        point[i] = 1
        result += 1

        while stack:
            target = stack.pop()
            for idx in range(1, n+1):
                if point[idx] == 0 and table[target][idx] == 1:
                    stack.append(idx)
                    point[idx] = 1
       
print(result)

 

 

4) 백준 11725 트리의 부모 찾기

 

평소처럼 n+1 로 2차원배열 만들었더니 메모리 초과 뜸

사이즈 최대가 100,000 개라서 2차원 배열 하면 안됨

 

그래서 n+1 * n+1 배열을 만드는 대신 해당하는 값만 담을 수 있도록 했다.

import sys
from collections import deque

# 빠른 입력을 위해 sys.stdin.readline() 사용
input = sys.stdin.readline

n = int(input())

# 포인트는 여기!
table = [[] for _ in range(n+1)]

for i in range(n-1):
    x, y = list(map(int, input().split()))
    # 그리고 여기!
    table[x].append(y)
    table[y].append(x)

result = [0] * (n+1)

stack = deque()

stack.append(1)
result[1] = 1

while stack:
    target = stack.pop()
    for idx in table[target]:
        if result[idx] == 0:
            stack.append(idx)
            result[idx] = target

for idx in range(2, n+1):
    print(result[idx])

 

 

5) 백준 2468 안전 영역

 

3중포문이라서 해도될까? 고민했는데, 최대가 100 이라서 괜찮은 것 같음

44% 정도에서 실패한다면, "아무 지역도 물에 잠기지 않을 수 있다" 라는 노트 글을 참고하자.

이건 즉 "비가 안 올수도 있다" 는 뜻이다.

 

import sys
from collections import deque

# 빠른 입력을 위해 sys.stdin.readline() 사용
input = sys.stdin.readline

n = int(input())

# 상, 하, 좌, 우 방향 정의
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

table = [[] for _ in range(n+1)]

result = 0

for i in range(n):
    line = list(map(int, input().split()))
    table[i] = line

stack = deque()

for depth in range(0, 101):    
    count = 0
    visited = [[False for _ in range(n+1)] for _ in range(n+1)]

    for i in range(n):
        for j in range(n):
            if table[i][j] > depth and visited[i][j] == False:
                stack.append((i, j))
                visited[i][j] = True
                count += 1

                while stack:
                    x, y = stack.pop()
                    for dx, dy in dirs:
                        new_x, new_y = x + dx, y + dy
                        if new_x >= 0 and new_y >= 0 and new_x < n and new_y < n and not visited[new_x][new_y] and table[new_x][new_y] > depth:
                            stack.append((new_x, new_y))
                            visited[new_x][new_y] = True

    result = max(result, count)

print(result)

 

6) 백준 1937 욕심쟁이 판다

dfs + dp 라고 생각해서 이전에 풀었던 것처럼 stack을 사용해서 시작했다.

그런데 할수록 뭔가 복잡해지고 꼬이는 느낌이 들었는데, 찾아보니 dfs + dp 일 때, stack으로 하면 복잡해질 수 있다고 한다.

그래서 재귀를 사용한 dfs + dp 조합으로 진행했다.

 

여기서 34% 정도 되면 RecursionError가 발생하는데, 이를 방지하기 위해 sys.setrecursionlimit을 올려야 한다.

import sys
from collections import deque

# 빠른 입력을 위해 sys.stdin.readline() 사용
input = sys.stdin.readline

# RecursionError 방지를 위해!
sys.setrecursionlimit(40000000)


n = int(input())

# 상, 하, 좌, 우 방향 정의
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

table = [[] for _ in range(n+1)]

result = 0

for i in range(n):
    line = list(map(int, input().split()))
    table[i] = line

stack = deque()

dp = [[-1 for _ in range(n+1)] for _ in range(n+1)]

def dfs(x, y):
    if dp[x][y] != -1:
        return dp[x][y]

    dp[x][y] = 1

    for dx, dy in dirs:
        new_x, new_y = x + dx, y + dy
        if 0 <= new_x < n and 0 <= new_y < n and table[new_x][new_y] > table[x][y]:
            dp[x][y] = max(dp[x][y], dfs(new_x, new_y) + 1)
    return dp[x][y]


for i in range(n):
    for j in range(n):
        result = max(result, dfs(i,j))

print(result)

 

7) 백준 2839 설탕 배달

직전에 dfs + dp를 풀고, 이제는 dp 문제를 쭉 풀어보려고 함

 

우선 이 문제는 이렇게 간단한 계산식으로 풀 수도 있는데, 

import sys

# 빠른 입력을 위해 sys.stdin.readline() 사용
input = sys.stdin.readline

n = int(input())

bags = 0

while n >= 0:
    if n % 5 == 0:
        bags += n // 5
        print(bags)
        break
    n -= 3
    bags += 1
else:
    print(-1)

 

원래 목적이었던 DP 풀이!

처음에 2차원 배열 생각해서 삽질했다가.. 일차원배열 사용하는 것으로 해결 🤣

import sys

# 빠른 입력을 위해 sys.stdin.readline() 사용
input = sys.stdin.readline
n = int(input())

dp = [float('inf')] * (n+1)

if n >= 3:
    dp[3] = 1
if n >= 5:
    dp[5] = 1

for i in range(6, n+1):
    dp[i] = min(dp[i-3]+1, dp[i-5]+1)

if dp[n] == float('inf'):
    print(-1)
else:
    print(dp[n])

 

 

 

8) 백준 1463 1로 만들기

 

7번 문제 풀었던 기억으로 풀었다~

파이썬으로 알고리즘 풀기 이제 좀 괜찮아짐

import sys

# 빠른 입력을 위해 sys.stdin.readline() 사용
input = sys.stdin.readline

n = int(input())

dp = [1000001] * (n+1)

dp[1] = 0
if n >= 2:
    dp[2] = 1
if n >= 3:
    dp[3] = 1

for i in range(4, n+1):
    m = dp[i-1]+1
    
    if i % 3 == 0:
        m = min(m, dp[i//3] + 1)
    if i % 2 == 0:
        m = min(m, dp[i//2] + 1)
    
    dp[i] = m

print(dp[n])