Algorithm/Programmers (15) 썸네일형 리스트형 [프로그래머스 코딩테스트 고득점 Kit - 스택/큐] 기능개발 구현 문제 programmers.co.kr/learn/courses/30/lessons/42586 [문제 풀이] 동시에 배포되는 기능의 개수를 순서대로 묻는 문제입니다. 뒷 순서의 기능이 먼저 배포되어도 이전 단계가 배포되지 않는다면 기다렸다가 한 번에 배포합니다. 즉 배포되지 않은 가장 앞 순서의 기능보다 뒷 순서가 더 짧은 시간이 걸린다면 그들을 그룹으로 묶고, 더 오래 걸리는 기능이 뒷 순서에 등장한다면 묶은 그룹의 크기를 answer에 넣고 그룹의 기능들이 배포되었다고 확정하면 됩니다. 그렇다는 것은 그룹을 구성할지 새로운 그룹을 만들지는 현재 순서의 기능과, 그룹의 가장 첫 번째 기능의 시간만 계속 비교해주면 됩니다. 그래서 큐를 사용합니다. 큐는 그룹의 역할을 합니다. 가장 첫 번째, 가장 먼.. [프로그래머스 코딩테스트 고득점 Kit - 스택/큐] 주식가격 스택 문제 programmers.co.kr/learn/courses/30/lessons/42584 [문제 풀이] 주식의 가격이 떨어지지 않는 기간을 구하는 문제입니다. 단순하게 생각한다면 이중 for문을 사용하여서 현재 가격이 유지되는 시간을 구하면 풀이가 가능합니다. 그러나 위의 풀이는 $O(N^2)$의 시간 복잡도를 갖고 배열의 크기 N의 최대가 100,000이므로 효율이 매우 떨어집니다. $O(N^2)$의 풀이가 통과가 되는 것 같지만 실제로는 그렇게 풀면 안 됩니다. 주어진 순서대로 특정 상태가 유지되는지 확인하는 문제이므로 스택의 느낌이 납니다. 예시로 어떻게 푸는지 흐름을 보여드리면 스택으로 풀이할 방법이 보일 겁니다. prices가 [1, 2, 3, 2, 0, 1]처럼 주어져 있다고 가정하겠.. [프로그래머스 코딩테스트 고득점 Kit - 스택/큐] 다리를 지나는 트럭 구현 문제 programmers.co.kr/learn/courses/30/lessons/42583 오래 걸린 문제입니다. 알고리즘 풀이를 많이 해도 구현 문제를 연습하지 않으면 상당히 어렵습니다. [문제 풀이] 순서가 정해져 있는 트럭들이 다리를 지나는 데에 걸리는 최소 시간을 구하는 문제입니다. 다리의 특징은 먼저 들어간 트럭이 먼저 나와야 한다는 것입니다. 여기서 우리는 큐를 떠올려야 합니다. 이제부터 다리를 큐라고 생각하겠습니다. 어떻게 풀이해야 하는지 한 번에 감이 오지 않습니다. 그러므로 해야 하는 작업을 나눠서 생각해보겠습니다. 새로운 트럭이 다리에 들어올 때, 다리의 용량이 버틸 수 없다면 새로운 트럭이 지나갈 수 있을 때까지 다리 위의 트럭들을 건너 보냄 새로운 트럭이 다리에 들어올 때, .. [프로그래머스 코딩테스트 고득점 Kit - 해시] 베스트앨범 해시 문제 programmers.co.kr/learn/courses/30/lessons/42579 [문제 풀이] 총 재생 수대로 장르를 정렬하고 장르 내에서도 가장 많은 재생 수와 두 번째로 많은 재생 수를 가진 고유 번호를 순서대로 출력하는 문제입니다. 문제를 이해하는 것조차 쉽지 않습니다. 요약하자면, 총 재생 수대로 장르를 정렬하고 그 장르 내에서도 가장 많은 재생 수를 가진 두 곡을 차례로 answer에 넣는 문제입니다. 단, 한 장르 내에 곡이 한 개인 경우 한 곡만 넣습니다. 한 번에 하려고 하면 머리가 아프니 한 개씩 천천히 생각해 봅시다. 우선 장르 별로 정렬할 필요가 있으니 장르 별 총 재생 수를 기록합시다. 이 과정까지는 간단한 해시 문제입니다. 맵을 하나 만들어 key로 장르 이름을 .. [프로그래머스 코딩테스트 고득점 Kit - 해시] 위장 해시 문제 programmers.co.kr/learn/courses/30/lessons/42578 [문제 풀이] 한 가지 이상의 의상을 사용하여 조합할 수 있는 경우의 수를 구하는 문제입니다. 다른 종류의 옷들을 조합하는 문제입니다. 주의할 점은 하나의 옷을 입고 나면 나머지는 입지 않는 경우가 존재합니다. 간단한 경우의 수 문제입니다. 2개의 옷과 3개의 모자가 존재할 때, 가능한 조합의 수가 6개라는 건 자명합니다. 하지만 입지 않는 경우를 넣어 조금 문제를 어렵게 보이도록 하였습니다. 우선 map을 하나 만들고 주어진 의상 배열을 순회하면서 key로는 의상의 종류를, value로는 가짓수를 기록합니다. 예를 들어 [[yellow_hat, headgear], [blue_sunglasses, eyewe.. [프로그래머스 코딩테스트 고득점 Kit - 해시] 전화번호 목록 문자열 문제 programmers.co.kr/learn/courses/30/lessons/42577 www.acmicpc.net/problem/5052 위 문제와 동일한 문제입니다. [문제 풀이] 주어진 문자열이 접두어에 해당하는지 판별하는 문제입니다. 해시 파트에 있지만 문자열로 풀었습니다. 이 문제를 처음 백준 온라인 저지에서 봤을 때 해시로 푼다는 생각은 전혀 없었습니다. 정해라고 생각했던 풀이는 문자열을 정렬하고 인접한 두 문자열을 비교하는 방법이었습니다. $O(NlogN)$의 시간 복잡도로 해결이 가능합니다. 그리고 트라이 자료구조를 이용하여 $O(NL)$의 시간 복잡도로 해결이 가능합니다. 트라이의 연습을 위해 트라이 자료구조를 사용하였습니다. 트라이에 문자열을 넣으면서 문자열의 끝에 해당하는.. [프로그래머스 코딩테스트 고득점 Kit - 해시] 완주하지 못한 선수 해시 문제 programmers.co.kr/learn/courses/30/lessons/42576 [문제 풀이] 두 집합의 차집합을 구하는 문제입니다. 집합에서 중복을 허용했으므로 set이 아닌 map을 사용하였습니다. map의 key로 문자열을, value로 동명이인의 수를 기록합니다. 그리고 completion에서 명단을 하나씩 확인하면서 map의 value를 1씩 줄여나갑니다. value가 1이었던 경우 map에서 삭제합니다. 두 집합의 크기 차이가 1이었으므로 위의 과정을 완료하면 map에는 하나의 값만 남게 되고 그 값의 key(string)를 출력하면 해결이 가능합니다. c++의 map은 레드블랙트리 기반이므로 삽입, 삭제, 탐색 모두 $O(logn)$의 시간 복잡도를 갖습니다. Java의 H.. 이전 1 2 다음
