프로그래머스[Python] - 게임 맵 최단거리, 조이스틱, 메뉴 리뉴얼, 프린터

게임 맵 최단거리

문제 url : https://programmers.co.kr/learn/courses/30/lessons/1844

코딩테스트 연습 - 게임 맵 최단거리

문제 내용 : 나는 n*m 짜리 map에서 (1,1)위치에 있으며, (n,m)가 목표(상대진영)이다. 여기까지 가는 다양한 경우의 수에서 가장 빠르게 도착하는 수를 구하여라. 만약 도착하지 못하면 -1을 출력한다. 이때, 1은 갈 수 있는 지역이고 0은 갈 수 없는 지역이다. 동,서,남,북 4가지로 갈 수 있다.

알고리즘 : BFS, DP

주의할 내용 : 아래 if 문을 보면 4가지 조건에 대해서 처리할때, Python 같은 경우는 index 범위에 벗어나는 조건을 앞에다가 쓰면 에러가 난다. 그래서 반드시 예외처리도 순서대로 왼쪽부터 오른쪽으로 처리해아한다는 것을 알게 되었다.

알게된 점 : BFS를 사용할때, 종종 까먹는데, 이 문제는 많은 기출에도 응용되어 나올 만큼 자주 나오는 문제 같다. 특히 대각선까지 따지는 경우도 있기 때문에 방향을 총 9개로 응용해서 알아둘 필요가 있는데 아래 방법과 크게 벗어나지는 않을 것 같다. 또한 매번 BFS에서 Visited라는 리스트를 활용해서 방문했는 지 True, False로 판단했는데, 이는 DP와 응용해서 나올 수도 있기 때문에 반복해서 코드를 보고 학습하자.

조이스틱

문제 url : https://programmers.co.kr/learn/courses/30/lessons/42860

코딩테스트 연습 - 조이스틱

문제 내용 : 조이스틱을 방향으로 움직여서 문자를 만들어보자. 처음은 'A' 로만 이루어져 있다. 이때 문자를 만들때까지 최소한의 횟수로 만들어야할 때, 몇번 눌러야 할까?

▲ - 다음 알파벳
▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
▶ - 커서를 오른쪽으로 이동

알고리즘 : Greedy(탐욕 알고리즘), 분할 정복

메뉴 리뉴얼[2021 KAKAO BLIND RECRUITMENT]

문제 url : https://programmers.co.kr/learn/courses/30/lessons/72411

코딩테스트 연습 - 메뉴 리뉴얼

문제 내용 : 단품 메뉴들을 가지고 코스 메뉴를 만들려고 한다.

알고리즘 : 단순 구현, Combinations, Counter

알게된 점 : 처음에 모든 코스 별로 구하는 바람에 Combination을 코스 구성 개수당, 사람들의 조합을 구한 것이아닌, 메뉴들의 조합을 구해서 사람들별로 맞추려고 했다.

뭐, 여기까지는 사실 상관은 없는데, Counter모듈이 생각이 나지 않았고 2명 이상이면 다 OK인줄 알았다. 하지만 함정이 있었다. 가장 많이 함께 주문한 단품메뉴들 이게 함정이었다. MAX가 아니라 다 구하는 바람에 에러가 있었고, 참고하여 수정했다.

또한 Counter모듈을 사용하면 List에 있는 원소들을 한번에 묶는 동시에 갯수도 셀 수 있다는 것을 다시 상기하게 되었다.

프린터

문제 url : https://programmers.co.kr/learn/courses/30/lessons/42587

코딩테스트 연습 - 프린터

문제 내용 : 프린터기에서 프린트를 하려고 하는데, 맨 앞에 있는 인쇄지보다 높은 중요도를 가진 것들이 대기하고 있다면 맨 뒤로 보낸다. 그래서 location에 있는 인쇄지가 언제 출력이 될까?

알고리즘 : 단순 구현, Queue