ALGORITHM/Greedy

    [leetcode] 1221. Split a String in Balanced Strings
    ALGORITHM/Greedy

    [leetcode] 1221. Split a String in Balanced Strings

    1221. Split a String in Balanced Strings 문제 Balanced string은 동일한 개수의 'L'과 'R'로 이루어있는 string을 의미합니다. 주어진 string s을 최대한 많은 balanced string으로 나눈 후 balanced string개수를 출력합니다. 풀이 Balanced string은 RL, LR, RRLL, LLLRRR, RRRLRLLL과 같이 R과 L의 개수가 동일한 string을 의미합니다. 따라서, L과 R의 개수를 각각 세어 동일한 개수만큼 나오면 balanced string이 하나 더 생긴 것으로 볼 수 있습니다. class Solution { public: int balancedStringSplit(string s) { int balanc..

    [leetcode] 605. Can Place Flowers
    ALGORITHM/Greedy

    [leetcode] 605. Can Place Flowers

    605. Can Place Flowers 문제 긴 화단에 중간 중간 식물이 심어져 있다. 식물은 바로 붙어서 자랄 수 없어 적어도 한 칸씩 띄워서 자라야 한다. flowerbed라는 integer array는 0과 1로 구성되어 있으며, 0은 비어있음을 의미하고 1은 식물이 심어져 있음을 의미한다. n 값은 새로 심고자 하는 식물의 수이고, n개를 심을 수 있을 경우 true이고 심을 수 없을 경우 false를 반환한다. 풀이 답안1의 경우는 discuss를 보지 않고 처음 풀었을 때 나온 답안이라 좀 코드 자체가 복잡해 보인다. 답안1은 flowerbed를 0번째 인덱스부터 반복문을 돌 때, i번째의 위치가 맨 처음인지, 맨 마지막인지, 중간인지 나누어 풀었다. 만약 i가 0이라면, (i+1)번째가 0..

    [leetcode] 455. Assign Cookies
    ALGORITHM/Greedy

    [leetcode] 455. Assign Cookies

    455. Assign Cookies 문제 i번째 아이는 g[i] 이상 사이즈의 쿠키를 받아야 만족하고, j번째 쿠키의 사이즈를 s[j]라고 한다. 이때, s[j] >= g[i]일 때 i번째 아이에게 j번째 쿠키를 줄 수 있다. 이 문제의 목적은 최대한 많은 아이들에게 만족할만한 쿠키를 나눠주는 것이다. 풀이 최대한 많은 아이들에게 쿠키를 나눠주어야 하므로, 각 아이들이 만족할만한 쿠키 사이즈 중 가장 작은 사이즈를 나눠줘야 한다. 따라서, 아이들이 만족할 쿠키 크기 벡터인 g 벡터를 오름차순으로 정렬하고 줄 수 있는 쿠키 사이즈 개수 벡터인 s 벡터를 오름차순으로 정렬해야 한다. 정렬된 벡터들의 값을 비교하면, 각 아이에게 줄 수 있는 최소 크기의 쿠키를 줄 수 있다. 답안 class Solution {..

    [leetcode] 392. Is Subsequence
    ALGORITHM/Greedy

    [leetcode] 392. Is Subsequence

    392. Is Subsequence 문제 string s와 string t가 문제에 주어지며 s가 t안에 속하는지 true or false로 답하는 문제이다. 여기서의 subsequence란, 오리지널 string에서 특정 문자들을 지웠을 때 나올 수 있는 string을 뜻한다. (예: "ace"는 "abcde"의 subsequece) 풀이 이 문제는, string s에 있는 각 문자들이 string t에 있는지 하나씩 확인하고 지나가면 된다. 즉, s의 첫 문자를 t의 첫 문자부터 비교하여 동일한 문자가 나오면 s의 다음 문자를 t의 다음 문자(s와 동일했던 문자 다음)와 비교하는 식으로 풀면 된다. 나는 s의 문자들이 모두 t에 있는지 체크하는 용도로 count 변수를 사용했는데, 해당 변수를 사용하..

    [leetcode] 122. Best Time to Buy and Sell Stock II
    ALGORITHM/Greedy

    [leetcode] 122. Best Time to Buy and Sell Stock II

    122. Best Time to Buy and Sell Stock II 문제 i번째 원소가 i일의 주식 가격을 의미하는 prices라는 array가 존재한다. 최대 이익을 얻을 수 있도록 알고리즘을 설계해라. 원하는 만큼 거래를 완료할 수 있다. (예: 주식 1개 구매 후 1개 파는 행위 반복 가능 → i일에 팔고, i일에 다시 구매 가능) Note: 동시에 여러 거래를 할 수 없다. (즉, 주식을 새로 구매하기 전에 기존 주식을 팔아야 함) 풀이 처음 이 문제에 접근할 때에 어떻게 하면 이익을 최대로 할 수 있을까 고민을 했다. 그래서, 큰 배열을 만들어서 거기에 각각의 경우를 다 저장하고 그 중 제일 큰 값을 찾아야 하는 줄 알았다. 생각해보니, prices = [1,2,3,4]라고 아래와 같은 결과..

티스토리툴바