컴공0개언어

문제 링크 : programmers.co.kr/learn/courses/30/lessons/42576

사실 해시 관련 문제가 어떤 것인지 잘 몰랐는데, 이 문제를 풀면서 대략적인 방법을 알게 된 것 같다.

해시 관련 문제를 풀 때는 어떻게 하면 탐색을 O(1)에 할 수 있는지를 생각하는게 중요하다 생각했다.

파이썬에서는 다행히 딕셔너리라는 좋은 자료형을 제공해줘서 딕셔너리를 잘 이용하면 될 것 같다.

이 문제는 완주자의 수가 (참여자의 수 - 1)이므로 사실상 같다고 할 수 있다. 따라서 참여자의 수를 n이라고 하면 1 <= n <= 100000이므로 시간복잡도를 최대 O(nlogn)까지 가능할 것이라 파악했다.

이 문제에서는 참여자 중 완주자에 포함되지 않는 사람을 찾는 것이고, 이를 위해 완주자가 참여자에 있는지 탐색을 하였다.

이 때, 탐색을 O(1)에 하기 위해 딕셔너리를 이용했고, 중복된 이름의 참여자가 있을 수 있으므로 딕셔너리의 Key로는 참여자의 이름, Value로는 Key값을 이름으로 가진 사람의 수를 저장하였다.

그리고 각 완주자들에 대해서 해당 완주자가 있으면 딕셔너리의 Value값을 1씩 감소시키고, Value가 0이 되면 Key를 이름으로 가진 사람은 완주를 했다는 것이므로 딕셔너리에서 삭제한다.

이러한 과정을 거치면 최종적으로 딕셔너리의 Key로는 완주하지 못한 한 사람의 이름과, Value값으로는 1을 갖게 된다.

따라서 하나 남은 Key를 최종 답으로 제출하면 된다.

해당 풀이는 O(n) 시간복잡도를 갖는다.

def solution(participant, completion):
    answer = ''
    participant_dict = {}
    
    for p in participant:
        if p not in participant_dict:
            participant_dict[p] = 1
        else:
            participant_dict[p] += 1
    
    for c in completion:
        participant_dict[c] -= 1
        if participant_dict[c] == 0:
            del participant_dict[c]
    
    answer = list(participant_dict.keys())[0]
    
    return answer

해당 알고리즘의 채점 결과이다.

그리고 defaultdict를 사용하면 key값에 대해서 if Key not in dict 구문을 사용하지 않아도 되므로 코드를 약간 간결하게 할 수 있다. 다만 시간은 기본 dictionary를 사용했을 때 보다 조금 느리다.

from collections import defaultdict

def solution(participant, completion):
    answer = ''
    participant_dict = defaultdict(int)
    
    for p in participant:
        participant_dict[p] += 1
    
    for c in completion:
        participant_dict[c] -= 1
        if participant_dict[c] == 0:
            del participant_dict[c]
    
    answer = list(participant_dict.keys())[0]
    
    return answer

문제링크 : www.acmicpc.net/problem/2164

deque를 사용하면 문제가 아주 간단해진다.

문제 설명에 나와있는대로 위에 있는 카드를 뺄 때는 deque.popleft()를 하면 되고, 위에 있는 카드를 아래로 옮길 때는 deque.popleft()값을 append해주면 된다.

import sys
from collections import deque

N = int(sys.stdin.readline())
deque = deque([i+1 for i in range(N)])

while len(deque) > 1:
    deque.popleft()
    deque.append(deque.popleft())

print(deque[0])

문제 링크 : programmers.co.kr/learn/courses/30/lessons/43163

재귀를 이용한 dfs로 해결하였는데, 최소 수행 횟수를 찾는 것이므로 bfs로 푸는 것이 더 좋을 것 같다는 생각을 했다. 

is_convertible은 인자로 들어온 2개의 문자열에 대해서 같은 위치에 있지만 다른 알파벳 개수를 계산하는데, 문제 조건에서는 다른 알파벳이 1개일 경우에만 단어 변환을 해줄 수 있으므로 다른 알파벳 개수가 1개이면 True, 1개가 아니면 False를 반환한다.

dfs에서는 리스트를 잘라서 인자로 넣어주므로 단어들의 리스트인 words의 길이가 0이면 재귀를 탈출하도록 하였다.

그리고 for문 내에서 리스트의 index를 삭제할건데, for문을 도는 리스트를 삭제하면 에러가 발생하므로 copy()를 통해 리스트의 복사본을 생성한다.

이후 문제 조건에 맞게 if문을 설정하고 방문한 element를 삭제한 후 다시 dfs의 인자로 넘겨주었다.

def is_convertible(word1, word2):
    # len(word1) == len(word2)
    num_diff_words = sum([True if ch1 != ch2 else False for ch1, ch2 in zip(word1, word2)])
    if num_diff_words == 1:
        return True
    else:
        return False
    

min_count = 99999
def dfs(begin, target, words, count):
    global min_count
    if len(words) == 0:
        return
    
    words_copy = words.copy()
    
    for i, word in enumerate(words):
        if is_convertible(begin, word):
            if word == target:
                if count < min_count:
                    min_count = count
                return
            
            del words_copy[i]
            dfs(word, target, words_copy, count+1)
            words_copy = words.copy()


def solution(begin, target, words):
    global min_count
    
    if target not in words:
        return 0
    
    dfs(begin, target, words, 1)
    
    return min_count

문제링크 : programmers.co.kr/learn/courses/30/lessons/43165

재귀를 통한 dfs를 이용했다. 리스트를 잘라가며 재귀에 넘겨주므로 재귀 탈출 조건으로 numbers가 빈 리스트인 경우로 설정하였다. 인자에 있는 numbers는 계산을 하기 위해 남은 숫자 리스트, sum은 현재 재귀에서의 합을 뜻한다.

그리고 입력한 숫자에 대해서 +와 -모두 고려해야 되므로 현재 sum에 -한 값과 +한 값을 sum_1, sum_2로 설정하여 이용한다.

count = 0
def dfs(numbers, target, sum):
    global count
    
    if len(numbers) == 0:
        return
    
    sum_1 = sum - numbers[0]
    sum_2 = sum + numbers[0]
    
    if len(numbers) == 1:
        if sum_1 == target:
            count += 1
        if sum_2 == target:
            count += 1
    else:
        dfs(numbers[1:], target, sum_1)
        dfs(numbers[1:], target, sum_2)    


def solution(numbers, target):
    # 2 <= len(numbers) <= 20
    global count
    dfs(numbers, target, 0)
    
    return count

문제 링크 : programmers.co.kr/learn/courses/30/lessons/72410

정규 표현식을 이용하면 간단하게 해결할 수 있는 문제다.

다만 처음에 3단계에서 정규표현식을 '.+'로 사용하였는데 계속 모든 답이 "aaa"로 나왔다.

정규표현식을 더 살펴보니 그냥 '.'을 사용하면 문자 전체를 의미하는 것이므로 단순이 '.'을 사용하면 안되고 '\.'을 사용해야 한다.

아직 정규표현식에 대해 익숙하지 않아 헷갈렸던 부분이다.

import re

def solution(new_id):
    answer = new_id
    
    # 1단계
    answer = answer.lower()
    
    # 2단계
    answer = re.sub('[^a-z0-9-_.]', '', answer)
    
    # 3단계
    # 그냥 . ==> 모든 문자, \. ==> 점
    answer = re.sub('\.+', '.', answer)
    
    # 4단계
    answer = answer.strip('.')
    
    # 5단계
    if not answer:
        answer = 'a'
    
    # 6단계
    if len(answer) >= 16:
        answer = answer[:15]
    answer = answer.rstrip('.')
    
    # 7단계
    if len(answer) <= 2:
        last_char = answer[-1]
        while len(answer) < 3:
            answer += last_char
    
    return answer

문제링크 : www.acmicpc.net/problem/2667

지도와 동일한 크기를 가지는 visited리스트를 만든다. visited는 방문했으면 True, 방문하지 않았으면 False값을 가진다. 따라서 map이 '1'값을 가지고, visited가 False값을 가질 때 탐색을 시작하도록 한다. 탐색한 부분의 visited는 True로 변경하고, 상하좌우 중 map이 '1'값을 가지고 visited가 False인 지점이 있으면 재귀를 이용하여 탐색을 진행한다.

import sys
sys.setrecursionlimit(10**9)

house_num = 0
house_nums = []
def dfs(house_map, visited, start_row, start_col):
    if visited[start_row][start_col]:
        return

    global house_num

    dx = [0, 0, -1, 1] # 상 하 좌 우
    dy = [-1, 1, 0, 0]

    house_num += 1
    visited[start_row][start_col] = True

    for i in range(len(dx)):
        if 0 <= start_row + dy[i] < len(house_map) and 0 <= start_col + dx[i] < len(house_map[start_row+dy[i]]):
            if house_map[start_row+dy[i]][start_col+dx[i]] == '1' and not visited[start_row+dy[i]][start_col+dx[i]]:
                dfs(house_map, visited, start_row+dy[i], start_col+dx[i])


N = int(sys.stdin.readline())

house_map = [sys.stdin.readline().rstrip() for _ in range(N)]
visited = [[False] * N for _ in range(N)]

group_count = 0
for i in range(len(house_map)):
    for j in range(len(house_map[i])):
        if house_map[i][j] == '1' and not visited[i][j]:
            dfs(house_map, visited, i, j)
            group_count += 1

            if house_num != 0:
                house_nums.append(house_num)
                house_num = 0

print(group_count)

house_nums.sort()
for house_num in house_nums:
    print(house_num)

문제 링크 : programmers.co.kr/learn/courses/30/lessons/42583

대기중인 트럭과 다리를 지나가고 있는 트럭들은 큐에 저장하였고, 다리를 지나간 트럭들은 리스트에 저장하였다. while문에서는 먼저 지나가고 있는 트럭 중 끝에 도달한 트럭이 있으면 다리를 지나간 트럭 리스트로 옮긴다. 다리의 끝에 도달했는지 판단하는 조건은 트럭이 1초에 1만큼 움직이므로 (현재 초) - (트럭이 다리에 들어올 때 초) >= bridge_length로 하였다.

그리고 대기중인 트럭이 들어왔을 때 weight를 넘게 되면 다리를 지나가는 트럭 큐에 추가하지 않고, 넘지 않으면 추가한다. 추가하는 내용은 (트럭의 weight, 트럭이 다리를 진입할 때의 초)이다.

from collections import deque

def solution(bridge_length, weight, truck_weights):
    answer = 0
    
    num_truck = len(truck_weights)
    
    waiting_truck = deque(truck_weights) # 대기중인 트럭
    passing_truck = deque() # 다리를 지나는 트럭
    passed_truck = [] # 다리를 지난 트럭
    
    weight_sum = 0
    while len(passed_truck) < num_truck:
        answer += 1
        
        if len(passing_truck) > 0:
            first_passing_truck = passing_truck.popleft()
            
            if answer - first_passing_truck[1] >= bridge_length:
                weight_sum -= first_passing_truck[0]
                passed_truck.append(first_passing_truck[0])
            else:
                passing_truck.appendleft(first_passing_truck)
        
        if len(waiting_truck) > 0:
            cur_weight = waiting_truck.popleft()
            weight_sum += cur_weight
        
            if weight_sum <= weight:
                passing_truck.append((cur_weight, answer)) # (weight, 진입한 시점의 초)
            else:
                weight_sum -= cur_weight
                waiting_truck.appendleft(cur_weight)
        
    return answer

문제 링크 : programmers.co.kr/learn/courses/30/lessons/42885

기본적인 그리디 문제와 유사해 보인다. 따라서 people을 오름차순으로 정렬한 후, limit에 넘지 않도록 최대한 많은 사람을 태우면 될 것 같다. 하지만 최대 2명 탑승가능 조건이 있기 때문에 앞에서부터 차례로 태우는 것이 아니라 보트에 탄 사람들의 무게가 limit에 최대한 가깝도록 사람들을 태워야 한다. 

예시로 people이 [40, 50, 60, 70, 80, 90]로 정렬되어 있는 상태이고 limit은 120이라고 하자.

그러면 앞에서부터 차례로 사람들을 태우는 경우 다음과 같이 5개의 구명보트가 필요하다.

따라서 보트에 탄 사람들의 무게가 limit에 최대한 가깝도록 하기 위해 다음과 같이 low와 high를 설정할 수 있다. 

여기서 people[low]+people[high]가 130이므로 limit 120보다 크다. 따라서 high에 있는 사람은 구명보트를 혼자서밖에 탈 수 없으므로 구명보트 개수를 1 증가시키고 high를 1 감소시켜서 high에 있는 사람을 구명보트에 태워 보낸다. 

갱신된 low와 high상태는 다음과 같다.

여기서는 people[low]+people[high]가 120이므로 limit와 같다. 따라서 low와 high에 있는 사람을 모두 구명보트에 태울 수 있으므로 구명보트 개수를 1 증가시키고 low는 1 증가, high는 1 감소시킨다.

이러한 작업을 low <= high일 동안 반복한다.

def solution(people, limit):
    answer = 0
    
    people.sort()
    
    low = 0
    high = len(people) - 1
    
    while low <= high:
        if (people[low] + people[high]) > limit:
            answer += 1
            high -= 1
        elif (people[low] + people[high]) <= limit:
            answer += 1
            low += 1
            high -= 1
    
    return answer