[python code review] 10주차 (수 묶기, 크게 만들기, 공항)

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

1744번: 수 묶기

양수 배열과 음수 배열을 따로 두어 양수는 오름차순, 음수는 내림차순으로 정렬한 뒤 그리디하게 접근했다.

숫자 두개씩 묶어 곱할 때, 큰 수를 만들기 위한 Best case는

 

1. 양수(1이 아님) * 양수(1이 아님) 

2. 음수 * 음수

3. 음수 * 0

n = int(input())

answer = 0
zeroCount = 0
pos, neg = [], []
for _ in range(n):
    num = int(input())
    if num == 0:
        zeroCount += 1
    elif num > 0:
        pos.append(num)
    else:
        neg.append(num)

pos = sorted(pos) # 1, 2, 3, 4
neg = sorted(neg, key=lambda x:-x) # -1, -2, -3, -4

while pos:
    num1 = pos.pop()
    # 양수 하나만 남은 경우
    if not pos:
        answer += num1
    # 양수 - 양수 짝이 있다면
    else:
        num2 = pos.pop()
        # 두 양수가 1이 아니라면
        if num1 != 1 and num2 != 1:
            answer += (num1*num2)
        # 두 양수 중 하나라도 1인 경우
        else:
            answer += num1
            answer += num2
while neg:
    num1 = neg.pop()
    # 음수 하나만 남은 경우
    if not neg:
        if not zeroCount:
            answer += num1
    # 음수 - 음수 짝이 있음
    else:
        num2 = neg.pop()
        answer += (num1*num2)
print(answer)

 

 

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

2812번: 크게 만들기

유사한 문제 - https://leetcode.com/problems/remove-k-digits/

                    k개를 제거해서 가장 작은 수를 구하는 문제이다.

[stack]  

n, k = map(int, input().split())
num = list(map(int, list(input())))
stack = []

for i in range(n):
    while stack and k > 0:
        if stack[-1] < num[i]:
            stack.pop()
            k -= 1
        else:
            break
    stack.append(num[i])

while k:
    if stack:
        stack.pop()
        k -= 1

print(''.join(map(str, stack)))

코드 개선)

5 3
11211

예를 들어 이런 입력값이 들어왔을 때

for문을 돌고 남은 k개(1)만큼 stack의 마지막 위치에서 제거해야 한다.

 

for i in range(len(stack) - k):
    print(stack[i], end='')  이렇게 for문을 돌아 마지막 k개를 날리는 방식이 있었다. 

  

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

10775번: 공항

 

union-find 문제임을 파악하지 못했다. .!

gi (1 ≤ gi ≤ G) 가 주어진 경우 1~gi gate 중에서 비행기는 gi에 도킹한다.  가장 오른쪽 끝에 두어야 최대한 많은 비행기가 도킹할 수 있어서이다.

i번째 비행기의 gi 값이 주어졌을 때, find(gi)를 통해 찾은 부모 값이 비행기가 도킹할 gate 번호이다. 중요한 점은 다음 비행기가 같은 gi 값을 가질 때 부모 -1 gate에 도킹할 수 있도록 도킹 후에 부모 값을 부모-1 값으로 갱신하는 것이다.logic)

find 함수로 찾은 부모 값이 0이 아니라면 도킹해주고 찾은 부모가 부모-1 값을 가리키도록 한다.

만약 부모값이 0이라면 0 gate는 없기 때문에 종료한다.

 

[union-find]

import sys
sys.setrecursionlimit(100000)

def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]


def union(parent, a, b):
    a = find(parent, a)
    b = find(parent, b)

    if a < b:
        parent[b] = a
    else:
        parent[a] = b


G = int(sys.stdin.readline().strip('\n'))
P = int(sys.stdin.readline().strip('\n'))
gates = [i for i in range(G+1)]
answer = 0 # 도킹 횟수
for _ in range(1, P+1):
    gi = int(sys.stdin.readline().strip('\n'))
    num = find(gates, gi) # 도킹할 gate 번호
    if num != 0:
        union(gates, num, num-1)
        answer += 1
    else:
        break
print(answer)

 

 

[개선된 union-find]

import sys


def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]


answer = 0
G = int(sys.stdin.readline().strip('\n'))
P = int(sys.stdin.readline().strip('\n'))
gates = [i for i in range(G+1)]

for _ in range(P):
    gi = int(sys.stdin.readline().strip('\n'))
    num = find(gates, gi)
    if num == 0:
        break
    gates[num] = find(gates, num - 1)
    answer += 1
    
print(answer)