본문 바로가기

대딩/프로그래머스풀이126

[프로그래머스 lv3] 선입 선출 스케줄링 풀이 해설 문제를 보자마자 오 이거 우선순위 큐 쓰면 되겠다 하고 빠르게 풀었다.n개의 작업을 처리할 때마다 가장 작업을 빨리 시작할 수 있는 코어를 찾고, 해당 코어의 다음 시작 지점을 수정하는 방법이다.시간복잡도도 O(NlogN)으로 여유롭다고 생각했는데... 이런! 효율성 통과가 안된다. int solution(int n, vector cores) { priority_queue, greater> pq; for (int i=0; i  다른 방법이 있을까 싶어서 시간대별 작업 현황을 그림으로 그려보았다.그랬더니, 일단 이분탐색을 이용하면 n개의 작업을 모두 처리할 수 있는 최소 시간을 구할 수 있겠다는 생각이 들었다. 1) 시간의 탐색 범위 시작을 first, 탐색 범위 끝을 las.. 2022. 9. 22.
[프로그래머스 lv3] 아이템 줍기 풀이 해설캐릭터 위치부터 아이템 위치까지 최단 거리를 구하는 bfs 문제이다.캐릭터 위치를 출발지로 하여 테두리에 해당하는 좌표들로 이동한다. 출발지로부터 각 좌표까지의 거리를 dist[x][y] 배열에 저장해 나가고, dist[아이템X][아이템Y]를 리턴하면 된다. 그럼, 테두리에 해당하는지 여부는 어떻게 표시할 수 있을까?전체 직사각형의 영역을 먼저 표시한 후 사각형 내부만 다시 0으로 변경하면 된다. //x: 세로좌표, y: 가로좌표로 처리//직사각형 부분을 1로 채우기for (int i=0; i  그런데, 위와 같이 구현하면 이동방향이 명확히 표현되지 않는 경우가 발생한다.예를 들어, 문제에서 제시한 [[1,1,7,4],[3,2,5,5],[4,3,6,9],[2,6,8,8]] 의 테두리를 표시해보자.하늘.. 2022. 9. 21.
[프로그래머스 lv3] 매칭 점수 풀이 해설웬만한 문제는 c++로 푸는 것을 선호하지만, 문자열 + 정규표현식을 사용하면 편할 것 같아 파이썬을 사용했다. 1. page를 순회하면서 url과 link 뽑기, word 개수 세기 1) url과 links 뽑기url의 경우 https://careers.kakao.com/index" /> 형식이라고 했으므로, 다음과 같은 정규표현식을 사용한다. ()는 정규표현식에서 필요한 부분만 캡처하는 기능으로 .group(1)을 통해 해당 부분만 추출할 수 있다. 예를 들어, ...https://a.com ... 문자열에서 ()가 씌워진 a.com만 추출하는 것이다.  url = re.search('', page).group(1) link의 경우 " target="_blank" rel="noopener">htt.. 2022. 9. 20.
[프로그래머스 lv3] 모두 0으로 만들기 풀이 해설주어지는 그래프는 트리이다. 트리는 모두 연결되어있기 때문에 모든 정점의 합이 0이 되기만 한다면 규칙을 여러번 사용할지언정 모든 정점을 0으로 만들 수 있다.따라서, 모든 정점의 합(sum)을 구하고 합이 0이 아닐 경우 -1을 리턴한다. 모든 정점의 합이 0이라면 이제는 최소의 규칙을 적용하여 모든 정점을 0으로 만들 방법을 찾아야 한다. 1) func(int cur)은 현재의 지점(cur)을 루트 노드로 하는 트리에 대하여, 자식 노드들의 숫자를 모두 상쇄시키고 남은 것을 a[cur]에 옮기는 함수이다. 말단에 있는 트리들 부터 0으로 만든 뒤, 남은 숫자들을 처리하여 루트 노드로 올린다. 밑에서 처리할 수 있는 것들은 미리미리 0으로 만들어야 최소한의 규칙을 사용할 수 있다. 2) 위의 사항을.. 2022. 9. 20.
[프로그래머스 lv3] 블록 이동하기 풀이 해당 문제는 2020 KAKAO BLIND RECRUITMENT 출제 문제로 공식 해설이 있습니다.2020 신입 개발자 블라인드 채용 1차 코딩 테스트 문제 해설  해설(1, 1) 에서 (N, N)까지 도달하는 최단 경로를 구하는 문제로, bfs를 이용하여 해결할 수 있다. 1) bfs를 이용하여 최단 시간(거리)을 구할 때, 특정 좌표까지의 거리를 기록하는 dist 배열을 만들어야 한다. 그런데, 이 문제에서는 로봇이 두 칸에 걸쳐 이동하고 심지어 방향까지 가지고 있다. 따라서, 특정 좌표를 방문했는지 그리고 해당 좌표까지의 거리가 얼마인지 기록하는 배열은 3차원이 되어야 한다. dist[x][y][d]는 (x, y)에 d 방향으로 도달했을 때 (d = 0이면 오른쪽으로, d = 1이면 아래쪽으로) 해.. 2022. 9. 19.
[프로그래머스 lv3] 광고 삽입 풀이 해당 문제는 2021 KAKAO BLIND RECRUITMENT 출제 문제로 공식 해설이 있습니다.2021 카카오 신입공채 1차 온라인 코딩 테스트 for Tech developers 문제해설 해설1) 가장 많은 줄이 겹치는 지점이나 구간을 구할 때 떠올리면 좋은 스킬이 있다.바로, 모든 로그의 시작점과 끝점에 대하여 (시작, +1), (끝, -1)을 저장한 배열을 만들고 해당 배열을 정렬하여 특정 포인트에 몇개의 +1과 -1이 추가 되는지 검사하는 것이다. 시간 t 지점에 겹치는 재생 목록이 n개인데 새로 시작되는 재생목록이 plus개, 끝나는 재생목록이 minus개라면 t+1 지점에는 겹치는 재생목록이 n+plus-minus 개가 된다. log 배열을 이용하여 시간 t에 도달했을 때 추가되는 재생목록.. 2022. 9. 19.
[프로그래머스 lv3] 스타 수열 풀이 해설스타 수열을 만들기 위한 조건은 다음과 같다.> 스타 수열의 원소들을 2개씩 나누었을 때 각 집합이 포함하는 공통된 원소가 있을 것 따라서, a에 등장하는 각 원소를 공통 원소로 하는 최대 스타 수열을 찾고 이 중에서도 가장 긴 수열의 길이를 리턴하면 된다. 1) a에는 0부터 a.size() 미만의 원소가 포함되어있다. a를 순회하면서 각 원소들의 등장 횟수를 cnt 배열에 저장하자. 2) a에 등장한 각 수 i를 순회하면서 i를 공통 원소로 하는 최대 스타 수열의 길이를 구해보자. - 이때, cnt[i]가 0이라면 i를 공통 원소로 하는 스타 수열을 만들 수 없다.- cnt[i]가 현재까지의 최대 스타 수열 길이 ans보다 작거나 같다면, i를 공통 원소로 하는 최대 스타 수열을 만들어도 그 길이.. 2022. 9. 18.
[프로그래머스 lv3] N으로 표현 풀이 해설숫자 number을 N과 사칙연산으로 표현할 때 N 사용 횟수의 최솟값을 구하는 문제이다.최솟값이 8보다 크면 -1을 리턴하라고 했으므로, 우리는 1개부터 8개까지의 N을 사용했을 때 각각 만들 수 있는 수 목록을 찾으면 된다. 1) 1개의 N을 사용해서 만들 수 있는 수는 N 하나이다. 2) 2개의 N을 사용해서 만들 수 있는 수는- N을 두개 이어 붙인 NN- (1개의 N의 사용해서 만들 수 있는 수)와 (1개의 N의 사용해서 만들 수 있는 수)를 사칙연산한 결과이다. 3) 3개의 N을 사용해서 만들 수 있는 수는- N을 세개 이어 붙인 NNN- (1개의 N을 사용해서 만들 수 있는 수)와 (2개의 N을 사용해서 만들 수 있는 수)를 사칙연산한 결과- (2개의 N을 사용해서 만들 수 있는 수)와 .. 2022. 9. 18.
[프로그래머스 lv3] 거스름돈 풀이 해설dp[K]를 주어진 동전을 사용해 K를 만드는 모든 경우의 수 라고 정의하자.예를 들어, K = 5 이고 주어진 동전 money = [1, 2, 5] 라면, 가능한 경우는 dp{K] = 4이다. 1+1+1+1+11+1+1+2 1+2+25 주의할 점은 1+1+1+2와 1+2+1+1, 1+1+2+1 등은 모두 같은 것이므로 중복해서 세면 안된다는 것이다.따라서, dp[K]를 구할 때 중복이 발생하지 않도록 사용할 수 있는 동전과 금액을 차차 늘려가야 한다. 우선, 0을 만드는 방법은 아무것도 사용하지 않는 방법 1가지 이므로 dp[0] = 1로 설정한다.이후, 각 동전을 끝에 추가하여 만들 수 있는 수를 확인하자. money[i]를 끝에 추가할 때 만들 수 있는 수 j는 money[i] ~ n까지의 수이.. 2022. 9. 18.
[프로그래머스 lv3] 풍선 터트리기 풀이 해설a의 풍선들 중에서 주어진 규칙으로 풍선을 터뜨렸을 때 최종적으로 남을 수 있는 풍선의 수를 구하는 문제이다.a의 i번째 풍선이 최종적으로 남을 수 있는지 어떻게 확인할 수 있을까? 1) 문제에서 인접한 풍선들끼리만 비교하여 터뜨릴 수 있다고 했으므로, a[i]의 오른쪽에 있는 풍선들을 비교하여 터뜨린다면 a[i]의 오른쪽에는 가장 작은 풍선만 남는다. 마찬가지로, a[i]의 왼쪽에 있는 풍선들을 비교하여 터뜨리면 a[i]의 왼쪽에는 가장 작은 풍선만 남는다. 2) 풍선들을 터뜨릴 때 작은 풍선을 터뜨릴 수 있는 기회는 최대 한번뿐이다. 따라서, a[i]의 왼쪽에 있는 풍선들 중 가장 작은 풍선,  a[i]의 오른쪽에 있는 풍선 중 가장 작은 풍선 중에서 a[i]보다 작은 것의 개수가 2개 미만이라면.. 2022. 9. 17.

티스토리툴바