https://programmers.co.kr/learn/courses/30/lessons/42577 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr 문제를 보자마자 단순하게 2중 for문을 사용해서 다 확인해야겠다는 생각을 할 수도 있다. 하지만 그럴경우 시간 복잡도가 1,000,000 * 1,000,000이므로 시간초과가 날 것이다. HINT : 이 문제는 sort와 substr을 통하여 간단하게 해결 할 수 있다. 더보기 문제 접근법 phone_book을 sort한다. 일반적으로 sort시 오름차순으..
https://programmers.co.kr/learn/courses/30/lessons/49993 코딩테스트 연습 - 스킬트리 programmers.co.kr skill_trees에 있는 스킬트리중 익힐수 있는 스킬트리의 갯수를 출력하는 문제입니다. 문제 접근법 skill_trees의 원소에 접근해야하고, skill의 각각의 문자들을 skill_tress원소의 길이만큼 확인해야 하므로 3중 for문을 사용하면 좋을것 같다는 생각을 할 수 있습니다. skill의 최대 길이는 26, skill_trees의 최대 길이는 20, skill_trees의 원소의 최대 길이는 26입니다 그러므로 시간복잡도는 26 * 20 * 26으로 3중 for문을 사용해도 괜찮다는 결론이 나옵니다. 3중 for문을 돌며 ski..
programmers.co.kr/learn/courses/30/lessons/49993 코딩테스트 연습 - 스킬트리 programmers.co.kr 문제 접근법 skill 문자열에 있는 문자를 skill_trees에 있는 문자열에 있는 문자와 하나씩 비교한다. 해당하는 단어가 있을경우 skill의 몇번째 위치의 문자인지와 skill_trees의 원소의 몇번째 자리인지를 체크하여 pair로 vector에 넣어준다. 만약 다음 문자가 이전 문자의 위치보다 앞에 있다면 틀린 스킬 트리이므로 다음 스킬 트리를 검사한다. vector의 사이즈가 1보다 크고 skill_trees의 원소를 모두 체크한 경우 vector의 맨 앞값의 first가 0이 아니라면, 스킬 트리의 순서가 틀린것이므로, 다음 스킬트리를 검사한..
programmers.co.kr/learn/courses/30/lessons/60057 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자 programmers.co.kr 문제 접근법 1자리 부터 시작하여 문자열 길이의 절반까지의 길이 만큼의 문자의 중복을 체크한다. 문자열 길이 절반을 초과하면 중복이 나오지 않기 때문이다. 중복되는 문자의 갯수를 체크 후 중복 되지않는 문자를 만나면 중복되는 문자의 갯수와 해당 문자를 더한 문자열을 만든다. 중복 되지 않았던 문자를 기준으로 다시 중복을 체크한다. 만약 문자열의 길이 % 중복체크용 문자 ..
programmers.co.kr/learn/courses/30/lessons/42587 코딩테스트 연습 - 프린터 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린�� programmers.co.kr 문제 접근법 순서와 우선순위를 저장할 queue와 우선순위 순서대로 정렬할 때 사용할 priority_queue를 준비한다. for문을 priorities의 길이만큼 사용하여 queue에 순서와 우선순위를 push하고 priority_queue에 priorites의 값들을 넣어준다. queue의 맨 앞값의 second 값이 priority_queue의 최상단 값과 같지않다면 ..
programmers.co.kr/learn/courses/30/lessons/42586 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 �� programmers.co.kr 문제 접근법 progresses에 speeds의 값을 더해 100이 되는 날짜를 구한다. 이 날짜를 deque에 넣는다. 맨 처음 들어온 날짜 값을 기준으로 뒤에 들어온 날짜 값들이 큰지 작은지 비교한다. 작거나 같을 경우 앞에 기능이 끝날 때 같이 나가게 되므로 배포되는 값에 +1을 한다. 클 경우 deque에서 pop_front()를 진행 후 deque 내부가..
programmers.co.kr/learn/courses/30/lessons/42578 코딩테스트 연습 - 위장 programmers.co.kr 문제 접근법 map을 이용해서 카테고리의 갯수를 파악합니다. 전체의 조합의 갯수를 구하는 방법은 각 카테고리의 갯수 + 입지 않는 경우의 수를 더해서 모두 곱해주면 됩니다. 단, 옷을 하나도 안 입는 경우가 없으므로 -1을 해주어야 합니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include #include #include using namespace std; int solution(vector clothes) { int answer = 1; int len = clothes...
programmers.co.kr/learn/courses/30/lessons/42577 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조�� programmers.co.kr 문제 접근법 가장 작은 값을 앞으로 두기 위해 sort를 합니다. 맨 앞에 값을 가지고 다른 값의 접두어가 되는지를 체크하면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include #include #include using namespace std; bool solution(vector phone_book) ..
https://programmers.co.kr/learn/courses/30/lessons/42583 코딩테스트 연습 - 다리를 지나는 트럭 트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이�� programmers.co.kr 문제 접근법 먼저 진입한 트럭이 먼저 나가므로 queue를 사용합니다. vector에 접근하기 위한 index 및 다리 위에 올라간 트럭들의 무게를 합, 출력할 정답을 나타낼 변수를 선언합니다. 다리 위 트럭들의 무게와 다음 트럭의 무게의 합을 다리가 견딜수 있는 무게인지 비교합니다. 가능 할 경우 vector 인덱스 값이 truck_weig..
https://programmers.co.kr/learn/courses/30/lessons/12899 코딩테스트 연습 - 124 나라의 숫자 124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다. 124 나라에는 자연수만 존재합니다. 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다. programmers.co.kr 문제 접근법 나누기와 나머지를 이용하여 풀 수 있는 문제입니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 #include #include using namespace std; string solution(int n) { stri..
