20200412 알고리즘

1. JadenCase 문자열 만들기

문제 설명

JadenCase란 모든 단어의 첫 문자가 대문자이고, 그 외의 알파벳은 소문자인 문자열입니다. 문자열 s가 주어졌을 때, s를 JadenCase로 바꾼 문자열을 리턴하는 함수, solution을 완성해주세요.

제한 조건

s는 길이 1 이상인 문자열입니다.
s는 알파벳과 공백문자(” “)로 이루어져 있습니다.
첫 문자가 영문이 아닐때에는 이어지는 영문은 소문자로 씁니다. ( 첫번째 입출력 예 참고 )

입출력 예

s	return
3people unFollowed me	3people Unfollowed Me
for the last week	For The Last Week

Solution (O(n))

def solution(s):
    tmp = ''
    answer = ''
    for v in s:
        if v == ' ':
            answer += tmp + ' '
            tmp = ''
        else:
            if not tmp:
                tmp += v.upper()
            else:
                tmp += v.lower()
    answer += tmp
    return answer

2. 가장 큰 이어지는 합

정수 배열(int array)가 주어지면 가장 큰 이어지는 원소들의 합을 구하시오. 단, 시간복잡도는 O(n).

Given an integer array, find the largest consecutive sum of elements.

예제}

Input: [-1, 3, -1, 5]

Output: 7 // 3 + (-1) + 5

Input: [-5, -3, -1]

Output: -1 // -1

if __name__ == '__main__':
    a = list(map(int, input().split()))
    cur = a[0]
    res = a[0]
    for i in range(1, len(a)):
        cur = max(cur + a[i], a[i])
        res = max(res, cur)
    print(res)

3. N개의 최소 공배수

문제 설명

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

제한 사항

arr은 길이 1이상, 15이하인 배열입니다.
arr의 원소는 100 이하인 자연수입니다.

입출력 예

arr	result
[2,6,8,14]	168
[1,2,3]	6

Solution

def solution(arr):
    hash = {}
    i = 1
    while True:
        for v in arr:
            tmp = v * i
            hash[tmp] = hash.get(tmp, 0) + 1
            if hash[tmp] == len(arr):
                return tmp
        i += 1

4. 숫자의 표현

문제 설명

Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다.

1 + 2 + 3 + 4 + 5 = 15
4 + 5 + 6 = 15
7 + 8 = 15
15 = 15

자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요.

제한사항

n은 10,000 이하의 자연수 입니다.

입출력 예

n	result
15	4

Solution

def solution(n):
    cnt = 0
    tmp = 0
    for i in range(1, n+1):
        for j in range(i, n+1):
            tmp += j
            if tmp == n:
                cnt += 1
                tmp = 0
                break
            elif tmp > n:
                tmp = 0
                break
    return cnt

5. 피자배달거리

N×N 크기의 도시지도가 있습니다. 도시지도는 1×1크기의 격자칸으로 이루어져 있습니다. 각 격자칸에는 0은 빈칸, 1은 집, 2는 피자집으로 표현됩니다. 각 격자칸은 좌표(행번호, 열 번호) 로 표현됩니다. 행번호는 1번부터 N번까지이고, 열 번호도 1부터 N까지입니다. 도시에는 각 집마다 “피자배달거리”가 았는데 각 집의 피자배달거리는 해당 집과 도시의 존재 하는 피자집들과의 거리 중 최소값을 해당 집의 “피자배달거리”라고 한다.

집과 피자집의 피자배달거리는 |x1-x2|+|y1-y2| 이다. 예를 들어, 도시의 지도가 아래와 같다면

(1, 2)에 있는 집과 (2, 3)에 있는 피자집과의 피자 배달 거리는 |1-2| + |2-3| = 2가 된다. 최근 도시가 불경기에 접어들어 우후죽순 생겼던 피자집들이 파산하고 있습니다. 도시 시장은 도시에 있는 피자집 중 M개만 살리고 나머지는 보조금을 주고 폐업시키려고 합니다. 시장은 살리고자 하는 피자집 M개를 선택하는 기준으로 도시의 피자배달거리가 최소가 되는 M개의 피자집을 선택하려고 합니다.

도시의 피자 배달 거리는 각 집들의 피자 배달 거리를 합한 것을 말합니다.

▣ 입력설명 첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 12)이 주어진다. 둘째 줄부터 도시 정보가 입력된다.

▣ 출력설명 첫째 줄에 M개의 피자집이 선택되었을 때 도시의 최소 피자배달거리를 출력한다.

▣ 입력예제 1

▣ 출력예제 1

Solution

import sys
sys.stdin = open("input104.txt", "rt")

def DFS(L, s):
    global res
    if L == m:
        sum = 0
        for v in hs:
            x = v[0]
            y = v[1]
            dis = 2147000000
            for v2 in cb:
               x2 = pz[v2][0]
               y2 = pz[v2][1]
               dis = min(dis, abs(x - x2) + abs(y - y2))
            sum += dis
        if sum < res:
            res = sum
    else:
        for i in range(s, len(pz)):
            cb[L] = i
            DFS(L+1, i+1)

if __name__ == '__main__':
    n, m = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(n)]
    hs = list()
    pz = list()
    cb = [0] * m # 조합의 경우의 수
    res = 2147000000
    for y in range(n):
        for x in range(n):
            if board[y][x] == 2:
                pz.append((x,y))
            elif board[y][x] == 1:
                hs.append((x,y))

    DFS(0, 0)
    print(res)

Written by@[HongDongUk]

공부한 것을 소소하게 적는 블로그.

GitHub Facebook