내일은 알고리즘

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

스위핑 알고리즘을 통해 풀 수 있는 문제입니다.

스위핑 알고리즘은 입력 데이터를 정렬한 뒤 한 쪽에서부터 쓸어가듯 (Sweep) 풀어가는 풀이를 말합니다.

우리는 모든 미사일을 최소한의 요격으로 처리해야합니다. 이때 하나의 요격으로 여러 미사일을 처리하려면 주어진 미사일의 구간을 동시에 관통해야 합니다. 따라서 미사일을 구간의 시작과 끝으로 정렬 한 후 한 방향으로 탐색하며 가능한 많은 미사일을 요격하도록 요격 위치를 정하면 됩니다.

a < b < c < d인 좌표 a, b, c, d가 있을 때 구간 [a, c]와 구간 [b, d]를 동시에 관통하려면 요격 미사일은 [b, c]를 통과해야 합니다. 이런 식으로 가능한 범위를 좁혀가다 불가능한 경우에 새로운 요격을 쏜다는 로직입니다. 구간을 미리 정렬해뒀기 때문에 왼쪽 좌표는 신경쓰지 않고 오른쪽 좌표만 체크해줘도 같은 결과가 나옵니다.

def solution(targets):
    answer = 1
    targets.sort(key = lambda x : (x[0], x[1]))
    right = targets[0][1]
    
    for idx in range(1, len(targets)):
        if right <= targets[idx][0]:
            right = targets[idx][1]
            answer += 1
            
        else:
            right = min(right, targets[idx][1])
    
    return answer

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

n이 10만 이하의 자연수입니다. 10만은 2진법으로 나타냈을때 1 1000 0110 1010 0000이고 길이는 17입니다.

우리가 찾아야하는 수는 n보다 크고 이진수로 나타냈을때 1의 갯수가 같은 수 중에 가장 작은 수입니다. 나올 수 있는 최악의 경우를 나이브하게 생각해봅시다.

길이가 17인 이진수에서 1의 갯수는 많아봐야 17개입니다. (10만을 넘기 때문에 실제론 1의 수가 더 적습니다.) 따라서 우리가 찾아야 하는 최악의 수는 1의 갯수가 17개인 n보다 큰 가장 작은 수입니다. 가능한 수 중에서 가장 작은 수는 11 1111 1111 1110 따위가 되겠죠. 이 값이래봐야 50만 근처입니다.

즉 나오지도 않는 최악중 최악의 경우에도 우리가 찾아봐야 하는 수의 갯수는 50만개이고 이 정도면 충분히 시간안에 탐색 할 수 있습니다. 따라서 n보다 큰 수를 모두 이진수로 바꿔가며 1의 수를 카운팅하고 1의 수가 같을때 바로 탐색을 끝냈습니다.

def solution(n):
    c = str(bin(n)[2:]).count('1')
    print(str(bin(100000)))
    while True:
        n += 1
        if str(bin(n)[2:]).count('1') == c:
            return n

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

규칙을 찾으면 풀리는 간단한 완전탐색 문제입니다. 옛날 문제라 레벨이 높게 책정된것 같네요.

카펫의 가로길이가 세로길이 이상이라는 조건이 주어져있기 때문에, 가능한 경우에 대해 테스트해보면 됩니다.

가로길이가 w 세로길이가 h라고 하면 갈색 카펫의 수는 2 * (w + h) - 4이고 노란 카펫의 수는 (w - 2) * (h - 2)입니다.

w >= h인 가능한 모든 w와 h에 대해 탐색해도 내가 시도해봐야할 w와 h 조합이 대략 w^2개이고 w는 2500 이하이기때문에 그렇게 긴 시간이 걸리지 않습니다.

def solution(brown, yellow):
    for i in range(2, brown):
        for j in range(2, brown):
            if j > i:
                break
            if brown == 2 * i + 2 * j - 4 and yellow == (i - 2) * (j - 2):
                return [i, j]

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

해시를 사용한 간단한 시뮬레이션 문제입니다. 우리가 체크해야하는 조건은 3가지 입니다.

1. 앞 사람이 말한 단어의 마지막 글자로 시작해야합니다.

2. 앞에서 나오지 않은 단어여야 합니다.

3. 끝말잇기가 진행된 차례 수와, 말한 참가자의 번호를 알아야 합니다.

1번 조건은 제일 첫 참가자를 제외하고 이전에 나온 단어의 마지막 글자를 저장하고 비교하여 구현할 수 있습니다.

2번 조건은 단어가 나올때 마다 이를 set, map 등 문자열을 key로 접근할 수 있는 해시 자료구조에 넣어 구현할 수 있습니다.

3번 조건은 어차피 단어를 입력된 순서대로 봐야하므로 Iterator나 forEach 구문 대신 idx를 사용해 단어에 접근하고, 참가자 번호는 n으로 나머지연산을 취해 n개의 값을 돌도록 구현했습니다.

def solution(n, words):
    answer = [0, 0]
    b = words[0][-1]
    idx = 1
    who = 1
    duple = {}
    duple[words[0]] = 1
    
    while idx < len(words):
        if words[idx] in duple or words[idx][0] != b:
            answer = [who + 1, (idx // n) + 1]
            break
        else:
            b = words[idx][-1]
            duple[words[idx]] = 1
            who = (who + 1) % n
            idx += 1
    
    return answer

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

문제에서 요구한 그대로 구현하면 쉽게 풀릴 것 같지만, 입력 문자열의 길이가 100만이기 때문에 좀 더 효율인 방법이 필요합니다. 

예를 들어 입력이 10일때 요구한 그대로 문자열을 비교한다면 알파벳이 2개씩 사라지므로 5번의 시행이 필요하고 그 때마다 10, 8, 6, 4, 2 길이의 문자열을 자르고 이어붙여야합니다. 문자열의 길이가 길수록 기하급수적으로 커지겠죠.

Stack, 혹은 List 등의 자료구조를 활용하여 맨 뒤의 알파벳만 비교할 수 있습니다. 이 경우엔 정확히 문자열의 길이만큼만 다루면 됩니다. Python 기준으로 List를 Stack과 유사하게 사용할 수 있으므로 이를 사용해 알파벳을 넣어주고, 만약 맨 뒤의 알파벳(즉 나와 맞닿은 알파벳)이 같다면 지워주는 식으로 풀 수 있습니다.

def solution(s):
    st = []
    
    for c in s:
        if len(st) > 0 and st[-1] == c:
            st.pop()
        else:
            st.append(c)
    
    return 1 if len(st) == 0 else 0

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

keymap을 돌며 각 알파벳 별로 키보드를 눌러야 하는 최소 횟수를 기록한 뒤 target의 알파벳 하나씩 필요한 횟수를 누적합해주고, 불가능한 경우가 있으면 바로 -1을 넣어주면 됩니다.

각 알파벳 별 최소 횟수는 set, map 등의 자료구조나 알파벳의 ASCII를 이용한 배열로 저장할 수 있습니다.

def solution(keymap, targets):
    answer = []
    keyset = {}
    
    for key in keymap:
        for i in range(len(key)):
            if key[i] not in keyset or keyset[key[i]] > i:
                keyset[key[i]] = i + 1

    for target in targets:
        n, f = 0, True
        for t in target:
            if t not in keyset:
                answer.append(-1)
                f = False
                break
            n += keyset[t]
        if f:
            answer.append(n)
    
    return answer

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

약간의 그리디 느낌이 있는 문제입니다. 카드 뭉치 두개의 인덱스를 따로 관리하면서 지금 필요한 단어가 있는 뭉치를 골라주면 됩니다. 두 뭉치에 중복되는 단어가 없기 때문에 필요한 단어가 있는 카드 뭉치를 사용하는게 반드시 최선의 선택임이 보장됩니다.

flag를 사용해 최종에서 return 해주어도 되고, 불가능한 경우가 생기면 바로 "No"를 return하고 문장을 끝까지 완성한다면 "Yes"를 return 하는 식으로 구현해도 됩니다.

def solution(cards1, cards2, goal):
    f, i, j = True, 0, 0
    
    for g in goal:
        if i < len(cards1) and cards1[i] == g:
            i += 1
        elif j < len(cards2) and cards2[j] == g:
            j += 1
        else:
            f = False
            break
    
    return "Yes" if f else "No"
    
    
    
# solution 2
def solution2(cards1, cards2, goal):
    i, j = 0, 0
    
    for g in goal:
        if i < len(cards1) and cards1[i] == g:
            i += 1
        elif j < len(cards2) and cards2[j] == g:
            j += 1
        else:
            return "No"
    
    return "Yes"

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

카이사르 암호를 응용한 문제입니다. skip에 포함된 알파벳은 넘긴 횟수로 세지 않는것과 z 다음이 a인것만 주의하고,

ord()와 chr() 같은 Python 내장 함수를 사용하면 쉽게 풀 수 있습니다. 

def solution(s, skip, index):
    answer = ''
    
    for c in s:
        i = ord(c)
        j = index
        while j > 0:
            i += 1
            if i > ord('z'):
                i = ord('a')
            if chr(i) in skip:
                j += 1
            j -= 1
        answer += chr(i)
    
    return answer