내일은 알고리즘

https://school.programmers.co.kr/learn/courses/30/lessons/72410

문자열이나 문자의 비교, 아스키코드를 알아야 쉽게 풀 수 있는 시뮬레이션 문제입니다.

입력된 문자열을 7단계를 거쳐 요구하는 조건에 맞는 문자열로 변형시켜야 하는데, 한 함수 안에서 동작해도 상관 없지만 구현시에 헷갈리지 않기 위해 7단계를 step 1~7로 쪼개어 각각 구현했습니다.

def solution(new_id):
    
    id = step1(new_id)
    id = step2(id)
    id = step3(id)
    id = step4(id)
    id = step5(id)
    id = step6(id)
    id = step7(id)

    answer = ""
    for i in id:
        answer += i
    return answer

def step1(id):
    result = []
    for i in id:
        character = ord(i)
        if(65 <= character and character <= 90):
            result.append(chr(character + 32))
        else:
            result.append(i)

    return result

def step2(id):
    result = []
    for i in id:
        character = ord(i)
        if((97 <= character and character <= 122) or (48 <= character and character <= 57) or character == 45 or character == 46 or character == 95):
            result.append(i)

    return result

def step3(id):
    result = []
    before = ''
    for i in id:
        if(before == '.' and i == '.'):
            continue
        else :
            result.append(i)
            before = i

    return result

def step4(id):
    if(len(id) > 0 and id[0] == '.'):
        id = id[1:]
    if(len(id) > 0 and id[-1] == '.'):
        id = id[0:-1]
    return id

def step5(id):
    if(len(id) == 0):
        return ['a']
    return id

def step6(id):
    if(len(id) > 15):
        id = id[0:15]
        if(len(id) > 0 and id[-1] == '.'):
            id = id[0:-1]
    return id

def step7(id):
    while(len(id) < 3):
        id.append(id[-1])
    return id


input = ["...!@BaT#*..y.abcdefghijklm","z-+.^.","=.=","123_.def","abcdefghijklmn.p"]
# input = ["...!@BaT#*..y.abcdefghijklm"]

for i in range(len(input)):
    print(solution(input[i]))

https://school.programmers.co.kr/learn/courses/30/lessons/67256

조금 머리를 써야하는 시뮬레이션 문제입니다.

왼손과 오른손의 엄지를 써서 누르는 방법이 정해진 번호 (1,4,7,*)과 (3,6,9,#)은 그대로 진행하면 되지만 중앙의 (2,5,8,0) 번호는 현재 상황에서 더 가까운 손가락을 사용해야 합니다.

저는 각 번호마다 해당 번호와의 거리를 미리 계산해놓고, 현재 손가락의 위치를 통해 거리를 비교하는 식으로 구현했습니다.

def solution(numbers, hand):
    distance = [[3,1,0,1,2,1,2,3,2,3,4,4],[2,2,1,2,1,0,1,2,1,2,3,3],[1,3,2,3,2,1,2,1,0,1,2,2],[0,4,3,4,3,2,3,2,1,2,1,1]]
    # 순서대로 2,5,8,0과 각 버튼(0~9,*,#)의 거리
    flag = (hand == "right")
    left = 10
    right = 11
    answer = ''

    for i in numbers :
        if(i == 1 or i == 4 or i == 7):
            left = i
            answer += 'L'
        elif(i == 3 or i == 6 or i == 9):
            right = i
            answer += 'R'
        else : 
            target = 0
            if(i == 5):
                target = 1
            if(i == 8):
                target = 2
            if(i == 0):
                target = 3
            
            if(distance[target][left] == distance[target][right]):
                if(flag) : 
                    right = i
                    answer += 'R'
                else : 
                    left = i
                    answer += 'L'
            elif(distance[target][left] < distance[target][right]):
                    left = i
                    answer += 'L'
            else : 
                    right = i
                    answer += 'R'
    return answer

numbers = [[1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5],[7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2],[1, 2, 3, 4, 5, 6, 7, 8, 9, 0]]
hand = ["right", "left", "right"]

for i in range(0,3):
    print(solution(numbers[i],hand[i]))

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

예전에 풀었던 문제들을 복습하면서 정리중입니다.

아이디어를 떠올리기 어렵지만 구현은 간단한 문제입니다.

A에 있는 수와 B에 있는 N개의 수를 하나씩 뽑아 곱해 더하고 그 누적합을 최소로 만드는 문제입니다.

해결방법은 간단합니다.

A에서 가장 작은수를 B에서 가장 큰수, 그 다음으로 작은 수를 다음으로 큰 수와 곱하는 식으로 계산해주면 됩니다.

문제의 조건에선 B를 재배열하지 말라고 하지만... 요구하는 정답이 A의 배열이었다면 몰라도 누적합이기 때문에 그냥 신경쓰지 않고 정렬해줘도 상관없습니다.

아이디어가 맞는지 생각해 보겠습니다.

A에서 기존의 가장 작은 수를 a 라고 하면 a가 아닌 어떤 수는 a+c로 나타낼 수 있을겁니다. (a와 같을 수 있음, 즉 c≥0)

B에서 가장 큰 수를 b라고 하면 b가 아닌 어떤 수는 b-d로 나타낼 수 있을겁니다. (마찬가지로 d≥0)

아이디어가 틀리다면 다른 순서로 수를 배열했을때 합이 더 작아져야합니다.

다른 순서로 수를 배열한다면 기존의 (a * b) + ((a+c) * (b-d))가 (a * (b-d)) + ((a+c) * b)로 대체될겁니다.

각 식을 계산해 풀어주면 1. ab + ab + cb - ad - cd 와 2. ab - ad + ab + cb가 됩니다.

다른 수를 선택해서 합이 더 작아지는 케이스가 있다면 1번 식보다 2번 식이 더 작아야합니다.

즉 1번식 - 2번식 > 0 이 성립해야하는데, 계산해보면 cd < 0이 되고 c와 d는 각각 0 이상의 정수이기 때문에 성립하지 않습니다. (c와 d가 둘 다 0이라면 같은 크기일 순 있지만, 이때의 선택도 정답 조합의 하나가 됩니다.)

따라서 A에서 가장 작은 a와 B에서 가장 큰 b를 곱하는게 최소값이 되는 조합이고, 이렇게 fix된 a와 b를 제외한 A' B'로 다시 최소합을 구한다고 생각하면 같은 증명으로 A와 B의 크기가 1이 될 때까지 적용이 가능합니다. 

둘의 크기가 1이라면 당연히 곱할 수 있는 방법이 하나밖에 없겠죠.

따라서 위와같이 정렬된 A와 역정렬된 B를 순서대로 곱한 합이 최소값입니다.

(제가 수학전공이 아니기 때문에 증명은 틀릴 수 있습니다... )

n = int(input())
A = list(map(int, input().split(' ')))
B = list(map(int, input().split(' ')))

A.sort()
B.sort(reverse=True)

answer = 0

for i in range(0,n):
    answer += int(A[i]) * int(B[i])

print(answer)

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

https://nodingco.tistory.com/50

접근 방법은 위의 JAVA 풀이에서 확인할 수 있습니다.

Python에서 String을 List로 바꿔주는 메소드는 split()이나 List의 생성자인 list()를 이용하면 됩니다. Python의 경우엔 정수 나눗셈의 몫을 구하고 싶을때 // 연산자를 활용할 수 있습니다.

def solution(s):
    # strArr = s.split('')
    strArr = list(s)

    answer = len(strArr)

    for i in range(1, len(strArr)//2 + 1):
        count = i
        idx = 0
        duple = 0
        for now in range(i, len(strArr) - (len(strArr) % i), i ):
            flag = True
            for j in range(0, i):
                if (strArr[idx + j] != strArr[now + j]):
                    flag = False
                    break
            if (flag):
                if(duple == 0):
                    duple = 2
                else:
                    duple +=1
            else :
                idx = now

                if (duple // 100 != 0):
                    count += 3
                elif (duple // 10 != 0):
                    count += 2
                elif (duple != 0):
                    count+=1
                count += i
                duple = 0
        if(duple // 100 != 0):
            count += 3
        elif (duple // 10 != 0):
            count += 2
        elif (duple != 0):
            count+=1
        
        duple = 0
        answer = min(answer, count + (len(strArr) % i))

    return answer

input = ["aabbaccc","ababcdcdababcdcd","abcabcdede","abcabcabcabcdededededede","xababcdcdababcdcd"]

for i in range(5):
    print(solution(input[i]))

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

https://nodingco.tistory.com/45

접근 방법은 위의 JAVA 풀이에서 확인할 수 있습니다.

def solution(lottos, win_nums):
    grade = [ 6, 6, 5, 4, 3, 2, 1 ]
    answer = []
    p = 0
    c = 0
    
    for i in range(6):
        if(lottos[i] == 0):
            p+=1
        else:
            for j in range(6):
                if(lottos[i] == win_nums[j]):
                    c+=1
    answer.append(grade[p+c])
    answer.append(grade[c])
    
    return answer

lottos = [ 44, 1, 0, 0, 31, 25 ]
win_nums = [ 31, 10, 45, 1, 6, 19 ]

print(solution(lottos, win_nums))

문제풀이 루틴에 관한 글은
https://nodingco.tistory.com/23  <- 여기를 참고해주세요!

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

1. 이해 (5분) - 2분

01knapsack 유형의 문제입니다. 워낙 유명한 DP문제라 따로 설명은 하지 않겠습니다.

풀이방법은 간단합니다. 우선 어떤 동전의 값이 V이라고 하면 당연히 V금액을 만드는것이 가능합니다.

그리고 만약 M이라는 금액을 만드는 방법이 있다면 우리는 V짜리 동전 하나를 더해 간단히 M+V를 만들 수 있습니다.

2. 계획 (5분) - 2분

위에서 이해한 개념을 바탕으로 계획을 세워봅시다.

사용가능한 동전의 값들을 입력받고, 크기 M+1짜리 배열을 만듭니다.

우리는 이 배열에 0원부터 순차적으로 그 금액에 가능한 가짓수를 구하고 최종적으로 M원을 만들 수 있는 가짓수를 구할것입니다.

동전의 갯수 N만큼 반복해야하는 작업은 이렇습니다.

1. V짜리 동전을 가지고 금액 V를 만드는건 당연히 가능하다. (1가지 방법)

2. 만약 M이라는 금액을 만드는 방법이 X개 있다면, 그 X가지 방법에 V짜리 동전을 더해 M+V금액을 만들 수 있다. (X가지 방법) 

이 두가지 작업을 마치면 최종적으로 주어진 동전들로 M원을 만들 수 있는 방법의 수를 구할 수 있습니다.

3. 검증 (5분) - 1분

만약 중복조합같은 방식으로 문제를 풀려고 했다면 문제가 생겼겠지만, 구상한 방식에서 M짜리 배열의 크기는 1만에 불과하고 동전과 테스트케이스도 20,10개이므로 시간초과가 발생하지는 않을 것 같습니다.

4. 풀이 (30분) - 13분

파이썬을 사용했고 문제의 풀이방법만 알고 있다면 간단히 작성가능한 코드라 금방 끝났습니다.

5. 채점, 디버깅 (+5분)

첫 제출에서 런타임에러가 발생했습니다! 동전의 값어치와 금액 M 사이에 대소관계가 없어 발생한 Index에러였습니다.

(만약 만들 금액이 30원인데, 100원짜리, 500원짜리 동전을 사용하려고 하면..? DP배열의 index를 넘어간다!) 

동전의 값어치가 금액보다 클때 반복문을 통과하는 조건문을 만들어주어 통과했습니다.

import sys

T = int(sys.stdin.readline())
sb = ""

for t in range(T):
    N = int(sys.stdin.readline())
    coin = list(map(int, sys.stdin.readline().split(' ')))
    M = int(sys.stdin.readline())
    dp = [0] * (M + 1)

    for n in range(N):
        dis = coin[n]
        if(dis > M):
            continue
        dp[dis] += 1
        
        for i in range(dis+1, M+1):
            dp[i] += dp[i-dis]

    sb += str(dp[M]) + "\n"

print(sb)

문제풀이 루틴에 관한 글은
https://nodingco.tistory.com/23  <- 여기를 참고해주세요!

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

JAVA로 푼 문제를 Python으로 다시 작성한 문제입니다.

풀이방법과 주의사항, JAVA 정답 코드를 보고 싶으신 분은 아래 링크를 확인해주세요!

https://nodingco.tistory.com/28

import sys

N,M = map(int, sys.stdin.readline().split(' '))
staffs = list(map(int, sys.stdin.readline().split(' ')))

left = 0
right = min(staffs) * M

while(left+1 < right):
    center = (left + right)//2
    balloon = 0

    for n in range(N):
        balloon += center//staffs[n]
    
    if(balloon >= M):
        right = center
    else :
        left = center

print(right)

문제풀이 루틴에 관한 글은
https://nodingco.tistory.com/23  <- 여기를 참고해주세요!

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

1. 이해 (5분) - 1분

문제에서 제시하는 조건은 30의 배수이지만, 사실상 3의 배수라고 생각을 해도 무방합니다.

3의 배수가 갖는 특징은 자릿수의 숫자를 모두 더하면 3의 배수가 나온다는 점입니다.

3, 6, 9, 12(3), 15(6)... 10진법에서 올림연산이 발생할때 3의 경우는 무조건 1만큼이 부족하기 때문에 앞의 자릿수는 1이 오르고 자기 자릿수에선 1만큼이 부족해지면서 합이 유지되는겁니다.

2. 계획 (5분) - 1분

문제에선 3의 배수가 아닌 30의 배수를 요구했으므로, 최소한 한개의 0이 필요합니다.

또한 가장 큰 수를 출력하라고 했으니 각 자리의 숫자들을 내림차순으로 정렬해 출력할 필요도 있겠네요.

다만 이 모든 계산은 이렇게 만들어진 수가 30의 배수일 경우, 즉 각 자릿수의 합이 3의 배수일 때만 해주면 됩니다.

3. 검증 (5분) - 1분

예외가 발생할 경우는 0 같은 특이한 수가 입력될때일텐데요, 조건에서 숫자가 0으로 시작하지 않는다고 하니 문제되지 않을것 같습니다.

각 자리의 숫자들을 내림차순으로 정렬한 수(만들 수 있는 가장 큰 수)도 3의 배수가 맞을까요?

예시를 떠올려보면 12345이나 54321이나 전부 3의 배수입니다! 각 자릿수의 합이 3의 배수기만 하면 전부 3의 배수인게 확실합니다.

4. 풀이 (30분) - 10분

오랜만에 Python을 사용하다보니 살짝 버벅였지만 작성에 크게 어려운 부분은 없었습니다.

짧은 코드인데도 시간이 꽤 걸렸네요.

5. 채점, 디버깅 (+@)

3의 배수가 갖는 특징을 알고 Python 언어를 알면 쉽게 풀 수 있는 문제여서 한번에 통과했습니다.

문제 풀이에는 총 15분 가량이 걸렸습니다.

정답코드입니다.

N = list(input())
N = sorted(N, reverse=True)

if N[-1] != '0' :
    print(-1)
else:
    sum = 0
    for i in N:
        sum += int(i)
    if sum % 3 != 0 :
        print(-1)
    else :
        print(''.join(N))