프로그래머스_Lv.3
1.C++:: 프로그래머스 <베스트앨범>
앨범 곡 수록순서의 조건은총 플레이 횟수가 많은 장르가 먼저 수록되어야 하고 해당 장르 내에서는 각각 플레이가 많이된 순서이다. 각 곡의 플레이 횟수가 같다면 genres에 등록된 인덱스 순으로 한다.
2.C++:: 프로그래머스 <디스크 컨트롤러>
우선순위 큐를 원하는 대로 정렬하는 방법에 대해 알게되는 문제였다. 아래 예시와 같이 구조체에 operator함수를 만들어서 비교하는 방식으로 구현할 수 있다. 이외에도 문제자체가 좀 난해해서 다른 풀이들을 참조하였다. 여러번 풀면서 완전히 체득하는 편이 좋을것같아보이
3.C++:: 프로그래머스 < 입국심사 >
처음에 비슷하게 접근을 하였지만 잘 풀리지않아서 찾아서 공부한 코드이다. 단순 이분탐색이긴한데 몇명이 지나갔는지를 체크하는 부분에서 애를먹었었다.
4.C++:: 프로그래머스 < 연속 펄스 부분 수열의 합 >
dp문제이다. 처음 주어진 수열에 펄스 수열을 곱해준 두개의 수열로 나누어서 해당 조건의 최대값을 구하면 된다.코드의 핵심적인 부분은 이전까지의 합 + 현재값 < 현재값 이면 이면 해당 인덱스의 dp는 현재값으로 넣어준다는 것이다.예시로 -1 -2 3 -2 4 과
5.C++:: 프로그래머스 < 억억단을 외우자 >
생각보다 간단한 문제인데 시간초과 때문에 애를 먹은 문제이다. 핵심적인 문제의 풀이는 해당 구간의 수들중 약수의 개수가 가장 큰 값(중복이면 작은 값)을 찾아주면 되는 문제이다. 이때 해당구간에서 v.begin() - max_element(v.begin()+s, v.b
6.C++:: 프로그래머스 < 인사고과 >
시간초과때문에 고생을 많이 한 문제이다. 첫풀이와 두번째 풀이를 합치고 최적화하여 통과하였다.첫번째 풀이는 인덱스를 주어진 벡터에 추가해주고 정렬한다음에 각 사람에 대해 인센티브 여부를 체크해 조건이 안된다면 점수를 -1로 변환하여 마지막에 몇등인지를 세주는 방식이었다
7.C++:: 프로그래머스 < 숫자 타자 대회 >
푸는데 상당히 오래걸린 문제이다. 풀이의 핵심은 먼저 숫자에서 타켓 숫자 까지의 가중치값을 구하고, unordered_map에 최종 자판과 가중치값을 넣어서 준다. 이를 통해 중복되는 경로 에대해서 최소값에 대한 계산을 하기떄문에 계산이 적어지게된다.
8.C++:: 프로그래머스 < 등대 >
접근은 비슷하게 하였으나 코드가 상당히 난잡해지고 메모리 사용 제한에 걸려서 다른 분의 풀이를 참고하였다. 해당 풀이의 핵심적인 부분은 부모에서 자식 노드로 타고 들어가면서 만약 부모 또는 자식 노드의 등대가 불이 안켜졌다면 켜주는 방식의 풀이이다.
9.C++:: 프로그래머스 < 부대복귀 >
처음에 dfs로 접근을 했다가 시간초과가 난 문제이다. bfs로 접근하여 풀면 쉬운문제이지만 해당 방법이 생각나지않아서 애를 먹은 문제이다.문제 풀이의 핵심은 목표지점에서 역으로 카운트를 한다는 점이다.
10.C++:: 프로그래머스 < 2차원 동전 뒤집기 >
본인의 풀이는 현재 보드에서 나올 수 있는 모든 가지수를 구해서 최소뒤집는 횟수를 리턴해주는 방식이다.하지만 좋은 풀이가 아니므로 아래의 다른 코드를 참고하자.
11.C++:: 프로그래머스 < 카운트 다운 >
처음에는 queue를 사용하여 풀라하였는데 시간초과가 났고, 생각을 해보니 굳이 queue로 풀지않고 비슷한 방식으로 dp처럼 사용해 풀어도 되겠다는 생각을 하였다.문제자체는 크게 어렵지않다.
12.C++:: 프로그래머스 < 파괴되지 않은 건물 >
누적합을 사용하여야 효율성 테스트를 통과할 수 있는 문제이다.누적합에 대한 간단한 예시를 보여주자면n = 4, m = 5인 배열에서 (0, 0) 부터 (2,3)까지 3을 더하고 싶다 가정해보자.0 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 0초기 0으로
13.C++:: 프로그래머스 < 이중우선순위큐 >
주어진 조건의 입력값에 따라 규칙에 따른 연산을 해주면 된다. 모든 연산을 하고 남은 데이터에 대한 최소 최대값을 벡터에 담아 리턴해주면 된다.map의 iterator를 다루는게 조금 까다로울 수 도 있는 문제이다.
14.C++:: 프로그래머스 < 정수 삼각형 >
간단한 dp문제이다. 주의할 점은 주어지는 triangle의 배열 크기가 n x m 크기로 들어오는게 아니라는 점이다.
15.C++:: 프로그래머스 < 네트워크 >
그래프 문제에서 bfs를 활용하여 푼 문제이다.다른 간단한 dfs 풀이도 참조한다.
16.C++:: 프로그래머스 < 최고의 집합 >
문제 조건을 확인했을때 자연수의 개수가 10000까지인걸 보면 직접 집합을 구하면 시간초과가 난다는 점을 판단할 수 있다. 때문에 최고의 집합을 판단하는 방법에 대해 생각을 했을 떄 각 수가 고르게 나누어지면 된다는 점을 알 수 있다.예시로 9 100 이 들어오게된다면
17.C++:: 프로그래머스 < 야근 지수 >
야근 지수가 가장 적게끔 일을 해서 그 결과를 리턴해 주면 되는 문제이다. 최대한 높은 작업량 순으로 하나씩 일을 하면 된다.
18.C++:: 프로그래머스 < 단어 변환 >
주어진 begin에서 target으로 words안에 있는 단어들을 통해 변환 가능한지 판단하고 가장 적은 회수를 반환하는 문제이다. 크게 어렵지않다.해당 풀이에서는 역숙으로 구현하였다.
19.C++:: 프로그래머스 < 등굣길 >
전형적인 dp문제이다. 당연히 dfs와 같은 풀이로 구현하면 시간 초과가 나게된다.
20.C++:: 프로그래머스 < 숫자 게임 >
제한사항들을 확인해 보면 최적의 계산이 필요한 문제임을 알 수 있다. 해당풀이는 두 배열을 오름차순으로 정렬하고 Bi 가 A의 원소들중 몇번째로 큰지를 체크해주어서 이기는 회수를 최대로 계산하는 풀이이다.
21.C++:: 프로그래머스 < 단속카메라 >
문제의 핵심은 최대한 중복이 많이 되는 구간에 단속카메라를 놓아야 최소로 놓을 수 있다는 점이다.
22.C++:: 프로그래머스 < 기지국 설치 >
제한조건의 범위가 상당히 크기 때문에 직접 배열로 생각하면 안되는 문제이다. 간단하게 전파가 필요한 범위를 구해서 최소 몇개의 기지국을 설치해야하는지 계산해 주면 된다.
23.C++:: 프로그래머스 < 스티커 모으기(2) >
전형적인 dp문제이다. 주의해야할 점은 스티커가 원형으로 이어져있기 때문에 맨처음 스티커를 고르는 것과 아닌 것, 두가지의 경우에 대해 dp를 구해야 한다.
24.C++:: 프로그래머스 < 불량 사용자 >
핵심은 불량사용자 문자열에 똑같은 문자열이 있을때의 처리를 어떻게 해주냐이다.
25.C++:: 프로그래머스 < 보석 쇼핑 >
로직을 생각하는게 중요한 문제이다. 해당 코드의 핵심은 시작과 끝 인덱스를 기준으로 기준에 부합하면 기억을 해주고, 시작인덱스와 끝 인덱스를 적절히 미루면서 최소 구간을 찾는 방식이다.
26.C++:: 프로그래머스 < 징검다리 건너기 >
얼핏 deque를 사용하여 푸는 방법을 구상했지만 제대로 로직을 구현하지 못한 문제이다. 잘푼 풀이를 참조한다.해당 풀이의 핵심은 dq에 쌓아가면서 맨앞에 있는 징검다리의 인덱스가 현대 인덱스 - (k-1) 한 인덱스보다 작지 않을때 까지 dq를 갱신해주고,dq의 뒷부
27.C++:: 프로그래머스 < 가장 먼 노드 >
그래프를 구현하는데 주어진 노드의 개수가 20000개 정도로 적기 때문에 이중벡터로 구현해도 된다.
28.C++:: 프로그래머스 < 섬 연결하기 >
말그대로 섬을 연결하는 최소 비용을 구하면 되는 문제이다. 핵심은 최소 비용의 다리들을 연결하되 연결하고자하는 섬들이 이미 이어져있다면 넘겨야한다는 점이다.
29.C++:: 프로그래머스 < 여행경로 >
dfs를 사용하여 모든 티켓을 사용하는 경우 중 사전순으로 가장 빠른 것을 반환해주면 되는 문제이다. 주의해야 할 점은 중복되는 경로의 티켓이 들어올 수도 있고 이에 대한 방문처리를 잘 해주어야 한다는 점이다. 예시로 A -> B 티켓이 여러장 일 수 있고 이에 대한