본문 바로가기

대딩192

[프로그래머스 lv2] 소수 찾기 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 문자열에 주어진 숫자들로 만들 수 있는 모든 순열과 순열의 부분집합에 대하여 소수인 것의 개수를 리턴하는 문제이다. 먼저, 문자들로 만들 수 있는 모든 수들을 탐색하기 위해 백트래킹(재귀)를 사용한다. 배열에 저장된 인덱스를 숫자로 바꾼 뒤, 해당 수가 소수인지 확인한다. 소수인지 확인할 떄는, isPrime() 함수를 별도로 만들어 일일이 호출하기 보다, 에라토스테네스의 체를 활용하여 한번에 소수를 확인하는 배열을 만들어놓고 O(1)에 처리한다. 아래의 코드에서는 check 배열을 false로 초기화해 놓고, 소수가 아닐 경우와 이미 카운트 했을 경우에 check[i] 값을 true로 변환하였다. 함꼐 참고하면 좋을 포스트 바킹독님의 실전알고리즘-백.. 2022. 8. 12.
[프로그래머스 lv2] 다음 큰 숫자 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 n을 이진수로 변환했을 때 1의 개수를 카운트하여, 같은 1의 개수를 갖는 다음 이진수를 리턴하는 문제이다. n을 이진수로 변환했을 때 1의 개수를 세고, n+1 부터 숫자들을 탐색하며 같은 1의 개수를 갖는 수를 찾는다. 주의 백준의 경우 대부분 문제의 시간 제한이 1초라서, 해당 문제를 1초 내에 돌아가는 다른 풀이로 먼저 제출을 했었다. 그런데 TLE이 남... 고수님께도 질문을 해봤으나, 이 문제의 시간복잡도가 너무 타이트하다는 결론을 내렸다. 혹시 자신의 풀이가 1초(연산 횟수 10^8) 내에 들어오는데 자꾸 시간초과가 난다면 너무 자책하지말고 프로그래머스를 약간 탓해보자.(관계자님 보고 계시나요...!) 코드 #include #include.. 2022. 8. 12.
[프로그래머스 lv2] 주식 가격 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 각 인덱스에 대하여 처음으로 가격이 떨어지는 인덱스를 구해 리턴하는 문제이다. 가장 먼저 이중 for문을 사용한 풀이가 떠오른다. vector solution(vector prices) { vector v(prices.size(), 0); for (int i=0; i 2022. 8. 12.
[프로그래머스 lv2] 영어 끝말잇기 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 단어들을 순회하면서 해당 단어가 조건에 맞지 않는다면, [해당 단어를 말한 사람, 그 사람이 자신의 몇 번째에 탈락하는지]를 리턴하는 문제이다. 끝말잇기를 진행하는 총 사람의 수가 n명일 떄, words를 순회하는 인덱스 i에 대하여, i번째 단어는 i%n+1번째 사람이 말하고, 그 사람은 i/n+1 번째로 단어를 말하는 중이다. (인덱스는 0부터 시작하므로 몫과 나머지 계산에 각각 1을 더해준다.) 단어를 순회하면서, 1. 단어의 길이가 1인 경우 2. 해당 단어가 이전 단어의 끝글자로 시작하지 않는 경우, 3. 이미 중복된 경우 [i%n+1, i/n+1]을 리턴하면 정답이다. 단어가 중복되는지 확인할 때는 해시 자료구조인 unordered_set을.. 2022. 8. 11.
[프로그래머스 lv2] 짝지어 제거하기 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 가장 단순한 풀이는 문자열 처음부터 연속된 문자들을 찾고, 이를 문자열에서 제거하는 과정을 반복하는 것이다. 하지만, 스택을 이용하면 문자열을 한번만 순회하고도 연속된 문자들을 짝지어 제거할 수 있다. 결론적으로, 문자들을 하나씩 스택에 넣되, 만약 가장 최근에 스택에 들어간 문자(top에 있는 문자)가 현재 넣으려는 문자와 같다면 이는 연속된 것이므로 바로 제거하면 된다. 예를 들어, 빈 스택 st 이 있고, 문자열이 "baabaa" 라 해보자. b -> 스택이 비었으므로 그냥 b 넣기(스택 상태: b) a -> top에 있는 문자가 b이므로 그냥 a 넣기(스택 상태: ba) a -> top에 있는 문자가 a이므로 연속되는 문자 제거(스택 상태: b.. 2022. 8. 11.
[프로그래머스 lv2] 더 맵게 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 모든 음식의 스코빌 지수를 K이상으로 만들기 위해 필요한 연산 횟수를 구하는 문제이다. 문제에서 주어진 연산은 가장 작은 스코빌 지수 두 개에 대하여 (가장 작은 스코빌 지수)+(두 번쨰로 작은 스코빌 지수)*2로 새로운 스코빌 지수를 만드는 것이다. 새로운 스코빌 지수를 만들 때 기존의 두 수는 사라진다. 두 수를 더해 새로운 수를 만들어가는 과정은 최대 O(n)이 걸린다.(점점 남아있는 수들이 줄어들기 때문) 따라서 가장 작은 두 수를 O(logn)으로 뺴낼 수만 있다면 문제의 전체 연산을 O(nlogn)에 해결 가능하다. 문제에서 최대 입력 범위가 1000000이므로, O(nlogn)에 문제를 해결할 있다면 효율성 테스트를 통과할 수 있다. 그렇.. 2022. 8. 11.
[프로그래머스 lv2] 프린터 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 문서를 순서대로 출력하되, 가장 앞에 있는 문서의 뒤쪽에 우선순위가 더 높은 문서가 있다면 현재 문서를 제일 뒤로 보내야 한다. 특별한 방법 필요없이, 문제에서 요구한 그대로 구현하면 정답을 받을 수 있다. 일단, 문서들의 초기 위치와 우선순위의 정보를 큐에 pair 형태로 저장해놓고, 해당 큐에서 하나씩 문서를 꺼내면서(프린트) location으로 주어진 문서가 몇번째로 프린트 되는지 확인하면 된다. 하나씩 문서를 꺼낼 때는, 큐의 가장 앞에 있는 문서가 남아있는 문서들 중에서 가장 높은 우선순위를 갖는지 확인하되, 가장 높은 우선순위를 갖지 않는다면 이를 큐의 가장 끝으로 보낸다. 반복해서 문서들을 뒤로 보내다가, 가장 높은 우선순위를 갖는 문서가.. 2022. 8. 10.
[프로그래머스 lv2] 위장 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 아이템의 종류와 이름이 주어졌을 떄, 가능한 모든 조합을 구하는 문제이다. 같은 종류의 아이템은 한번에 하나만 매치할 수 있고, 0개의 아이템을 매치하는 것을 제외하고는 모든 경우가 가능하다. 결론부터 말하자면, a1 종류의 아이템이 a2개, b1 종류의 아이템이 b2개, c1 종류의 아이템이 c2개 ... 있을 때, 가능한 모든 경우의 수는 (a2+1) * (b2+1) * (c2+1) * ... -1 이다. 한 종류의 아이템에 대하여, 한번에 하나만 매치하거나 아에 매치하지 않을 수 있으므로 (아이템의 개수 + 0이라는 경우의 수 1)이 가능하다. 이를 모두 곱해주면 가능한 모든 경우의 수가 나오는데, 문제에서 모든 아이템을 매치하지 않는 경우는 제.. 2022. 8. 10.
[프로그래머스 lv2] 멀리 뛰기 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 대표적인 dp 유형이다. 효진이가 n번째 칸에 도달할 때, 다음과 같은 두가지 방법이 가능하다. 1. n-1번째 칸까지 뛰고 마지막 한칸을 뛰어 n번째 칸에 도달하는 방법 2. n-2번째 칸까지 뛰고 마지막에 두칸을 뛰어 n번째 칸에 도달하는 방법 따라서, dp[n]을 n번째 칸까지 뛰는 경우의 수라고 할 때, dp[n] = dp[n-1](n-1번쨰 칸까지 도달하는 경우의 수) + dp[n-2](n-2번째 칸까지 도달하는 경우의 수)로 점화식을 세울 수 있다. 초항 dp[1] = 1, dp[2] = 2를 설정해주고, dp[i]를 구할 때마다 1234567로 나눈 나머지를 저장한다. 이후, dp[n]을 리턴하면 정답이다. 코드 #include #incl.. 2022. 8. 10.
[프로그래머스 lv2] 전화번호 목록 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 phone_book 배열 내 문자열들에 대하여, 특정 문자열이 다른 문자열의 접두사가 될 때 false를 리턴하는 문제이다. 가장 쉽게 떠올릴 수 있는 방법은, 이중 for문으로 모든 문자열들을 맞춰보면서 특정 문자열이 다른 문자열의 접두사인지 확인하는 것이다. 그러나 해당 방법의 시간복잡도는 O(N^2)으로 비효율적이다. 그렇다면, phone_book 배열을 단일 for문으로 한번만 순회하면서 문제를 해결할 수 있을까? (당근 있다!) phone_book의 문자열 길이 순으로 먼저 정렬해 놓는다면, 특정 문자열의 접두사는 해당 문자열 위치의 앞쪽에 있을 것이다. 예를 들어, ["119237", "119", "11", "119240"]을 길이 순으로 .. 2022. 8. 10.

티스토리툴바