greentea31's Note

https://www.acmicpc.net/problem/2805

풀이 과정

절단기 높이 H보다 높은 나무의 길이를 길이 - H 만큼 잘라서 길이 M만큼 챙겨야 할 때, 가능한 최소 절단기의 높이를 구하는 문제이다.

나무 최대 길이 = 절단기 높이를 초기값으로 잡고, 길이 M만큼 챙길 수 있을 때 까지 절단기 높이 H를 1씩 낮추는 방법이 먼저 떠오르지만, 나무 길이가 10억까지 들어오므로 100% TLE가 날 것이다. 따라서 이분 탐색을 활용하여 문제를 해결하였다.

소스 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool cut(long long mid, vector<long long>& vec, int N, int M) {
    long long sum = 0;

    for (int i = 0; i < N; i++) {
        if (vec[i] > mid) {
            sum += vec[i] - mid;
        }

        if (sum >= M) {
            return true;
        }
    }

    return false;
}

int main() {
    int N, M;
    cin >> N >> M;

    vector<long long> tree(N);

    for (int i = 0; i < tree.size(); i++) {
        cin >> tree[i];
    }

    long long left = 0;
    long long right = *max_element(tree.begin(), tree.end());
    long long mid;
    long long answer;

    while (left <= right) {
        mid = (left + right) / 2;
        if (cut(mid, tree, N, M)) {
            answer = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    cout << answer;

    return 0;
}

https://www.acmicpc.net/problem/2003

풀이 과정

i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하면 된다.

for문 중첩시키고 모든 연속구간을 만들어 보는 방법으로는 시간제한 내로 문제를 해결할 수 없다. 간단하게만 생각해봐도 N이 만까지 들어오는데 O(N^2) 알고리즘만 되도 TLE가 날 가능성이 있다. 투 포인터 알고리즘을 사용하면 O(N)으로 해결할 수 있다.

l, h 두 개의 포인터를 조절해가며 문제를 해결하였다.

소스 코드

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, sum, number, answer, l, h;
    sum = 0; l = 0; h = 0; answer = 0;
    vector<int> vec(N);
    cin >> N >> M;

    for (int i = 0; i < N; i++) {
        cin >> vec[i];
    }

    while(true) {
        if (sum >= M) {
            sum -= vec[l++];
        } else if (h == N) {
            break;
        } else {
            sum += vec[h++];
        }

        if (sum == M) {
            answer++;
        }
    }
    cout << answer;
    return 0;
}

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

풀이 과정

문자열을 살펴보면서 같은 알파벳이 2개 짝지어지는 부분은 지워주면 된다.

for i in range(len(a)):
        if a[i] == a[i+1]:
            a = a[:i] + a[i+2]

처음에는 위와 같은 문자열 조작을 통해 문제를 해결하려 했는데 이건 반복도 잦고 너무 시간이 오래 걸려 테스트를 통과할 수 없다.

문자열을 스택에 넣으면서, 넣으려는 문자가 스택 탑이랑 같으면 문자를 넣지 말고 스택 탑에 있는 문자를 꺼내고, 같지 않으면 문자를 넣는 방식으로 더욱 짧은 시간내로 간편하게 문제를 해결할 수 있다.

소스 코드

def solution(s):
    stack = []
    
    for i in s:
        if stack and stack[-1] == i:
            stack.pop()
        else:
            stack.append(i)
    
    return 1 if not stack else 0

https://programmers.co.kr/learn/courses/30/lessons/17677

풀이 과정

2개의 문자열을 줄테니 문자열을 2글자씩 끊어서 자카드 유사도를 구하고, 65535를 곱하고 정수형으로 반환해달라는 문제이다.

upper(), lower(), isalnum(), isalpha(), isdigit() 등의 파이썬 내장함수를 알고 있다면 더 편하게 풀 수 있다.

문제에서 소문자, 대문자를 같게 취급하라 하였으니 문자열을 전부다 upper()로 대문자로 바꿔주고 시작했다.

문자열을 2글자씩 끊고, isalpha()로 알파벳이 아닌 것이 있으면 무시하고, 알파벳이면 딕셔너리에 넣으면서 문자열에서 몇번 나왔는지 체크해 주었다.

집합 a + 집합 b - a, b의 교집합 = a, b의 합집합임을 이용해서 딕셔너리를 순회하면서 집합 a, b와 합집합과 교집합을 구했다.

소스 코드

def solution(str1, str2):
    string_dict = {}
    string_dict2 = {}
    str1 = str1.upper()
    str2 = str2.upper()
    
    for i in range(len(str1)-1):
        string = str1[i] + str1[i+1]
        if not string.isalpha():
            continue
        if string in string_dict:
            string_dict[string] += 1
        else:
            string_dict[string] = 1
    for i in range(len(str2)-1):
        string = str2[i] + str2[i+1]
        if not string.isalpha():
            continue
        if string in string_dict2:
            string_dict2[string] += 1
        else:
            string_dict2[string] = 1

    a_size = 0
    b_size = 0
    for i in string_dict.values():
        a_size += i
    for i in string_dict2.values():
        b_size += i
        
    kyo_size = 0
    for i, j in string_dict.items():
        if i in string_dict2:
            kyo_size += min(j, string_dict2[i])
    
    hap_size = a_size + b_size - kyo_size
    
    return int(65536 * kyo_size / hap_size) if hap_size != 0 else 65536

https://programmers.co.kr/learn/courses/30/lessons/60058

풀이 과정

균형 잡힌 괄호 문자열을 줄 테니 올바른 괄호 문자열로 변환한 결과를 출력하라는 문제다.

균형잡힌균형 잡힌 괄호 문자열의 정의, 올바른 괄호 문자열의 정의, 균형 잡힌 괄호 문자열을 올바른 괄호 문자열로 바꾸는 방법을 전부 다 문제 지문에서 주었고, 문제가 시키는 대로 구현을 하면 된다.

1. 균형 잡힌 괄호 문자열 분리 방법

문자열의 앞에서 부터 (의 개수, )의 개수를 세면서 서로 같아지는 순간의 index까지 분리해 u, 그 이후는 v로 분리하면 된다 개수가 0, 0일 때 분리되지 않도록 주의해야 한다.

2. 올바른 괄호 문자열 판별법

스택을 써도 되지만 그냥 0으로 초기화된 정수 변수로도 판별할 수 있다. 

(을 인식하면 integer += 1

)을 인식하면 integer -= 1

문자열을 읽으면서 위와 같은 연산을 계속 해준다. 문자열을 읽는 도중에 integer가 중간에 0 이하로 떨어진다면, 괄호의 쌍이 맞지 않으므로 올바른 괄호 문자열이 아니라고 판단해주고, 문자열을 다 읽었는데 integer가 0이 아니라면 또 괄호의 쌍이 맞지 않으므로 올바른 괄호 문자열이 아니라고 판단해주면 된다. 다 읽었는데 integer가 0이면 올바른 괄호 문자열이라고 판단해주자.

ex) (()))( -> +1 +1 -1 -1 -1, 5번째 문자를 읽으면 -1이 됨

      (())( -> +1 +1 -1 -1 +1, 다 읽었는데 integer가 1임, 마지막 (에 대응되는 )이 없으므로 올바른 괄호 문자열이 아님

      (())() -> +1 +1 -1 -1 +1 -1, 문자열을 읽는 도중 정수가 음수로 떨어지지 않고, 다 읽으면 정수가 0으로 끝남, 올바른 괄호 문자열임

위의 2개만 알고 있으면 그냥 나머지는 문제에서 주어진대로 하면 된다.

소스 코드

def recursive_string(string):
    if string == '':
        return ''
    
    a, b = 0, 0
    for index in range(len(string)):
        if string[index] == '(':
            a += 1
        else:
            b += 1
        if a == b:
            u, v = string[:index+1], string[index+1:]
            break
    
    if right_string(u):
        return u + recursive_string(v)
    else:
        temp = '('
        temp += recursive_string(v)
        temp += ')'
        u = u[1:-1]
        for letter in u:
            if letter == '(':
                temp += ')'
            else:
                temp += '('
        return temp
        


def right_string(string):
    count = 0
    for letter in string:
        if letter == '(':
            count += 1
        else:
            count -= 1
        if count < 0:
            return False
    
    if count == 0:
        return True
    else:
        return False


def solution(p):
    return recursive_string(p)

https://programmers.co.kr/learn/courses/30/lessons/72411

풀이 과정

비문학 지문을 읽듯이 꼼꼼히 읽지 않으면 문제 이해가 어려울 수도 있었다. 문제 지문이 굉장히 긴데, 요약하자면 orders의 각 원소 order로 course가지 코스 요리를 구성할 때, 가장 많이 함께 주문한 단품 메뉴를 코스요리로 구성하는 경우를 리스트에 담아 출력해주면 된다.

안 그래도 이해하기 어려운데 문제를 요약하니 더욱 이해가 안 간다. 1번 예시를 살펴보자.

orders = ["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"]에서 1번째 손님이 주문한 ABCFG로 만들 수 있는 코스요리는 다음과 같다.

1. 코스 요리를 2가지 메뉴로 구성할 때

AB, AC, AF, AG, BC, BF, BG, CF, CG, FG

2. 코스 요리를 3가지 메뉴로 구성할 때

ABC, ABF, ABG, ACF, ACG, AFG, BCF, BCG, BFG, CFG

3. 4가지

ABCF, ABCG, ACFG, BCFG

4. 5가지

ABCFG

이렇게 모든 order에 대해 만들 수 있는 코스 요리를 구하고, 가장 많이 함께 주문한 단품 메뉴를 살펴보면 된다. 첫 번째 예시에서는 "ABCDE"에서 AC가 한 번, "AC"에서 AC가 또 한 번, "ACDE"에서 AC가 또 한 번, "ACDEH"에서 AC가 또 한번 나오면서 AC가 함께 주문된 경우가 4번이 된다. 2가지 메뉴로 코스요리를 만들 때, 4번보다 같거나 많이 나오는 경우는 없으므로 답에는 AC가 포함되고, AC를 제외한 다른 2가지 메뉴 코스요리는 답에 포함되지 않는다 (가장 많이 함께 주문된 단품 메뉴가 아닌 것이 되므로)

XW, WX등은 같은 코스요리로 처리하기 위해 적절히 sort()를 활용해주고, 가장 많이 함께 주문한 단품 메뉴 구성 이어도 2번 이상 등장하지 않으면 답에 포함되지 않음을 고려해주면서 문제를 해결하였다.

소스 코드

from itertools import combinations

def solution(orders, course):
    answer = []
    length_filter = {}
    for order in orders:
        for i in range(2, len(order) + 1):
            for j in combinations(order, i):
                word = ''.join(sorted(list(j)))
                if word in length_filter:
                    length_filter[word] += 1
                else:
                    length_filter[word] = 1

    length_list = sorted(length_filter.items(), key=lambda x:x[1], reverse=True)
    length_dict = {}

    for tupl in length_list:
        if tupl[1] < 2:
            continue
        length = len(tupl[0])
        if length not in course:
            continue
        if length in length_dict:
            if length_dict[length] == tupl[1]:
                answer.append(tupl[0])
        else:
            length_dict[length] = tupl[1]
            answer.append(tupl[0])

    answer.sort()
    return answer

https://programmers.co.kr/learn/courses/30/lessons/42889

풀이 과정

도달했으나 아직 미클리어 / 도달한 플레이어 수로 표현되는 실패율을 구하고, 각 스테이지를 실패율의 내림차순 순서대로 반환하되 실패율이 같으면 앞의 스테이지가 우선적으로 오게 해달라는 문제이다.

스테이지에 도착한 플레이어 수를 표현하는 arrive 리스트, 도착했으나 클리어를 하지 못한 수를 표현하는 non_clear 리스트를 선언하고, stages 리스트를 살펴보며 값을 변경해주었다. stage에 3이 들어왔다면 arrive 0 ~ 2가 1씩 늘어나고 non_clear[2]가 1이 늘어날 것이다.

그 후 temp에 [인덱스, 실패율]을 저장한 뒤 temp.sort(key=lambda x:x[1], reverse=True)로 실패율 내림차순으로 정렬해준 뒤 answer에 index만 넣어주어 문제를 해결하였다.

리스트 내부의 값을 전부 다 1씩 증가시키는 코드를 짤 때

for i in list:

    i += 1 (x)

for i in range(len(list)):

    list[i] += 1 (o)

임에 유의해야 한다. 위의 코드에서는 리스트에 아무런 변화가 없다.

소스 코드

def solution(N, stages):
    non_clear = [0 for _ in range(N)]
    arrive = [0 for _ in range(N)]

    for stage in stages:
        if stage == N+1:
            for number in range(N):
                arrive[number] += 1
            continue
        for number in range(stage):
            arrive[number] += 1
        non_clear[stage-1] += 1

    temp = []
    answer = []
    for number in range(N):
        if arrive[number] == 0:
            temp.append([number + 1, 0])
            continue
        temp.append([number + 1, non_clear[number] / arrive[number]])

    temp.sort(key=lambda x:x[1], reverse=True)

    for item in temp:
        answer.append(item[0])

    return answer

https://programmers.co.kr/learn/courses/30/lessons/42888

풀이 과정

아이디를 변경하면 이전 입장 퇴장 메세지의 표시된 아이디까지 모두 변경될 때, 최종적으로 방이 개설한 사람이 보게되는 메세지를 구해달라는 문제이다.

record를 2번 순회하면 된다. 1번째는 Enter, Change를 살펴보면서 최종적으로 유저 아이디가 어떤 닉네임에 대응되는지를 구하고, 2번째에서는 Enter, Leave를 살펴보면서 유저 아이디에 최종적으로 대응되는 닉네임을 출력해주면 된다.

유저 아이디를 키, 닉네임을 밸류로 갖는 딕셔너리를 사용하여 밸류값을 갱신해가면서 문제를 해결하였다.

소스 코드

def solution(record):
    answer = []
    uid_nickname = {}
    
    for rec in record:
        rec_list = rec.split()
        if rec_list[0] in ['Enter', 'Change']:
            uid_nickname[rec_list[1]] = [rec_list[2]]
    
    for rec in record:
        rec_list = rec.split()
        if rec_list[0] == 'Enter':
            answer.append(f'{uid_nickname[rec_list[1]][-1]}님이 들어왔습니다.')
        elif rec_list[0] == 'Leave':
            answer.append(f'{uid_nickname[rec_list[1]][-1]}님이 나갔습니다.')
        
    
    return answer

https://programmers.co.kr/learn/courses/30/lessons/60057

풀이 과정

문자열을 몇개 단위로 잘라서 압축해야 가장 짧은 압축 문자열이 되는지 고려하면서 그때의 압축 문자열의 길이를 구하는 문제이다.

aaaabbbb는 4a4b, 2a2a2b2b, aaaabbbb가 가능하다. 높은 숫자 단위로 압축해야 가장 짧은 문자열이 될까?

aaaabbbbaaaabbbb는 8개 단위로 자르면 2aaaabbbb이고 4개 단위로 자르면 4a4b4a4b이다. 4개 단위로 잘랐을때 압축 문자열이 더 짧다. 몇 개로 잘라야 가장 짧은 압축 문자열이 되는지는 미리 알 수 없고 다 구해봐야 알 수가 있다.

k개 단위로 자른다고 할 때, 1 ~ len(문자열) // 2 + 1 범위로 일일이 잘라서 문자열을 만들어서 답을 구할 수 있다.

k가 전체 문자열의 길이의 반을 넘을 수는 없다. 넘으면 압축이 되는 경우가 전혀 없기 때문이다

소스 코드

def string_cut(string, cut):
    string_list = []
    number = 1
    real_string = ""
    length = len(string)
    string_list = [string[i:i+cut] for i in range(0, len(string), cut)]
    list_length = len(string_list)
    
    for i in range(1, list_length):
        if string_list[i-1] == string_list[i]:
            number += 1
        else:
            if number == 1:
                real_string += string_list[i-1]
            else:
                real_string += str(number)
                real_string += string_list[i-1]
            number = 1
    
    if string_list[list_length-2] == string_list[list_length-1]:
        real_string += str(number)
        real_string += string_list[list_length-1]
    else:
        real_string += string_list[list_length-1]
    
    return len(real_string)
    


def solution(s):
    answer = 12345678
    if len(s) == 1:
        return 1
    for i in range(1, len(s) // 2 + 1):
        temp = string_cut(s, i)
        if answer > temp:
            answer = temp
    return answer

https://programmers.co.kr/learn/courses/30/lessons/12935

풀이 과정

입력받은 배열의 길이가 1이면 [-1]을 리턴해주고 아니면 가장 작은 원소의 값을 제거한 배열을 리턴해주면 된다.

i != j 이면, arr[i] != arr[j]라는 조건이 있으므로 같은 원소일때는 어떻게 할지 처리해 줄 필요가 없다.

list.remove(3) -> list 리스트에서 가장 먼저 탐색된 3 원소를 제거한다

위의 예시를 생각하며 문제를 해결할 수 있다.

소스 코드

def solution(arr):
    if len(arr) == 1:
        return [-1]
    arr.remove(min(arr))
    return arr