내일은 알고리즘

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

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

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

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

문자열 파싱과 dictionary 등의 자료구조를 사용하면 쉽게 풀리는 문제입니다.

저는 우선 각 약관별로 유효기간을 dictionary에 저장해놓고, 수집일자와 오늘 날자를 파싱해 정수형으로 변환해 비교해주었습니다. 다행히 한 달의 일수가 28일로 모두 같아 계산하기 쉬웠습니다. 

(예를들어 1년이 28 * 12 = 336일이므로 100년 1월 1일은 33601일이 됩니다.) 

**솔루션 수정**

2023.01.06 - 괄호를 잘못 묶었습니다. ^^;;

def solution(today, terms, privacies):
    answer = []
    termdict = {}
    
    for term in terms:
        t = term.split(' ')
        termdict[t[0]] = int(t[1]) * 28
        
    t = today.split('.')
    d = 28 * 12 * int(t[0]) + 28 * (int(t[1]) - 1) + int(t[2])
    
    for p in range(len(privacies)):
        pret = privacies[p].split(' ')
        t = pret[0].split('.')
        nd = 28 * 12 * int(t[0]) + 28 * (int(t[1]) - 1) + int(t[2])
        
        if termdict[pret[1]] + nd <= d:
            answer.append(p + 1)
        
    
    return answer

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

구현할게 많아 귀찮은(?) 문제입니다.

index를 밀어가면서 주어진 4개의 문자열이 나오는지를 확인해주면 되고, 연속해서 쓰이지 않도록 이전 문자열을 기억해줘야 합니다. 조건을 만족하지 못하거나 문자열을 전부 탐색해서 성공했을때 반복문을 끝내는 부분만 신경쓰면 어렵지 않게 풀립니다.

def solution(babbling):
    answer = 0

    for b in babbling:
        idx = 0
        flag = -1
        while idx < len(b):
            if b[idx] == 'a':
                if flag != 0 and idx + 2 < len(b) and b[idx+1] == 'y' and b[idx + 2] == 'a':
                    flag = 0
                    idx += 3
                else:
                    flag = -1
                    break
            elif b[idx] == 'y':
                if flag != 1 and idx + 1 < len(b) and b[idx+1] == 'e':
                    flag = 1
                    idx += 2
                else:
                    flag = -1
                    break
            elif b[idx] == 'w':
                if flag != 2 and idx + 2 < len(b) and b[idx+1] == 'o' and b[idx + 2] == 'o':
                    flag = 2
                    idx += 3
                else:
                    flag = -1
                    break
            elif b[idx] == 'm':
                if flag != 3 and idx + 1 < len(b) and b[idx+1] == 'a':
                    flag = 3
                    idx += 2
                else:
                    flag = -1
                    break
            else:
                flag = -1
                break

        if flag != -1:
            answer += 1

    return answer

print(solution(	["ayaye", "uuu", "yeye", "yemawoo", "ayaayaa"]))

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

일주일 공부를 안한 사이에 또 문제가 추가되었다.

열일하는 프로그래머스 화이팅~

기본적인 Stack 응용 문제인것 같은데, 사실 그닥 스택 느낌이 없다. 문제 설명도 뭔가 부족한 느낌... 처음엔 가능한 만큼 햄버거를 계속 만드는줄 알았는데 그런거 없더라.

아무튼, Python엔 Stack이 없기 때문에 List를 하나 만들어 주고, 적절히 탐색해가면서 만들어지는 햄버거의 갯수를 카운팅하면 쉽게 풀린다.

def solution(ingredient):
    answer = 0
    remain = []

    for i in ingredient:
        if i == 1 and len(remain) >= 3 and remain[-1] == 3 and remain[-2] == 2 and remain[-3] == 1:
            for _ in range(3):
                remain.pop()
            answer += 1
        else:
            remain.append(i)

    return answer