내일은 알고리즘

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

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

아주 간단한 set, map을 활용하는 기본 문제입니다.

name과 yearning을 순회하며 name을 key로 추억점수를 저장하고, photo[i]마다 추억점수가 존재하는 이름이라면 그 값을 합해주면 쉽게 풀립니다.

def solution(name, yearning, photo):
    answer = []
    m = {}
    for i in range(len(name)):
        m[name[i]] = yearning[i]
    
    for pho in photo:
        s = 0
        for p in pho:
            if p in m:
                s += m[p]
        answer.append(s)
    return answer

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

set, map 등의 hash 자료구조를 이용해 풀이했습니다. 아주 효율적인 코드는 아니지만 시간 내에 잘 돌아갑니다.

접근 아이디어는 선수의 이름과 현재 등수가 서로를 양방향으로 지목해 바꿉니다. 어떤 선수의 이름이 불린다면, 그 선수의 등수를 알게 되고, 그 선수의 앞 등수를 알게 되어 이름을 알게되는 구조입니다.

등수와 이름을 모두 안다면 호명된 선수와 앞 선수의 순위를 바꾸어 갱신하면 됩니다.

def solution(players, callings):
    n = len(players)
    
    ranking = []
    idxset = {}
    for i in range(n):
        ranking.append(players[i])
        idxset[players[i]] = i
    
    for c in callings:
        t = idxset[c]
        f = ranking[t - 1]
        
        ranking[t - 1] = c
        ranking[t] = f
        
        idxset[c] = t - 1
        idxset[f] = t
        
    return ranking

코딩테스트와 PS를 연습하며 자주 당했고, 본 실수들을 적어봅니다.

여기 적힌 내용들은 정말 '실수'라서 올바른 솔루션을 작성하고서도 틀리는 안타까운 경우들입니다. 제출 전에 잘 체크하여 쓸데없는 시간낭비나 불합격을 줄이도록 합시다.

1. 쓸데없는 출력문 지우기

디버깅을 하거나 작성한 코드가 제대로 돌아가는지 확인하기 위해서 코드 중간 중간에 print문을 넣어놓는 경우가 있습니다. 

출력으로 결과를 제출하는 백준의 경우엔 해당 print문을 주석처리하지 않으면 99% 확률로 오답처리되고, 프로그래머스나 Leetcode처럼 데이터를 return하는 경우에도 print로 인한 시간초과가 발생하기 쉽습니다. 실제 기업 채용 코딩테스트에서도 비슷하게 작동하겠죠?

문제를 잘 풀어놓고 틀리지 않으려면 제출 전에 주석처리나 지우는 작업을 했는지 반드시 체크해야합니다.

2. 정답 갱신 체크하기

호출한 재귀 함수나 반복문 내부에서 정답을 잘 구해놓고 return 하는 answer값을 변경하지 않아 틀리는 경우가 종종 있습니다. 또는 최솟값, 최댓값을 요구하는 문제에서 min이나 max함수를 제대로 사용하지 않아 틀리는 경우가 많습니다.

특히 예시에서 보여주는 입력이 해당 오류를 체크할 수 없는 경우에 잘 풀어놓고 정말 허망하게 문제를 틀리는 경우가 많습니다. 채점 결과를 공개하지 않는 테스트가 늘어나는 흐름에서 응시자가 놓치면 안되는 포인트입니다.

예를들어, 양의 정수가 담겨있는 배열에서 가장 큰 정수가 위치한 인덱스를 return하는 쉬운 문제에서 솔루션 코드를 이렇게 짰다고 해봅시다.

def solution(arr):
   answer = 0
   n = -1
    
   for i in range(len(arr)):
      if arr[i] > n:
      	 answer = i
   	
    return answer

예시 케이스로 [1, 2, 3, 4, 5]가 주어진다면 가장 큰 정수인 5가 위치한 인덱스 4를 return합니다.

하지만 이 솔루션은 틀린 솔루션입니다. 입력으로 [2, 3, 4, 5, 1]이 들어와도 정답인 3 대신 4를 return합니다.

i 번째 수가 더 큰지를 판단하고 나서 값을 갱신해주지 않았기 때문에 조건문이 항상 -1보다 더 큰지를 비교하고 맨 뒤 인덱스를 return하기 때문입니다. 

.

또는 가장 큰 수가 몇개 있는지를 출력하는 문제를 생각해 봅시다.

def solution(arr):
   answer = 0
   maxnum = -1
    
   for n in arr:
      if n >= maxnum:
         answer = 1
         maxnum = n
      elif n == maxnum:
         answer += 1
   	
   return answer

예시 케이스로 [1, 2, 3, 4, 5]가 주어진다면 정답인 1을 return하지만 이 솔루션도 틀린 솔루션입니다. [1, 2, 3, 4, 5, 5, 5]가 들어와도 정답인 3 대신 1을 return합니다.

가장 큰 수가 갱신되는 n > maxnum이 아닌 n >= maxnum을 넣었기 때문에 큰 수가 몇개인지 카운트를 키우지 않고 계속 1로 초기화 하기 때문입니다.

이런 간단한 실수를 발견하지 못한다면 기껏 문제를 잘 풀어놓고 억울하게 틀릴 수 있습니다.

위 실수들을 잘 체크해서 코딩테스트 통과하시고 취업의 꿈! 꼭 이루시길 바랍니다. 

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

2023 카카오 블라인드 2번 문제입니다. 

가장 먼 택배 업무의 위치가 n이라고 했을때 왕복으로 2 * n을 움직이면서 수거와 배달 두가지 일을 할 수 있다는 아이디어만 떠올리면 풀립니다.

다만 구현할때 실수하기 쉬운 부분이 꽤 있었습니다. (빈 집을 뛰어넘기, 초기 데이터 정리 등등)

def solution(cap, n, deliveries, pickups):
    answer = 0

    pi, di = n, n

    while not (pi == 0 and di == 0):
        while pi >= 1 and pickups[pi - 1] == 0:
            pi -= 1
        while di >= 1 and deliveries[di - 1] == 0:
            di -= 1

        answer += (max(pi, di)) * 2

        c = cap
        while c > 0 and pi >= 1:
            d = min(c, pickups[pi - 1])
            pickups[pi - 1] -= d
            c -= d
            if pickups[pi - 1] == 0:
                pi -= 1

        c = cap
        while c > 0 and di >= 1:
            d = min(c, deliveries[di - 1])
            deliveries[di - 1] -= d
            c -= d
            if deliveries[di - 1] == 0:
                di -= 1

    return answer