(파이썬 S/W 문제해결 기본) Linked List - 5108번 5110번 5120번 5122번

작성일 2019-09-05 In ALGORITHM 🎯 , SW 아카데미 댓글:

5108번 - 숫자 추가

시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

list.insert(self, index, object) 함수를 사용하여 쉽게 리스트의 해당 인덱스에 숫자 삽입

def addNum(m):
for \_ in range(M): # 추가할 인덱스와 숫자 입력
idx, num = map(int, input().split())
mySeq.insert(idx, num)

def printNum(l):
return mySeq[l]

T = int(input())

for test_case in range(1, T+1): # 수열의 길이 N, 추가 횟수 M, 출력할 인덱스 번호 L
N, M, L = map(int, input().split())
mySeq = [int(num) for num in input().split()]

    addNum(M)
    ans = printNum(L)

    print('#{} {}'.format(test_case, ans))

5110번 - 수열 합치기

시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

테스트 케이스 10개 중 9개만 통과하고 1개는 제한시간 초과가 뜬다

def mergeSeqLists():
finalSeq = []

    finalSeq.extend(myLists[0])

    for idx in range(1, M):
        ptr = len(finalSeq)
        for i, num in enumerate(finalSeq):
            if myLists[idx][0] < num:
                ptr = i
                break

        finalSeq = finalSeq[:ptr] + myLists[idx] + finalSeq[ptr:]

    return finalSeq

T = int(input())

for test*case in range(1, T+1): # 수열의 길이 N, 수열의 개수 M
N, M = map(int, input().split()) # 전체 수열을 저장할 리스트
myLists = [[int(num) for num in input().split()] for * in range(M)]

    ans = mergeSeqLists()

    print('#{} '.format(test_case), end='')
    print(' '.join(str(n) for n in ans[-1:-11:-1]))
    #print('#{} {}'.format(test_case, ans[:10]))

def mergeSeqLists():
first_seq = list(map(int, input().split()))

    for _ in range(M - 1):
        seq_len = len(first_seq)
        next_seq = list(map(int, input().split()))

        for i in range(seq_len):
            if first_seq[i] > next_seq[0]:
                first_seq[i:0] = next_seq
                break

        if seq_len == len(first_seq):
            first_seq.extend(next_seq)

    return first_seq

T = int(input())
for test_case in range(1, T+1):
N, M = map(int, input().split())

    ans = mergeSeqLists()

    print('#{} '.format(test_case), end='')
    print(' '.join(str(n) for n in ans[-1:-11:-1]))

5120번 - 암호

시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

pivot을 정할 때 pivot = (pivot + M) % len(pwd) 이렇게 나머지를 이용하면 리스트의 시작과 끝이 0으로 똑같다. pivot이 마지막에 있을 때만 특수한 조건으로 해당 값을 더하기 때문에 주의해야한다.

def crypto(pwd):
pivot = 0
start_num = pwd[pivot]

    for _ in range(1, K + 1):
        pivot += M

        if pivot > len(pwd):
            pivot -= len(pwd)

        if pivot == len(pwd):
            pwd.append(pwd[-1] + start_num)
        else:
            pwd.insert(pivot, pwd[pivot - 1] + pwd[pivot])

    return pwd

T = int(input())

for test_case in range(1, T + 1):
N, M, K = map(int, input().split())
password = list(map(int, input().split()))

    encrypted = list(reversed(crypto(password)))

    print(f'#{test_case}', end=' ')
    print(*encrypted[:10])

5122번 - 수열 편집

시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

편집이 끝난 후 L이 존재하지 않는 경우를 주의

def modify*seq():
for * in range(M):
command, \*args = input().split()

        if command == 'I':
            seq.insert(int(args[0]), int(args[1]))
        elif command == 'D':
            seq.pop(int(args[0]))
        elif command == 'C':
            seq[int(args[0])] = int(args[1])

    try:
        return seq[L]
    except IndexError:
        return -1

T = int(input())

for test_case in range(1, T+1): # 수열의 길이 N, 추가 횟수 M, 출력할 인덱스 번호 L
N, M, L = map(int, input().split())
seq = list(map(int, input().split()))

    print(f'#{test_case} {modify_seq()}')

(파이썬 S/W 문제해결 기본) Queue - 5097번 5105번 5099번 5102번

작성일 2019-09-02 In ALGORITHM 🎯 , SW 아카데미 댓글:

5097번 - 회전

시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

리스트 내장함수인 pop()과 append()로 쉽게 해결

T = int(input())

for test_case in range(1, T+1): # 입력 길이 N, 회전 수 M
N, M = map(int, input().split())
seq_lst = [num for num in input().split()]

    # M번 반복
    for _ in range(M):
        # 맨 앞 원소를 빼서 pop(), 맨 뒤로 추가 append()
        seq_lst.append(seq_lst.pop(0))

    print('#{} {}'.format(test_case, seq_lst))

5105번 - 미로의 거리

시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

지난 미로 문제는 DFS, 이번에는 BFS로 해결
DFS는 재귀적으로, BFS는 반복을 통해 접근

def BFS(x, y): # 현재 좌표 등록
path.append((x, y))
visited.append((x, y))

    while path:
        # 경로 맨 앞 원소 제거
        cur_x, cur_y = path.pop(0)

        for i in range(4):
            next_x = cur_x + dx[i]
            next_y = cur_y + dy[i]

            if (next_x, next_y) not in visited and (0<=next_x<N and 0<=next_y<N) and maze[next_y][next_x] != 1:
                if maze[next_y][next_x] == 3:
                    return path_len[cur_x][cur_y]

                path.append((next_x, next_y))
                visited.append((next_x, next_y))
                path_len[next_x][next_y] = path_len[cur_x][cur_y] + 1

def findStart():
for y in range(N):
for x in range(N):
if maze[y][x] == 2:
return x, y

T = int(input())

for test*case in range(1, T+1): # 미로의 크기
N = int(input())
maze = [[int(num) for num in input()] for * in range(N)]

    # 시작점 찾기
    startX, startY = findStart()

    # 방문체크, 경로 큐, 경로 길이 리스트
    visited, path, path_len = [], [], [[0]*N for _ in range(N)]

    # 시계방향 (우, 하, 좌, 상)
    dx = [1, 0, -1, 0]
    dy = [0, -1, 0, 1]

    ans = BFS(startX, startY)
    if ans is None:
        ans = 0

    print('#{} {}'.format(test_case, ans))

5099번 - 피자 굽기

시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

화덕을 돌려가며 피자를 굽자

def pizza(): # 초기 화덕 큐
oven = [] # 피자 번호
pNum = 0

    # (init) 빈 화덕에 피자 채우기
    for _ in range(N):
        oven.append([C[pNum], pNum])
        pNum += 1

    # (반복) 오븐에 마지막 피자만 남을 때 까지
    while len(oven) != 1:
        # 현재 화덕 확인으로 치즈가 반 녹음
        oven[0][0] = oven[0][0] // 2

        # 치즈가 다 녹았다면
        if oven[0][0] == 0:
            # 꺼내고
            oven.pop(0)
            # 피자가 남았다면
            if pNum != len(C):
                # 화덕에 넣어준다
                oven.append([C[pNum], pNum])
                pNum += 1
        # 덜 녹았으면 회전
        else:
            oven.append(oven.pop(0))

    return oven[0][1] + 1

T = int(input())

for test_case in range(1, T+1): # 화덕의 크기 N, 피자 개수 M
N, M = map(int, input().split()) # 치즈의 양 C
C = [int(amount) for amount in input().split()]

    print('#{} {}'.format(test_case, pizza()))

5102번 - 노드의 거리

시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

전역변수 ‘ans’를 사용하지 않고 BFS() 함수에서 return path_len[]를 하면 테스트 케이스 중 하나가 오답이 된다
간선이 없는 경우인거 같은데…

def makeGraph():
graph = {key + 1: set() for key in range(V)}

    for _ in range(E):
        key, val = map(int, input().split())
        graph[key].add(val)
        graph[val].add(key)

    return graph

def BFS(s, g):
global ans
path.append(s)
visited[s] = True

    while path:
        node = path.pop(0)

        for next_node in myGraph[node]:
            if not visited[next_node]:
                path.append(next_node)
                visited[next_node] = True
                path_len[next_node] = path_len[node] + 1

                if next_node == g:
                    ans = path_len[next_node]
                    return
    return

T = int(input())

for test_case in range(1, T+1):
V, E = map(int, input().split())
myGraph = makeGraph()
S, G = map(int, input().split())

    path = []
    visited = [False] * (V+1)
    path_len = [0] * (V+1)
    ans = 0
    BFS(S, G)

    print('#{} {}'.format(test_case, ans))

(파이썬 S/W 문제해결 기본) Stack2 - 4874번 4875번 4880번 4881번

작성일 2019-08-24 In ALGORITHM 🎯 , SW 아카데미 댓글:

4874번 - Forth

시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

Forth는 기본 사칙연산 +, -, *, / 4가지만 제공
문제에서 정확하게 어떤 연산자를 제공하는지 명시되었으면 더 좋을 것 같음
정수 나눗셈 연산자 주의!(이거 때문에 오류 찾는 시간이 좀 걸림)

def operator(op, n1, n2): # 나눗셈은 '//' 연산자를 사용해야 하는 것을 주의
return {'+':n1+n2, '-':n1-n2, '*':n1*n2, '/':n1//n2}[op]

def calc_code(code):
stack = []

    for token in code:
        if token == '.':
            if len(stack) == 1:
                return stack.pop()
            # 연산자 수가 부족하여 stack에 숫자가 남은 경우
            else:
                return 'error'

        if token.isdigit():
            stack.append(token)
        else:
            try:
                num2, num1 = int(stack.pop()), int(stack.pop())
                stack.append(operator(token, num1, num2))
            # stack에 계산에 필요한 숫자가 부족한 경우 예외 처리
            except IndexError:
                return 'error'

T = int(input())

for test_case in range(1, T+1): # 연산코드 입력
operation_code = list(input().split())
ans = calc_code(operation_code)

    print('#{} {}'.format(test_case, ans))

4875번 - 미로

시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

백트래킹을 활용한 미로 탐색

def backtracking(x, y): # 시계방향 (우, 하, 좌, 상)
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]
global isPath

    if maze[y][x] == 3:
        isPath = 1
        return

    visited.append((x, y))
    #path.append((x, y))
    for i in range(4):
        nextX = x + dx[i]
        nextY = y + dy[i]

        # 방문하지 않았고, 범위를 벗어나지 않으며, 벽(1)이 아닌 곳
        if (nextX, nextY) not in visited and (0<=nextX<N and 0<=nextY<N) and maze[nextY][nextX] != 1:
            backtracking(nextX, nextY)
            #path.pop()

def findStart():
for y in range(N):
for x in range(N):
if maze[y][x]==2:
return x, y

T = int(input())

for test*case in range(1, T+1): # 미로의 크기
N = int(input())
maze = [[int(num) for num in input()] for * in range(N)]

    # 시작점 찾기
    startX, startY = findStart()

    visited = []
    path = []
    isPath = 0
    backtracking(startX, startY)

    print('#{} {}'.format(test_case, isPath))

4880번 - 토너먼트 카드게임

시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

이긴 카드의 번호가 아닌 이긴 학생의 번호를 출력해야 함

def winner(left, right):
player1 = card_no[left-1]
player2 = card_no[right-1]
win = ''

    if player1 < player2:
        if player2 == 3 and player1 == 1:
            win = left
        else:
            win = right
    elif player1 > player2:
        if player1 == 3 and player2 == 1:
            win = right
        else:
            win = left
    elif player1 == player2:
        win = left

    return win

def tournament(start, end):
mid = (start+end)//2

    if start == end:
        return start

    left = tournament(start, mid)
    right = tournament(mid+1, end)
    return winner(left, right)

T = int(input())

for test_case in range(1, T+1): # 인원수 입력
N = int(input()) # 카드 입력
card_no = [int(num) for num in input().split()]

    # 절반씩 분할정복하는 재귀호출 함수
    ans = tournament(1, N)

    print('#{} {}'.format(test_case, ans))

4881번 - 배열 최소 합

시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

n-queen 문제와 비슷

def calc_sum(y):
global sub_sum, min_sum

    if sub_sum > min_sum:
        return

    if y == N:
        if sub_sum < min_sum:
            min_sum = sub_sum
        return

    for x in range(N):
        if not visited[x]:
            visited[x] = True
            sub_sum += array_2d[y][x]
            calc_sum(y+1)
            visited[x] = False
            sub_sum -= array_2d[y][x]

T = int(input())

for test*case in range(1, T+1): # 배열 길이 입력
N = int(input())
array_2d = [[int(num) for num in input().split()] for * in range(N)]

    # 합의 최대
    sub_sum, min_sum = 0, 10*10
    # 방문 체크
    visited = [0] * N
    calc_sum(0)

    print('#{} {}'.format(test_case, min_sum))

NUNU

개인적으로 공부하면서 정리한 내용들을 블로그에 남기고 있습니다.

RSS