프로그래머스

[python] 프로그래머스 - 블록 게임(2019 KAKAO BLIND RECRUITMENT)

🤔문제 해결 Lv 4 | 시뮬레이션? 먼저 지울 수 없는 블록과 지울 수 있는 블록으로 나눴다. 동그라미 친 블록은 지울 수 있는 블록 board 의 맨위 왼쪽부터 차례로 탐색한다. 블록을 만나면 위에 동그라미 친 블럭인지 확인하고, 맞다면 지울 수 있는지 확인한다. 지울 수 있다면 지워주고, 지울 수 없다면( 지울 수 있는 블록이긴 한데 위에가 막혀서 아직 못지움) 임시 리스트에 저장. 다음 블록들을 지우는 것을 성공할 때마다 임시저장한 블록들도 지울 수 있는지 같이 체크해서 지워준다. 💨 문제는 크게 어렵지 않지만, 어떻게든 풀 수 있을 것이다. 시간이 오래걸리겠지만... 💻소스 코드 blocks = { 1: [[ (1, 0), (1, 1), (1, 2) ], [(0, 1), (0, 2)]] , 2:..

[python] 프로그래머스 - 야근 지수

🤔문제 해결 Lv3 가장 큰 값을 조금 씩 줄여나가야 하는 문제! - 우선순위 큐를 이용했다. 우선순위 큐는 리스트에서 pop()을 하게 되면 가장 작은 값이 나오게 된다. 여기서는 가장 큰 값을 꺼내야 하므로 각각의 값을 음수로 힙큐에 넣어 줬다. 가장 작은 값(사실은 가장 큰 값)을 꺼내서 1씩 더해준다. 그리고 다시 힙큐에 넣어준다. 테스트 케이스 1번을 풀이 해 보자. 4, [4, 3, 3] 위 그림의 첫째줄은 처음 힙큐에 넣었을 때이다. 다음 줄부터는 1시간씩 지날 때 마다의 힙큐의 상황이다. -4가 제일 작으므로 -4를 꺼내서 1을 더해주고 다시 넣는다. -3을 꺼내서 1을 더해주고 다시 넣는다. 또 -3을 꺼내서 1을 더해주고 다시 넣는다. 마지막으로 -3을 꺼내서 1을 더해주고 다시 넣는다..

[python] 프로그래머스 - 쿠키 구입

🤔문제 해결 Lv4 기준점을 하나 정한다. 0부터 쿠키의 길이-1 까지 그 기준은 첫째 아들 과자, 기준 + 1은 둘째 아들 과자로 시작한다. 1. 첫째의 과자가 적으므로 첫째에게 과자를 하나 더 준다. 2. 둘째의 과자가 더 적으므로 둘째에게 과자를 하나 더 준다. 3. 첫째의 과자가 적으므로 첫째에게 과자를 하나 더 준다. 4. 둘째의 과자가 더 적으므로 둘째에게 과자를 하나 더 준다. 5. 둘의 과자가 같으므로 값을 저장하고 첫째부터 과자를 더 줘본다. (둘째 먼저 줘도 된다.) 6. 둘째의 과자가 더 적으므로 둘째에게 과자를 하나 더 준다. 7. 첫째의 과자가 더 적어서 첫째에게 과자를 더 주고 싶지만 더 이상 줄 과자가 없다. 8. 다음 기준을 잡고 위의 과정을 반복한다. 💨 💻소스 코드 def..

[python] 프로그래머스 - 디스크 컨트롤러

🤔문제 해결 Lv3 | 우선순위 큐 파이썬에서는 heapq 를 사용합니다. 먼저 현재 시간을 항상 계산해 줍니다. 현재 시간보다 투입시간이 작은 작업들을 힙큐에 넣어줍니다. 힙큐에 값이 여러개 들어있더라도, heappop() 을 하게 되면 작업시간이 가장 짧은 작업이 나오게 됩니다. ( 힙큐에서는 최솟값이 나오게 됩니다 ) 작업시간만큼 현재시간 을 늘려주고, 해당 작업의 대기시간+작업시간 을 따로 저장해 둡니다. 한 작업이 끝나고 나면 시간이 흘렀기 때문에 다시 현재 시간보다 투입시간이 작은 작업들을 힙큐에 넣어줍니다.(아까 넣은 작업 제외) 똑같이 heappop() 으로 현재시간과 작업시간을 저장합니다. 💨 업무투입시간이 오름차순 정렬이 안되어있어서 먼저 정렬을 해줘야 합니다. 💻소스 코드 import..

[python] 프로그래머스 - 외벽 점검(2020 KAKAO BLIND RECRUITMENT)

🤔문제 해결 Lv 3 | 정답률: 0.6% 주어진 값의 크기가 크지 않기 때문에 완전탐색으로 해결이 가능하다. 먼저 친구를 순열로 만든다. ex) [1,2,3] 이면 [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] 외벽이 원형이므로 앞과 뒤가 이어져 있다고 생각해야 한다. 취약점도 첫번째 취약점을 먼저 갈것인가 두번째 취약점을 먼저 갈것인가... 순서를 정해서 가야한다. - 첫번 째 테스트케이스의 취약점([1, 5, 6, 10])을 배열(n=12)로 나타내면 [0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0] 위의 경우는 첫번째 취약점(1)이 가장 먼저 나오는 경우 - 다음 취약점 2가 가장 먼저 나오는 경우는 0,1을 맨뒤로 옮겨주면 된다. ..

[python] 프로그래머스 - 블록 이동하기(2020 KAKAO BLIND RECRUITMENT)

🤔문제 해결 1. Lv3 | BFS 심화 2. BFS를 돌릴 q와 방문체크할 visited리스트를 준비한다. (1) q는 deque를 이용. 로봇의 좌표 4가지 (x1,y1,x2,y2)와 현재의 거리 d 를 넣는다. (2) visited에는 로봇의 좌표만 넣는다. 3. BFS를 돌린다. (1) 먼저 끝점에 도달했다면 바로 멈춰주고 거리를 출력한다. (2) 그렇지 않다면 로봇이 세로인경우와 가로인경우를 나누고, 상하좌우 움직일 수 있는 지 체크한다. (3) 로봇이 세로인 경우 오른쪽 이동이 가능하면 오른쪽 회전도 가능하다. 마찬가지로 왼쪽이동이 가능하면 왼쪽으로 회전도 가능하다. (4) 가로도 마찬가지 (5) 이동이나 회전이 가능하면 visited리스트를 확인해 방문한적이 없으면 q와 visited에 넣어..