[python code review] 2주차 : (영역 구하기, 숫자 할리갈리 게임, 오픈채팅방)

[영역 구하기]

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

2583번: 영역 구하기

1. 코드구현 (중) - DFS 

import sys
sys.setrecursionlimit(10**4)
m, n, k = map(int, input().split())
board = [[0]*n for _ in range(m)]

dx = [1,0,-1,0]
dy = [0,1,0,-1]


def dfs(y, x, arr):
    global areaCnt
    arr[y][x] = 1
    areaCnt += 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < m:
            if arr[ny][nx] == 0:
                dfs(ny, nx, arr)


# 직사각형 세팅하기
for _ in range(k):
    x1, y1, x2, y2 = map(int, input().split())
    for y in range(y1, y2):
        for x in range(x1, x2):
            board[y][x] = 1

areaCnt = 0
area = []
for i in range(m):
    for j in range(n):
        # '0'이라면 영역 구하기
        if board[i][j] == 0:
            areaCnt = 0
            dfs(i, j, board)
            area.append(areaCnt)
print(len(area))
for data in sorted(area):
    print(data, end=' ')

- RecursionError

파이썬 인터프리터에서 가능한 재귀함수 깊이(호출 횟수)를 초과하는 경우 발생

 

import sys
sys.setrecursionlimit(10**4)

를 사용하여 호출 횟수 개선 가능 

 

1-1) 코드 개선 

import sys
sys.setrecursionlimit(10**4)
m, n, k = map(int, input().split())
board = [[0]*n for _ in range(m)]

dX = [1,0,-1,0]
dY = [0,1,0,-1]


def dfs(y, x, arr, count):
    arr[y][x] = 1
    for dx, dy in zip(dX, dY):
        nx = x + dx
        ny = y + dy
        if 0 <= nx < n and 0 <= ny < m:
            if arr[ny][nx] == 0:
                count = dfs(ny, nx, arr, count+1)
    return count


# 직사각형 세팅하기
for _ in range(k):
    x1, y1, x2, y2 = map(int, input().split())
    for y in range(y1, y2):
        for x in range(x1, x2):
            board[y][x] = 1

area = []
for i in range(m):
    for j in range(n):
        # '0'이라면 영역 구하기
        if board[i][j] == 0:
            area += [dfs(i, j, board, 1)]
print(len(area))
for data in sorted(area):
    print(data, end=' ')

- global 선언 없이 매개변수로 count 처리 

for data in sorted(area):

    print(data, end=' ')

는 숏코딩으로

print(*sorted(area)) 와 같이 처리할 수 있음 (하지만 오히려 처리 속도는 느려짐)

- zip함수를 이용하여 동서남북 좌표 리스트인 dX, dY에 접근함 (속도 개선 o)

- *args : - 파라미터를 몇개 받을지 모르는 경우에 사용

print(*[1,2,3,4,5])
print(*('a','b'))
print(*{1:2, 2:4, 8:9})

*args를 리스트나 튜플에 사용하면 각 원소에 접근하고 ' '로 split 해줌 

마찬가지로 dictionary에서도 각 key값에 접근함 

 

4. BFS 풀이 

from collections import deque

m, n, k = map(int, input().split())
board = [[0]*n for _ in range(m)]

dX = [1,0,-1,0]
dY = [0,1,0,-1]


def bfs(yy, xx):
    count = 1
    queue = deque([[yy, xx]])
    board[yy][xx] = 1
    while queue:
        y, x = queue.popleft()
        for dx, dy in zip(dX, dY):
            nx = dx + x
            ny = dy + y
            if 0 <= nx < n and 0 <= ny < m and board[ny][nx] == 0:
                board[ny][nx] = 1
                queue.append([ny, nx])
                count += 1
    return count


# 직사각형 세팅하기
for _ in range(k):
    x1, y1, x2, y2 = map(int, input().split())
    for y in range(y1, y2):
        for x in range(x1, x2):
            board[y][x] = 1


area = []
for i in range(m):
    for j in range(n):
        # '0'이라면 영역 구하기
        if board[i][j] == 0:
            area.append(bfs(i, j))


print(len(area))
for data in sorted(area):
    print(data, end=' ')

 

 

[숫자 할리갈리 게임]

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

20923번: 숫자 할리갈리 게임

1. 코드구현 (중상)

from collections import deque

n, m = map(int, input().split())
dDeck, sDeck = deque(), deque()
dGround, sGround = deque(), deque()

def appendStack(result):
    global dGround, sGround, dDeck, sDeck
    # 도도가 이긴 경우
    if result == 2:
        while sGround:
            dDeck.append(sGround.pop())
        while dGround:
            dDeck.append(dGround.pop())
    else:
        while dGround:
            sDeck.append(dGround.pop())
        while sGround:
            sDeck.append(sGround.pop())

for _ in range(n):
    a, b = map(int, input().split())
    dDeck.appendleft(a)
    sDeck.appendleft(b)

# 도도와 수연이가 카드를 내는 총합이 'm'
while True:
    # 도도의 차례
    dCard = dDeck.popleft()
    dGround.appendleft(dCard)

    # 도도의 덱이 비어있는 경우 종료
    if not dDeck:
        break

    # 도도가 이길 경우
    if dCard == 5:
        # 더미 합치기
        appendStack(2)

    # 수연이가 이길 경우
    if sGround and dGround and (sGround[0] + dGround[0]) == 5:
        appendStack(1)

    m -= 1
    if m == 0:
        break

    # 수연의 차례
    sCard = sDeck.popleft()
    sGround.appendleft(sCard)

    # 수연의 덱이 비어있는 경우 종료
    if not sDeck:
        break

    # 도도가 이길 경우
    if sCard == 5:
        appendStack(2)

    # 수연이가 이길 경우
    if sGround and dGround and (sGround[0] + dGround[0]) == 5:
        appendStack(1)

    m -= 1
    if m == 0:
        break

s, d = len(sDeck), len(dDeck)
if s == d:
    print('dosu')
elif s < d:
    print('do')
else:
    print('su')

블로그, 숏코딩 참고  

input으로 덱의 아래의 값부터 주길래 stack을 사용하였는데 시간 초과가 발생했다..

deque를 사용해야 빠르게 구현할 수 있는 문제였다.

deque를 사용할 경우, 뒤는 물론 앞에서 추가할 때도 O(1)의 시간 복잡도를 가지므로 매우 효율적이다. 

popleft() : 왼쪽에서 꺼내기 appendleft(): 왼쪽에 붙이기 

append() : 오른쪽에 붙이기 pop(): 오른쪽에서 꺼내기 

 

2. 시간초과 발생한 코드 

n, m = map(int, input().split())
dDeck, sDeck = [], []
dGround, sGround = [], []


def appendStack(result):
    global dGround, sGround, sDeck, dDeck
    s_data, d_data = list(reversed(sGround)), list(reversed(dGround))
    # 도도가 이긴 경우
    if result == 2:
        dDeck = d_data + s_data + dDeck
    # 수연이가 이긴 경우
    else:
        sDeck = s_data + d_data + sDeck
    # 그라운드 초기화
    dGround, sGround = [], []


for _ in range(n):
    a, b = map(int, input().split())
    dDeck.append(a)
    sDeck.append(b)

# 도도와 수연이가 카드를 내는 총합이 'm'
while True:
    # 도도의 차례
    dCard = dDeck.pop()
    dGround.append(dCard)

    # 도도의 덱이 비어있는 경우 종료
    if not dDeck:
        break

    # 도도가 이길 경우
    if dCard == 5:
        # 더미 합치기
        appendStack(2)

    # 수연이가 이길 경우
    if sGround and dGround and (sGround[-1] + dGround[-1]) == 5:
        appendStack(1)

    m -= 1
    if m == 0:
        break

    # 수연의 차례
    sCard = sDeck.pop()
    sGround.append(sCard)

    # 수연의 덱이 비어있는 경우 종료
    if not sDeck:
        break

    # 도도가 이길 경우
    if sCard == 5:
        appendStack(2)

    # 수연이가 이길 경우
    if sGround and dGround and (sGround[-1] + dGround[-1]) == 5:
        appendStack(1)

    m -= 1
    if m == 0:
        break

s, d = len(sDeck), len(dDeck)
if s == d:
    print('dosu')
elif s < d:
    print('do')
else:
    print('su')

[list time complexity]

- arr.pop(i) : O(n-i)

- arr.pop() : O(1)

- arr.append(2) : O(1)

- len(arr) : O(1)

- arr[2] : O(1) 

- arr.reverse() : O(N)

- reversed(arr) : O(1) 

- list(B) : O(len(B)) 

 

이긴 경우를 처리하는 appendStack 함수에서 시간이 오래걸렸다. 재밌는 것은 arr.reverse()는 O(N)이지만 내장함수 reversed()는 시간복잡도가 O(1)이라고 한다. 하지만 list()로 리스트화하는 과정에서 O(N)가 걸린다.

https://hyerios.tistory.com/24 

reverse()와 reversed()비교

 

3. 코드개선 

from collections import deque

n, m = map(int, input().split())
dDeck, sDeck = deque(), deque()
dGround, sGround = deque(), deque()

for _ in range(n):
    a, b = map(int, input().split())
    dDeck.appendleft(a)
    sDeck.appendleft(b)

check = True
# 도도와 수연이가 카드를 내는 총합이 'm'
while True:
    # 도도의 차례
    if check:
        dCard = dDeck.popleft()
        dGround.appendleft(dCard)
        check = False
    # 수연의 차례
    else:
        sCard = sDeck.popleft()
        sGround.appendleft(sCard)
        check = True
    
    # 도도의 덱이 비어있는 경우 종료
    if not dDeck or not sDeck:
        break

    # 도도가 이길 경우
    if (not check and dCard == 5) or (check and sCard == 5):
        # 더미 합치기
        while sGround:
            dDeck.append(sGround.pop())
        while dGround:
            dDeck.append(dGround.pop())

    # 수연이가 이길 경우
    if sGround and dGround and (sGround[0] + dGround[0]) == 5:
        # 더미 합치기
        while dGround:
            sDeck.append(dGround.pop())
        while sGround:
            sDeck.append(sGround.pop())

    m -= 1
    if m == 0:
        break

s, d = len(sDeck), len(dDeck)
if s == d:
    print('dosu')
elif s < d:
    print('do')
else:
    print('su')

 

[오픈채팅방]

https://programmers.co.kr/learn/courses/30/lessons/42888

코딩테스트 연습 - 오픈채팅방

1. 코드구현 (하)

def solution(record):
    n = len(record)
    result = []
    dic = dict()
    for i in range(n):
        data = record[i].split()
        # 입력이나 변경이 들어온 경우 
        if data[0] == 'Enter' or data[0] == 'Change':
            # 아이디 : 닉네임 변경
            dic[data[1]] = data[2]
    for data in record:
        s = ''
        behave = data.split()[0]
        id = data.split()[1]
        # 'Enter'
        if behave == 'Enter':
            s = f"{dic[id]}님이 들어왔습니다."
        # 'Leave' 
        elif behave == 'Leave':
            s = f"{dic[id]}님이 나갔습니다."
        # 'Change'  
        else:
            continue
        result.append(s)
    
    return result