Class 2 (팩토리얼 0의 개수 ~ 좌표 정렬하기)

solved.ac

• 이번 포스팅은 정렬 문제 위주로 다뤄보겠습니다.

 

1676번 : 팩토리얼 0의 개수

1676번: 팩토리얼 0의 개수

• 특정 수의 팩토리얼을 계산했을 때 뒤에 0이 몇 개가 붙는지를 계산하는 문제입니다.
• 처음에는 그저 팩토리얼을 일일이 계산해 문자열로 변환한 뒤, 뒤집어서 0의 개수를 세어보았습니다.
• 그러나 이 방법은 N이 커질수록 시간적으로 비효율이고 성능이 안 좋아지기에 다른 방법을 고안해보았습니다. 아래와 같은 로직을 따라가 보겠습니다.

1. 숫자의 끝자리에 0이 생기려면 수가 10으로 나누어져야 하고, 10은 2와 5인 인수로 구성.
2. 팩토리얼 내에서 일부는 2로, 일부로 5로 나누어지며 2의 배수가 5의 배수보다 많기에 5로 나누어지는 수들만 취급.
3. 5의 배수마다 적어도 하나의 0이 끝자리에 생성. 예를 들어 5!에서는 1개, 10!에서는 2개 생성.
4. 25!, 50! 등의 인수 5가 2번 들어가게 되는 경우의 수들은 0이 추가적으로 하나 더 생성.

• 위 로직대로 코드를 구현하면 5와 그 제곱수들이 각 팩토리얼을 몇 번씩 나누는지 계산하여, 끝자리 0의 개수를 셀 수 있게 됩니다.

def count_zeros(n):
    count = 0
    divisor = 5
    while n // divisor > 0:
        count += n // divisor
        divisor *= 5
    return count

if __name__ == '__main__':
    n = int(input())
    print(count_zeros(n))

 

2751번 : 수 정렬하기 2

2751번: 수 정렬하기 2

• 전에 풀었던 '10989번: 수 정렬하기 3' 문제와 아주 유사한 문제입니다.
• 이번에는 메모리가 많이 제한되지 않기 때문에 sorted()를 사용해서 코드를 구현하시면 쉽게 푸실 수 있습니다.

import sys; input=sys.stdin.readline

if __name__ == "__main__":
    n = int(input())
    answer = [int(input()) for _ in range(n)]
    print(*sorted(answer), sep='\n')

 

7568번 : 덩치

7568번: 덩치

• 상대와 비교했을 때, 키와 몸무게 모두 상대보다 크다면 덩치가 더 크다고 판단해주는 문제입니다.
• 키와 몸무게를 각각 입력받기 때문에 이중 반복문을 통해 두 기준을 놓고 비교해주시면 간단히 풀리게 됩니다.

import sys; input = sys.stdin.readline

def calculate_ranks(info):
    n = len(info)
    ranks = [1] * n

    for i in range(n):
        for j in range(n):
            if info[i][0] < info[j][0] and info[i][1] < info[j][1]:
                ranks[i] += 1

    return ranks

if __name__ == "__main__":
    n = int(input())
    info = [tuple(map(int, input().split())) for _ in range(n)]
    
    print(*calculate_ranks(info))

 

10814번 : 나이순 정렬

10814번: 나이순 정렬

• 나이와 이름이 주어지면 나이순으로 정렬해서 출력해주는 문제입니다.
• 정렬 문제는 만능 sorted() 함수와 lambda 식만 있다면 거의 풀 수 있다고 생각합니다. 👍🏻

import sys; input=sys.stdin.readline

def read_person_info(): 
    n = int(input())
    return [tuple(input().split()) for _ in range(n)]

def sort_person_by_age(person):
    return sorted(person, key=lambda p: int(p[0]))

def print_sorted_person(person):
    for age, name in person:
        print(age, name)
        
if __name__ == '__main__':
    person = read_person_info()
    sorted_person = sort_person_by_age(person)
    print_sorted_person(sorted_person)

 

11650번 : 좌표 정렬하기

11650번: 좌표 정렬하기

• 위 문제와 아주 유사한 문제! x좌표 및 y좌표 순으로 정렬하기 때문에 따로 lambda 식을 적용해주지 않아도 sorted()가 알아서 정렬해준답니다! 🥰

import sys; input=sys.stdin.readline

def read_coord_info():
    N = int(input())
    return [tuple(map(int, input().split())) for _ in range(N)]

def sort_by_coord(coords):
    return sorted(coords)

def print_sorted_coords(coords):
    for coord in coords:
        print(coord[0], coord[1])

if __name__ == '__main__':
    coords = read_coord_info()
    print_sorted_coords(sort_by_coord(coords))