PS/programmers (4) 썸네일형 리스트형 [프로그래머스] Level 2 124 나라의 숫자 문제 링크 programmers.co.kr/learn/courses/30/lessons/12899 풀이 [BOJ] 16265 Spreadsheets 문제와 매우 유사하다. 3진법처럼 계산하되 오프셋 계산을 해주면 된다. C++ 코드 더보기 #include using namespace std; string solution(int n) { string ret; for (; n; n = (n - 1) / 3) ret += "124"[(n - 1) % 3]; reverse(ret.begin(), ret.end()); return ret; } [프로그래머스] Level 2 숫자의 표현 문제 링크 programmers.co.kr/learn/courses/30/lessons/12924 풀이 1 $n$을 $k$개의 연속된 자연수의 합으로 나타낼 수 있는지 확인하려면 어떻게 해야할까? 차근차근 따져보도록 하자. $k$가 1이라면 $n$ 자기 자신으로 표현된다. $k$가 2라면 어떤 자연수 $m$과 $m+1$에 대해서 $n=m+m+1$이 성립해야 한다. 이는 $n$에서 1을 빼고 2로 나누어 떨어지는지 확인하면 된다. $k$가 3이라면 어떤 자연수 $m$, $m+1$, $m+2$에 대해서 $n=m+m+1+m+2$가 성립해야 한다. 이는 $n$에서 $1+2$를 빼고 3으로 나누어 떨어지는지 확인하면 된다. 규칙이 보이는가? 즉, $n$에서 1+2+...+k-1을 빼고 $k$로 나누어 떨어지는지 .. [프로그래머스] Level 2 다음 큰 숫자 문제 링크 programmers.co.kr/learn/courses/30/lessons/12911 풀이 n+1부터 시작해서 1씩 증가시키며 켜진 비트의 수가 같은 경우를 찾으면 된다. 이렇게 풀 경우 최악의 경우는 어떻게 될까? 대강 따져보자면 n은 최대 100만이므로 사용되는 비트의 수는 많아봤자 20개다. 20개의 비트를 재조정하는 것으로 항상 모든 답이 나올 수 있으니 연산의 수는 $2^{20}$을 넘지 않는다. C++ 코드 더보기 프로그래머스는 clang++으로 컴파일한다. gcc나 clang에는 켜진 비트의 수를 구하는 내장함수인 __builtin_popcount라는 함수가 있다. int solution(int n) { int cnt = __builtin_popcount(n); for (int .. [프로그래머스] Level 2 스킬트리 문제 링크 programmers.co.kr/learn/courses/30/lessons/49993 풀이 선행 스킬을 이용해 각 스킬을 배워야하는 순서를 배열에 1, 2, 3, ... 순서로 체크한다. 체크되지 않은 나머지 스킬들은 언제 배워도 상관 없으므로 적당히 0으로 둔다. 이제 각 스킬트리를 순회하면서 선행 스킬에 포함되는 스킬의 순서가 1, 2, 3, ... 순서로 증가하는지 확인한다. 이 순서가 지켜지지 않았다는 것은 불가능한 스킬트리라는 뜻이 된다. C++ 코드 더보기 #include using namespace std; int solution(string skill, vector skill_trees) { int order[26]{}; for (int i = 0; i < skill.size(.. 이전 1 다음