데린이 성장 일지

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

1차 시도

query가 맨 앞이 "?"인지 확인하여 시작위치를 파악하고, query 길이와 word 길이가 같은지, "?"를 제외한 문자열이 word이 시작위치 기준으로 문자열 길이만큼 동일한지 확인하면 된다고 생각했습니다.

def solution(words, queries):
    answer = []
    
    for query in queries:
        cnt = 0
        N = len(query)
        if query[0] == "?":
            front = False
        else:
            front = True
        for word in words:
            if N != len(word):
                continue
            search_word = query.replace("?", "")
            search_N = len(search_word)
            if front:
                if word[:search_N] == search_word:
                    cnt += 1
            else:
                if word[-search_N:] == search_word:
                    cnt += 1
        answer.append(cnt)
    return answer

2차 시도

1차 시도보다 시간 효율성을 좋게하기 위해 딕셔너리를 생각했습니다.

딕셔너리 키는 word에 들어갈 수 있는 모든 query의 수이고, 값은 해당 쿼리로 검색할 수 있는 word의 수입니다.

def solution(words, queries):
    answer = []
    
    word_dict = {}
    
    for word in words:
        string = ""
        N = len(word)
        for token in word[:-1]:
            string += token
            keyword = string.ljust(N, "?")
            if keyword in word_dict:
                word_dict[keyword] += 1
            else:
                word_dict[keyword] = 1
        string = ""
        for token in word[::-1][:-1]:
            string += token
            keyword = string.ljust(N, "?")[::-1]
            if keyword in word_dict:
                word_dict[keyword] += 1
            else:
                word_dict[keyword] = 1
    
    for query in queries:
        answer.append(word_dict[query] if query in word_dict else 0)
    
    return answer

3차 시도

마지막으로 트리에 알고리즘을 적용했습니다.

class Node(object):
    def __init__(self, key = None):
        self.key = key
        self.length = []
        self.child = {}

class Trie():
    def __init__(self):
        self.head = Node()
        
    def insertTree(self, word):
        cur = self.head
        word_length = len(word)
        cur.length.append(word_length)
        for token in word:
            if token not in cur.child:
                cur.child[token] = Node(token)
            cur = cur.child[token]
            cur.length.append(word_length)
            
    def searchTree(self, word):
        cur = self.head
        word_length = len(word)
        for token in word:
            if token == "?":
                return cur.length.count(word_length)
            elif token not in cur.child:
                break
            cur = cur.child[token]
        return 0

def solution(words, queries):
    answer = []
    tree = Trie()
    reverse_tree = Trie()
    for word in words:
        tree.insertTree(word)
        reverse_tree.insertTree(word[::-1])
    for query in queries:
        if query[0] == "?":
            answer.append(reverse_tree.searchTree(query[::-1]))
        else:
            answer.append(tree.searchTree(query))
    return answer

코드 설명

Node class는 문자열의 token를 key로 갖고, 해당 노드를 거치는 word들의 길이를 나타내는 리스트를 length로 갖고, 자식노드를 나타내는 딕셔너리를 child로 갖습니다.

Trie class는 트리에 알고리즘을 적용시키기 위한 클래스입니다.

insertTree는  word의 token들을 노드에 차례로 넣고 함께 그 노드를 거치는 word들의 길이를 length 리스트에 넣어줍니다.

searchTree는 query의 token이 "?"가 나올 때까지 들어가서 "?"를 만나면 전 노드의 length에 찾고자하는 query 길이를 카운트하고 그 카운터 값을 리턴합니다.

solution function에서 "????o"와 같이 뒤에서 부터 검색하기 위한 reverse_tree를 따로 만들어 줍니다.

그리고 words에 대하여 모든 tree와 reverse_tree를 만듭니다.

그리고 queries에 대하여 query가 "?"로 시작하면 revers_tree에서 찾고 아니라면 tree에서 찾아서 answer 리스트에 추가합니다.

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

1차 시도

구현부터 해보자는 생각에 먼저 words를 돌면서 word가 완성될 수 있는 모든 경우의 수에 대한 딕셔너리를 만들었습니다.

ex) words = ["go", "gone"]는 {"g": ["go", "gone"], "go": ["go", "gone"], ":gon": ["gone"], "gone": [ "gone" ]}

딕셔너리를 만든 후 words를 돌아서 특정 word가 만들어 지는 경우의 수 key에 대해 특정 word value를 가지거나 완전한 word만 가능할 때 answer에 key의 길이를 더해주면 될 것 같다고 생각했습니다.

from collections import defaultdict

def solution(words):
    answer = 0
    
    word_dict = defaultdict(list)
    
    for word in words:
        N = len(word)
        for i in range(1, N+1):
            word_dict[word[:i]] += [word]
            
    for word in words:
        N = len(word)
        for i in range(1, N+1):
            if len(word_dict[word[:i]]) == 1:
                answer += i
                break
        else:
            answer += N
    
    return answer

2차 시도

value에 가능한 word 리스트가 아닌 개수를 넣어서 len(word_dict[word[:i])의 시간을 줄여보려했습니다.

또한 먼저 word_dict[word]가 1가 아니라면 바로 answer에 word 길이를 더하여 word에 대해 for문이 도는 횟수를 줄이고자 했습니다.

from collections import defaultdict

def solution(words):
    answer = 0
    
    word_dict = defaultdict(int)
    
    for word in words:
        N = len(word)
        for i in range(1, N+1):
            word_dict[word[:i]] += 1
            
    for word in words:
        N = len(word)
        if word_dict[word] != 1:
            answer += N
            continue
        for i in range(1, N+1):
            if word_dict[word[:i]] == 1:
                answer += i
                break
    
    return answer

※ 실행 결과

다른 사람 코드

class Node(object):
    def __init__(self, key, cnt = 0):
        self.key = key
        self.cnt = cnt
        self.child = {}

class Trie():
    def __init__(self):
        self.head = Node(None)
    def insertTree(self, string):
        cur = self.head
        for token in string:
            if token not in cur.child:
                cur.child[token] = Node(token)
            cur = cur.child[token]
            cur.cnt += 1
    def searchTree(self, string):
        cur = self.head
        cnt = 0
        for token in string:
            cnt += 1
            cur = cur.child[token]
            if cur.cnt == 1:
                return cnt
        return len(string)   

def solution(words):
    answer = 0
    wordTree = Trie()
    for word in words:
        wordTree.insertTree(word)
    for word in words:
        answer += wordTree.searchTree(word)
    return answer

※ 실행 결과

풀이

Trie 알고리즘으로 푼 코드입니다.

단어 단위로 트리 형식으로 연결합니다.

트리의 깊이가 단어의 길이가 됩니다.

이 코드에서 노드의 구조는 key(단어의 token), cnt(자식 노드 수), child(자식 노드들)로 구성되어 있습니다.

여기서 child는 딕셔너리 형식으로 상수 시간에 검색하도록 합니다.

해당 단어의 자동 완성 조건에 만족하려면 노드의 cnt가 1일 때까지 타고 들어가거나, 노드의 cnt가 1인 경우가 없어서 모든 노드를 타고 들어가야합니다.

궁금한 점

2차 시도에서 짠 코드의 실행 결과에서 통과된 시간을 보면 3배이상 빠른데, 시간 초과는 어떤 경우에서 뜨는지 모르겠습니다.

혹시 아시는 분은 댓글로 알려주시면 감사하겠습니다.

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

1차 시도

첫째 아들에게 쿠키를 주다가 둘째 아들에게 쿠키를 주는 기준점을 정해서 answer을 구하는 방법으로 코드를 구현했습니다.

def solution(cookie):
    answer = 0
    N = len(cookie)
    
    if N == 1:
        return answer
    
    for mid in range(N-1):
        l = mid
        r = mid+1
        while l >= 0 and r <= N-1:
            first_cookie = sum(cookie[l:mid+1])
            second_cookie = sum(cookie[mid+1:r+1])
            if first_cookie == second_cookie:
                answer = max(answer, first_cookie)
                r += 1
                l -= 1
            elif first_cookie > second_cookie:
                r += 1
            else:
                l -= 1
        
    return answer

2차 시도

1차 시도에서 시간을 줄일 수 있는 방법으로 while문을 돌 때 sum을 매번 하는 것이 아닌 새롭게 추가된 쿠키를 더하는 방법으로 변경했습니다.

def solution(cookie):
    answer = 0
    N = len(cookie)
    
    if N == 1:
        return answer
    
    for mid in range(N-1):
        l = mid
        r = mid+1
        first_cookie = cookie[l]
        second_cookie = cookie[r]
        while True:
            if first_cookie == second_cookie:
                answer = max(answer, first_cookie)
                r += 1
                l -= 1
                if l >= 0 and r <= N-1:
                    first_cookie += cookie[l]
                    second_cookie += cookie[r]
                else:
                    break
            elif first_cookie > second_cookie:
                r += 1
                if r <= N-1:
                    second_cookie += cookie[r]
                else:
                    break
            else:
                l -= 1
                if l >= 0:
                    first_cookie += cookie[l]
                else:
                    break
        
    return answer

코드 설명

기준점 mid를 for문으로 전부 돕니다.

while문이 핵심 코드인데,

• if first_cookie == second_cookie:(첫째 아들에게 준 쿠키와 둘째 아들에게 준 쿠키가 같다면)
  answer와 first_cookie 중 높은 수를 answer로 초기화합니다.
  r은 1을 더해주고 l은 1을 뺍니다.
  유효한 r과 l이라면 first_cookie와 second_cookie에 바로 전 또는 후의 쿠키를 더해주게 됩니다.
  유효하지 않다면 while문을 종료합니다.
• elif first_cookie > second_cookie:(첫째 아들에게 준 쿠키가 더 많다면)
  r에 1을 더해줍니다.
  유효한 r이라면 second_cookie에 바로 후의 쿠키를 더해줍니다.
  유효하지 않다면 while문을 종료합니다.
• else:(둘째 아들에게 준 쿠키가 더 많다면)
  l에 1을 빼줍니다.
  유효한 l이라면 first_cookie에 바로 전의 쿠키를 더해줍니다.
  유효하지 않다면 while문을 종료합니다.

https://school.programmers.co.kr/learn/courses/30/lessons/42897?language=python3

1차 시도

dp로 푸는 것을 떠올랐고, 첫 번째 집부터 터는 경우와 두 번째 집부터 터는 경우로 나누어서 각 경우의 마지막 dp 값이 큰 경우가 답이 될 것이라 생각했습니다.

def solution(money):
    N = len(money)
    
    # 첫 번째부터 털 경우 -> 마지막 집 못 텀
    dp = [0] * N
    
    dp[0] = money[0]
    dp[1] = money[0]
    
    for i in range(2, N-1):
        dp[i] = max(dp[i-2] + money[i], dp[i-1])
        
    from_first = dp[N-2]
    
    # 두 번째부터 털 경우
    dp = [0] * N
    
    dp[0] = 0
    dp[1] = money[1]
    
    for i in range(2, N):
        dp[i] = max(dp[i-2] + money[i], dp[i-1])
        
    from_second = dp[N-1]
    
    return max(from_first, from_second)

결과: 100

정확성, 효율성 모두 통과

풀이

현재(i)까지 집을 털었을 때 최대값은 

• i-2 번째까지 집을 털었을 때 최대값(dp[i-2]) +  i 번째 집을 털었을 때
• i-1 번째까지 집을 털었을 때 최대값(dp[i-1])

이 두 경우를 비교해서 더 큰 값이 dp[i]가 됩니다.

첫 번째 집을 털 경우 마지막 집은 첫 번째 집과 인접하기 때문에 털 수가 없습니다.

그래서 첫 번째 집부터 털 경우와 두 번째 집부터 털 경우를 구분해야 합니다.

첫 번째 집부터 털 경우

첫 번째 집을 털 경우 두 번째 집을 털지 못하기 때문에 dp[0]과 dp[1]는 money[0]이 됩니다.

마지막 집의 바로 전 집(N-2)까지 턴 경우의 최대값이 첫 번째 집부터 털 경우의 최대값(dp[N-2])이 됩니다.

두 번째 집부터 털 경우

첫 번째 집을 털지 않고 두 번째 집을 털기 때문에 dp[0]는 0, dp[1]는 money[1]이 됩니다.

마지막 집(N-1)까지 턴 경우의 최대값이 두 번째 집부터 털 경우의 최대값(dp[N-1])이 됩니다.

두 경우의 최대값 중 더 큰 값이 정답이 됩니다.

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

1차 시도

방 번호를 key를 갖고 바로 다음 방 번호를 value로 두고 찾아보자는 생각으로 구현

def solution(k, room_number):
    room_dict = dict()
        
    for room in room_number:
        while room in room_dict.keys():
            room = room_dict[room]
        room_dict[room] = room + 1
    
    return list(room_dict.keys())

결과: 78.8

정확성만 통과

다른 사람 코드

import sys
sys.setrecursionlimit(1012)

def solution(k, room_number):
    room_dict = dict()
        
    for room in room_number:
        find_empty_room(room, room_dict)
            
    return list(room_dict.keys())

def find_empty_room(room_num, room_dict):
    if room_num not in room_dict.keys():
        room_dict[room_num] = room_num + 1
        return room_num
    empty_room = find_empty_room(room_dict[room_num], room_dict)
    room_dict[room_num] = empty_room + 1
    return empty_room

결과: 100

정확성과 효율성 모두 통과

1차 시도와 차이점

저의 코드는 value를 바로 다음 방 번호를 넣기 때문에 다음 가능한 방 번호를 찾을 때 어떠한 경우라도 1씩 증가시키면서 찾습니다.

다른 사람 코드는 value를 이전까지 찾았던 배정 가능한 빈 방 번호를 넣기 때문에 1씩 증가시키는 것보다 탐색 경로가 압축이 되기 때문에 더 빠르게 됩니다.

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

문제를 요약하자면 k초까지 음식을 먹고 난 다음 차례를 구하는 문제라 할 수 있을 것 같습니다.

1차 시도

food_times를 매번 다 돌기보다는 음식이 남아있는 인덱스만 돌자라는 생각으로 구현했습니다.

def solution(food_times, k):
    N = len(food_times)
    
    leftovers = [idx for idx in range(N)]
    
    cur = 0
    
    while 0 <= k:    
        if leftovers == []:
            return -1
        
        repeat_leftovers = leftovers.copy()
        
        for left in repeat_leftovers:
            if k == 0:
                return left+1
            
            food_times[left] -= 1
            k -= 1
            
            if food_times[left] == 0:
                leftovers.remove(left)

결과

정확성은 통과하였지만 효율성에서 다 실패했습니다.

2차 시도

queue를 이용해보자는 생각으로 구현했습니다.

import queue

def solution(food_times, k):
    food_queue = queue.Queue()
    for idx, food_time in enumerate(food_times):
        food_queue.put((food_time, idx+1))
    
    while not food_queue.empty():
        food_time, idx = food_queue.get()
        if k == 0:
            return idx
        food_time -= 1
        k -= 1
        if food_time:
            food_queue.put((food_time, idx))
    return -1

결과

가독성은 늘어났으나 실행시간은 더 느려졌습니다. (1차 시도와 마찬가지로 정확성만 통과)

3차 시도

다른 사람의 코드를 참고하였고, 음식을 섭취하는데 걸리는 시간을 오름차순으로 정렬한 후,

현재 음식의 섭취하는데 걸리는 시간과 다음 음식의 섭취하는데 걸리는 시간을 비교하여 for문을 도는 횟수를 줄이자는 생각으로 구현했습니다.

import heapq

def solution(food_times, k):
    if sum(food_times) <= k:
        return -1
    
    food_queue = []
    for idx, food_time in enumerate(food_times):
        heapq.heappush(food_queue, (food_time, idx+1))
    
    times = 0
    previous_time = 0
    left_food_count = len(food_queue)
    
    while times + (food_queue[0][0] - previous_time) * left_food_count <= k:
        food_time = heapq.heappop(food_queue)[0]
        times += (food_time - previous_time) * left_food_count
        left_food_count -= 1
        previous_time = food_time
        
    leftovers = sorted(food_queue, key=lambda x: x[1])
    return leftovers[(k-times)%left_food_count][1]

결과

정확성과 효율성 모두 통과했습니다.

설명

heapq를 이용하여 food_queue를 섭하는데 걸리는 시간을 기준으로 우선순위 큐를 만듭니다.

현재까지 섭취한 시간인 times, 이전까지 섭취한 시간인 previous_time, 남은 음식 개수인 left_food_count를 초기화합니다.

while문으로 현재 음식과 다음 음식의 섭취 시간 차이 * 남은 음식 수가 현재 섭취 시간에 더해질 때 시간과 k초를 비교합니다.

※ 여기서 food_queue[0][0]이 다음 음식 섭취시간이고, previous_time가 현재 음식 섭취시간입니다.

k초를 넘지 않는다면, 다음 음식을 다 섭취하는 루틴으로 넘어가게 됩니다.

이 루틴에서 food_queue에서 다음 음식을 빼내고, times가 다음 음식을 다 섭취할 때의 루틴의 섭취 시간으로 초기화 되고, left_food_count에 1을 빼고, previous_time을 다음 음식 섭취 시간으로 초기화합니다.

k초를 넘는다면, k초에 times를 빼고 left_food_count로 나눈 나머지의 위치에 있는 음식 번호를 return 해주게 됩니다.

만약 전체 음식을 다 섭취하는데 걸리는 시간이 k초보다 작다면 이후 로직을 탈 필요가 없기 때문에,

맨위에서 if  sum(food_times) <= k의 조건문을 추가했습니다.

https://school.programmers.co.kr/learn/courses/30/lessons/147354?language=python3 

try1

문제 설명만 보고 이해하기 어려웠던 문제였던 것 같다.

그래도 다행히 예시를 보고 이해했다.

이해를 한 후 크게 알고리즘을 3가지로 나눴다.

1. 전체 data 정렬

2. S_i들의 나머지들 합 구하기

3. bitwise XOR

※ 나의 코드

def solution(data, col, row_begin, row_end):
    answer = 0
    
    # 전체 정렬
    S_data = sorted(data, key = lambda x:(x[col-1], -x[0]))
	
    # S_i들의 나머지 합 구하기
    i = row_begin
    for S in S_data[row_begin-1:row_end]:
        S_i = 0
        for v in S:
            S_i += v % i     
        # bitwise XOR
        answer = (S_i)^answer
        i += 1

    return answer

문제 풀이)

sorted key를 이용하여 첫번째 기준 x[col-1]으로 오름차순, x[0]에 -를 붙여서 두번째 기준 x[0]으로 내림차순으로 정렬함

i에 시작 col값인 row_begin을 넣음

row_begin과 row_end를 이용하여 구해야할 튜플의 범위만큼 for문으로 돌림

처음에 S_i에 0을 할당하고 해당 순서의 튜플을 for문으로 돌면서 해당 i를 나눈 나머지를 S_i에 더해줌

해당 순서의 튜플을 도는 for문이 끝나면 해당 순서의 S_i는 구해짐

구해진 S_i을 ^연산자를 이용하여 answer과 bitwise XOR을 함

제일 첫번째 S_i로 하는 bitwise XOR은 answer이 0이므로 첫번째 S_i가 answer에 그대로 넣어짐

bitwise XOR을 하고나면 i에 1을 더해줌

이런식으로 S_data[row_begin-1:row_end]를 도는 for문이 돌면서

해당 순서의 S_i는 그 이전 S_i들의 bitwise XOR한 결과들과 bitwise XOR을 함으로써

우리가 원하는 결과 answer을 얻을 수 있음

테스트 결과) - 총합 232.03ms

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

try1

첫번째 카드를 찾는 알고리즘, 2번째 카드를 찾는 알고리즘, 조작 횟수를 카운트하는 알고리즘을 짜면 되겠구나하고 많은 시도를 하였으나 시간초과와 실패로 통과하지 못해서 다른 사람 코드를 분석하고자 함

※ 다른 사람 코드

from copy import deepcopy
from math import inf
from collections import deque

def get_key_count(board, cy, cx, ty, tx):    # (cy, cx)에서 (ty, tx)까지의 
    dy = [1, 0, 0, -1]                       # 이동 조작횟수를 구하는 함수
    dx = [0, 1, -1, 0]
    que = deque()
    que.append((cy, cx))
    visited = [[inf for _ in range(4)] for _ in range(4)]
    visited[cy][cx] = 0
    while que:
        y, x = que.popleft()
        if y == ty and x == tx:
            return visited[y][x]
        for i in range(4):
            ny, nx = y + dy[i], x + dx[i]
            if 0 <= ny < 4 and 0 <= nx < 4 and visited[ny][nx] > visited[y][x] + 1:
                visited[ny][nx] = visited[y][x] + 1
                que.append((ny, nx))

        for i in range(4):
            ny, nx = y + dy[i], x + dx[i]
            while 0 <= ny + dy[i] < 4 and 0 <= nx + dx[i] < 4 and board[ny][nx] == 0:
                ny, nx = ny + dy[i], nx + dx[i]
            if 0 <= ny < 4 and 0 <= nx < 4 and visited[ny][nx] > visited[y][x] + 1:
                visited[ny][nx] = visited[y][x] + 1
                que.append((ny, nx))

def get_coord_by_num(board, target):            # target의 i, j를 구하기 위한 함수
    for i in range(4):
        for j in range(4):
            if board[i][j] == target:
                return i, j

answer = inf           # 최솟값을 구하는 것이기 때문에 아주 큰 값 inf를 할당

def is_end(board):             # 모든 조작이 끝났다면 Ture를 아니라면 False를 반환해주는 함수
    for i in range(4):
        for j in range(4):
            if board[i][j] != 0:
                return False
    return True


def dfs(board, r, c, ty1, tx1, cnt):
    global answer
    board = deepcopy(board)     # 해당 경우의 수가 다른 경우의 수에 영향을 주지 않기 위한 deepcopy
    target_num = board[ty1][tx1]

    # 첫 번째 카드
    cnt += get_key_count(board, r, c, ty1, tx1)    # 현재 위치에서 첫번째 카드 찾기까지의
    board[ty1][tx1] = 0							   # 이동 조작 횟수를 cnt에 더해줌
    # 두 번째 카드
    ty2, tx2 = get_coord_by_num(board, target_num)
    cnt += get_key_count(board, ty1, tx1, ty2, tx2)  # 첫번째 카드에서 두번째 카드 찾기까지의
    board[ty2][tx2] = 0								 # 이동 조작 횟수를 cnt에 더해줌
    cnt += 2       # 첫번째 카드와 두번째 카드의 뒤집기 조작 횟수를 cnt에 더해줌
    if is_end(board):
        answer = min(answer, cnt)  # 해당 경우의 cnt와 answer 중 작은 값을 answer에 넣음
    for i in range(4):     # 다음 첫번째 카드가 될 수 있는 모든 i, j에 대하여 dfs를 함
        for j in range(4):
            if board[i][j] != 0:
                dfs(board, ty2, tx2, i, j, cnt)

def solution(board, r, c):
    for i in range(4):    # 처음 첫번째 카드가 될 수 있는 모든 i, j에 대하여 dfs를 함
        for j in range(4):
            if board[i][j] != 0:
                dfs(board, r, c, i, j, 0)

    return answer

문제풀이)

대략적으로 설명하자면

get_key_count 함수는 인수로 들어간 (cy, cx)에서 (ty, tx)까지의 이동 조작 횟수를 리턴해주는 함수임

첫번째 for문의 if문과 두번째 for문의 if문에 print(visited)를 해보면 이해할 수 있을 것이라 생각함

get_coord_by_num 함수는 target과 같은 값을 가지고 있는 보드의 행과 열을 구하기 위한 함수임

여기선 두번째 카드의 행과 열을 구하려고 씀

is_end 함수는 해당 경우에서 모든 조작이 끝났다면 True를, 아니라면 False를 반환해주는 함수임

여기선 최솟값을 answer에 넣으려고 씀

dfs 함수는 현재 위치 -> 첫번째 카드 선택 -> 두번째 카드 선택까지의 모든 조작 횟수를 cnt에 더해주고 다음 dfs를 진행하는 함수임

solution 함수에서 모든 경우의 수를 확인하여 최종 answer을 return 해줌

테스트 결과) 총합 - 52284.35ms