프로그래머스

[python3] 프로그래머스 외벽 점검 ( 2020 KAKAO BLIND RECRUITMENT, level3, 완전탐색, 순열 )

일단 문제 설명에 앞서 너무 어려웠다. 어려워서 짜증이 치밀어 오르다가 여러 사람의 풀이를 참고해보고 스스로 풀기를 반복하여 겨우겨우 풀었다. 문제를 읽어보면 크게 별게 없다. 취약한 지점이 존재하고 최대한 적은 친구들을 사용하여 취약한 지점을 점검하고 오는 것이다. 이때 사용된 친구들 수의 최솟값을 구하면 된다. 그런데 문제는 어디에서 시작해야할지, 어떤 친구를 투입할지 여러가지 고민이 필요하다. 처음에는 그리디 냄새가 났다. 어떤 취약한 지점을 고르고 가장 이득이 큰 부분을 선택하는 방식으로 진행하려고 했지만 기준을 만드는게 어려웠고 어떻게 구현을 해야하나 고민되었다. 그런데 n은 200이하이고, weak배열은 15이하, dist배열도 8이하였다. 그렇다면 완전 탐색으로 모든 경우를 해볼수도 있겠다는..

[python3] 프로그래머스 추석트래픽 풀이 ( 그리디 )

이 문제는 접근은 바로 했는데 한 날짜를 계산하는 포인트에서 막혀서 상당히 버벅거리다 다른 풀이를 보고 빠르게 해소되었다. 그래서 다시는 잊지 않고자 이렇게 풀이를 쓴다. 문제를 요약하면 다음과 같다. 로그에 처리시간과 걸린시간이 주어진다. 그렇다면 1초간 얼마나 많은 트래픽을 처리할 수 있는지 확인하고자 한다. 로그는 날짜순으로 오름차순으로 제공된다. 위와 같은 그림을 보면 각 초마다 매번 확인을 하며 로그를 확인해야하는가 싶다. 그렇게 된다면 24시간을 초당 루프를 돌아야하고 더구나 각 로그가 속하는지도 확인을 해야한다. 다행인건 주어지는 로그가 오름차순으로 정렬되어 있다는 점이다. 이를 통해 문제 해결의 실마리를 찾을 수 있다. (각 구간에 속하기만 하면 된다. ) 따라서 로그1이 존재할때 로그 1..

[python3] 프로그래머스 징검다리 풀이 ( 이분탐색 )

왜 이분 탐색문제인지 이해를 할수가 없어서 상당히 헤맸다. 결국 풀이를 봤다. 우선 문제를 읽어보면, 징검다리를 만들 때 n만큼 돌을 제거하고 최솟값을 찾는다. 이때 최솟값을 최대로 만드는 경우를 구하면 된다. 제한사항을 보면 distance가 1~1,000,000,000이다. 아무래도 선형탐색은 못할 만큼 값이 크다. 따라서 여기서 이분탐색의 냄새를 살짝 맡아본다. 처음에 나는 각 돌마다 거리를 구하고 작은 값부터 제거하면 되지 않나?하고 생각했다. 그러나 문제는 돌이 제거되면 각 돌의 거리를 다시 최신화 해주어야 한다. 그럼 돌을 제거 할 때마다 sort를 하게 되고 n만큼 sort를 해야되는 상황이 발생한다. 그럼 생각을 바꿔보자 만약 최솟값을 기준으로 현재 바위가 만족하는지 확인한다고 가정한다. ..

[python3] 프로그래머스 입국심사 풀이 ( 이분 탐색 )

이거 어려웠다. 처음에 점화식을 세워야하나 많이 당황했다. 솔직히 이분탐색 문제가 아니었다고 한다면 제한된 시간내에 풀지 못했을거 같다. 일단 문제를 보자 문제를 읽어보면 입국심사가 필요한 인원과, 입국심사에 걸리는 시간이 존재한다. 이때 입국심사를 모두 마치기 위한 최소시간을 구하면 된다. 처음에는 이분탐색을 어디에 적용해야할지 몰라서 당황했다. 이후에 문제를 차분히 살펴보니 return값을 살펴보는게 어떨까라는 생각이 들었다. 정리된 생각은 아래와 같다. 1. 입국심사에 적은 시간이 걸리는 심사관이 많은 입국자를 받아야 총 시간이 줄어든다. 2. 최소시간을 times로 나누었을때 값을 더하면 n이 된다. 처음에는 1번에 꽂혀서 무조건 작은 시간을 많이 주고 하나씩 줄여가며 연산을 하면 되겠지라는 생각..