Greedy

출처 프로그래머스 110 옮기기 접근 문제 분석 주어진 이진 문자열에서 110이라는 문자열을 이동시켜야 하는 문제입니다. 문자열에서 110을 제거한 뒤, 새로운 위치에 얼마나 빨리 삽입할 수 있는지가 포인트입니다. 주어진 문자열의 길이는 1,000,000으로, O(N)혹은 O(NlogN) 이내의 시간복잡도를 구현해야 합니다. 퓰이 우선 문제에서 주어진대로 110을 옮겨야 하기 때문에, 우선 110을 모두 제거하고 그 개수를 저장해야 합니다. 110 제거 그러나 문자열에서 110을 제거하는 과정이 만만치 않습니다. 문자열에서 단순히 110이라는 글자를 찾아 삭제하면 끝일 것 같지만, 다음과 같은 경우에는 한번에 끝나지 않습니다. 다음과 같이 문자열이 주어졌다고 가정해보겠습니다. 문자열에서 110을 제거하면, 다시 110이라는 문자열이 나타납니다. 따라서, 문자열에서 110이 나타나지 않을 때까지 110을 제거해야 합니다. 또한, 단순히 제거만 하는게 아니라 제거한 횟수를 별도로 저장해야 합니다. ...

출처 해커 랭크 : Non Divisible Subset 문제 설명 영문 사이트이므로 문제를 간단히 설명하겠습니다. 중복되지 않는 정수 배열(집합)이 주어집니다. 문제 예시에는 10이 중복되어 있는데 오타인 것 같습니다. K가 주어졌을 때, 두 수의 합이 k로 나누어 떨어지지 않는 부분 집합을 찾는 문제입니다. 부분 집합에서 임의의 두 수를 골라도 k로 나누어 떨어지지 않아야 하며, 부분 집합이 여러개가 있을 때는 최대 길이를 구해야 합니다. 접근 완전탐색 부분 집합을 만들 수 있는 각각의 경우에서 2개씩 고른 뒤 K로 나누어 떨어지는지를 일일히 확인하면 시간복잡도를 초과합니다. O(N! x nC_2) ...