문제 https://leetcode.com/problems/find-the-lexicographically-smallest-valid-sequence 풀이 word1에서 인덱스를 고르고, 그 문자들로 word2를 만들면 된다. 선택한 문자는 순서를 유지해야 하고, word1의 문자 중 최대 하나는 다른 문자로 바꿔서 사용할 수 있다. 가능한 수열 중 인덱스가 사전순으로 가장 작은 것을 구하면 된다. 앞에서부터 무조건 현재 문자가 같은지 확인하면서 고르면 되지만, 문자가 다른 위치에서 변경 기회를 바로 사용해도 뒤쪽에 남은 문자를 모두 맞출 수 있는지 확인해야 한다. 즉, 현재 위치를 선택했을 때 남은 문자의 개수가 충분해야 한다. ...
문제 https://codeforces.com/problemset/problem/489/C 풀이 자리수가 m이고 각 자리수의 합이 s인 정수 중 가장 큰 수와 가장 작은 수를 찾는 문제이다. 처음에는 DP로 접근했는데, DP로는 수의 개수 정도만 구할 수 있고, 최대값과 최소값을 찾기는 힘들 것 같았다. 그래서 다시 그리디로 접근했다. 자리수가 m인데 $1 <= m <= 100$ 이기 때문에, int 타입으로 수를 다루는건 쉽지 않고, 배열이나 벡터로 다루는게 더 쉽다. 최대값은 계수가 높은 쪽에 큰 숫자를 배치하고, 최소값은 계수가 낮은 쪽에 큰 숫자를 배치하는 방법을 사용하자. ...
문제 https://leetcode.com/problems/minimum-number-of-pushes-to-type-word-i 풀이 휴대전화의 2에서 8까지의 숫자에 문자를 배치할 수 있고, 2개 이상의 수가 배치되었을 땐 여러번 눌러야 뒤에 있는 숫자를 타이핑 할 수 있다. 스트링 word가 주어졌을 때, 버튼을 가장 적게 눌러 word를 타이핑 했을 때의 타이핑 수를 리턴하면 된다. 각 키의 첫 번째 문자는 1번, 두 번째는 2번… 눌러야 하므로 많이 등장하는 문자일수록 누름 횟수가 적은 앞자리에 배치해야 한다. 빈도수 내림차순 정렬 후, 인덱스를 8로 나눈 몫 + 1이 해당 문자의 누름 횟수가 된다. ...
문제 https://leetcode.com/problems/smallest-palindromic-rearrangement-ii 풀이 1번 문제와 마찬가지로 팰린드롬의 성질상 절반만 결정하면 전체가 결정된다. 따라서 이 문제는 절반 문자열의 k번째 사전순 순열을 구하는 문제로 단순화된다. 각 문자의 등장 횟수를 세고, 홀수 번 등장하는 문자는 팰린드롬의 가운데에 배치한다. 나머지는 2로 나눠 halfTable을 만든다. 절반 문자열에는 중복 문자가 있을 수 있으므로, 전체 순열 수는 단순히 $n!$이 아니라 중복 순열 공식으로 구해야 한다. $$\frac{n!}{\prod_{i} n_i!}$$ 여기서 n은 절반 문자열의 길이, n_i는 각 문자의 개수이다. 이 값이 k보다 작으면 k번째 순열이 존재하지 않으므로 빈 문자열을 반환한다. ...
문제 https://leetcode.com/problems/maximize-active-section-with-trade-i 풀이 '0'와 '1'로만 이루어진 문자열 s가 존재하고, 문제에서 주어진 연산을 최대 1번 적용하여 문자열에 있는 '1'의 개수를 최대로 만든 뒤 그 개수를 리턴하면 된다. 주어진 연산은 다음과 같다. (순서대로 둘 다 적용해야 한다.) 양 옆이 '0'로 둘러싸인 연속된 '1' 블록 하나를 선택해서 모두 '0'로 바꾼다. 양 옆이 '1'으로 둘러싸인 연속된 '0' 블록 하나를 선택해서 모두 '1'으로 바꾼다. 문제에서 s의 양 옆에 '1'을 붙이라 했는데, 이때 추가된 '1'은 최종 반환값에 포함되지 않는다. ...
문제 https://school.programmers.co.kr/learn/courses/30/lessons/42884 풀이 그리디 문제다. 그리디는 따로 정석 구현이 있는 알고리즘이 아니라 일종의 컨셉이지만, 배열 + 그리디면 잘 알다시피 정렬이 중요한 경우가 많다. 단순하게 생각해보자, 문제에서 주어지는 것은 시작 위치와 종료 위치다. 그냥 종료하는 위치를 기준으로 오름차순 정렬한 후에 앞에서부터 탐색을 한다. 현재 자동차의 종료 위치에 카메라를 설치하고, 다음 자동차를 살펴본다. 다음 자동차의 시작 위치가 이전 자동차의 종료 위치(즉 카메라가 설치된 위치)보다 앞에 있으면 다음 자동차도 설치된 카메라를 만나게 된다. 그렇지 않다면 또 그 자동차의 종료 위치에 카메라를 설치하면 된다. ...
문제 https://www.acmicpc.net/problem/11000 풀이 정렬 후 그리디를 수행하는 전형적인 그리디 알고리즘 문제이다. 강의가 시작하는 시간과 끝나는 시간이 주어져 있으므로 배열에 입력으로 주어진 시간들을 저장한 다음에 정렬해서, 강의가 가장 많은 시간의 강의 수를 출력하면 된다. 알고리즘을 글로 표현하면 다음과 같다. 수업이 시작하는 시간과 끝나는 시간을 배열 lecture에 저장한다. 이때 배열은 [(Int, Bool)] 타입이며, Int에는 시간, Bool에는 강의가 시작하는 시간일 경우 true, 끝나는 시간일 경우 false를 저장한다. 배열 lecture를 정렬한다. lecture를 for 반복문으로 전체 순회한다. 튜플의 두 번째 원소가 true인 경우 현재 진행 중인 강의 수를 저장하는 변수 current의 값을 1 더한다. false인 경우 강의가 끝난 것 이므로 변수 current의 값을 1 뺀다. 이때, 배열 lecture를 시간순으로만 정렬하게 되면 문제에서 다음과 같은 부분 때문에 문제가 생긴다. ...
문제 https://www.acmicpc.net/problem/1049 풀이 6개 묶음 패키지의 가격과 낱개의 가격이 각각 여러 개가 주어졌을 때, 가장 적은 비용으로 n개 이상의 수를 채워야 하는 문제이다. 문제의 알고리즘은 다음과 같다. 패키지의 가격과 낱개의 가격이 같이 들어오므로 현재 가장 싼 패키지와 낱개의 가격과, 입력으로 들어온 가격을 각각 비교해서 갱신한다. 패키지만 샀을때, 낱개만 샀을때, 패키지와 낱개를 동시에 샀을때 세가지 경우를 비교해서 가장 비용이 낮은 값을 출력한다. 이 문제에서 구매 수량에 제한을 두지 않았으므로, 굳이 배열을 만들고 정렬을 할 필요가 없다. 패키지든 낱개든 무조건 가장 싼 가격만 알고 있으면 된다. ...