프로그래머스16 프로그래머스 - 아이템 줍기 문제 설명 여러 사각형의 겉면을 따라 목표지점으로 갈 수 있는 최단 거리를 구하는 문제이다. 주의 사항 단순 선을 격자의 칸으로 생각하고 최단거리를 탐색하게 되면 이슈가 있을 것이다. 왼쪽 그림 처럼 겉면이 표시된 경우를 보면 우리가 기대하는 탐색과는 다르게 탐색을 하게 된다. 왜냐하면 4방향을 탐색하면서 갈 수 있는지 판단할 것이기 때문이다. 2배율로 격자판을 확장하면 저런 경우를 방지할 수 있다! 기대하는 바와 다르게 탐색 하는 경우를 방지하기 위해 2배율을 한다면 이런식으로 좌표도 확장 되어 거리가 생기니 기대하는 탐색과 다르게 탐색 되지 않게된다! 또다른 시도로는 각 칸에 갈수 있는 방향을 넣어줬다.(정사각형의 입력을 주어질때) 하지만 해당 방법에서 위 그림의 경우 예외를 방지할 수 있지만 또다른.. Algorithm/프로그래머스 2023. 4. 16. 프로그래머스 - 미로탈출 명령어 문제 설명 출발점 , 도착점이 주어진다. 도착점 까지 k거리가 걸려 올 때, 올수 있는 경로는 여러가지이다. 그중 사전순으로 가장 앞선 경로를 나타내는 문제이다. 주의할점 출발지 , 목적지를 다시 방문해도 상관없음에 유의해야 한다. 그래서 아마 일반적인 BFS 큐가 커져 시간초과가 난다. BFS를 사용한다면 큐에 담긴 객체를 최적화 해야한다. TRY 큐안에 담긴 객체를 최적화 하기위해 3가지 시도를 했다. 현재 온 거리 +1 > k 크다면 삽입 x [시간초과] - 4개 맞음 현재 온거리 + 맨헤튼 거리 > k 일 경우 삽입 x [시간초과] - 6개 맞음 3차원 방문 [통과] 사전 순으로 먼저 인것을 골라내기 위해 d,l,r,u 으로 거리백터까지 생성해야함 풀이 public String solution(i.. Algorithm/프로그래머스 2023. 4. 15. 프로그래머스 - 표 편집 문제 설명 주어진 명령을 따라 이행한 뒤 그에 맞는 표 값을 출력하는 문제이다. 완벽한 구현문제이다. 자료구조를 어떻게 사용하지도 물어보는 문제인것같다. TRY 2차원 배열과 map 이 두가지를 이용했다. 2차원 배열에는 각 칸이 가지고 있는 문자값을 저장했고 map에는 해당 칸과 연관되어 있는 각 칸들의 정보를 저장했다. 왜냐하면 병합 또는 병합제거, 정보 수정에 이전에 수행했던 연관되어 있는 칸들이 필요했기 때문이다. 병합시 - 이전에 수행된 연관정보들로 부터 추가로 병합을 이어나가야 하기 때문. 병합제거 - 이전에 수행된 연관정보들 모두 초기화 해야하기 때문. 정보수정 - r,c와 병합을 한 셀들을 기반으로 모든 값을 교체해야하기 때문. 주의사항 다른 연관관계를 이어붙이기 위한 과정에서 변경에 대한.. Algorithm/프로그래머스 2023. 4. 12. 프로그래머스 - 표현 가능한 이진트리 필요지식 이진트리 트리순회 문제 설명 해당 수를 이진트리로 표현할 수 있으면 1 없으면 0을 출력하는 문제이다. 주어진 문제 예시를 보면 주어진 이진트리에 더미노드를 추가하여 포화 이진트리를 형성한다. 즉, 이 것을 이용해 이진트리로 만들 수 있는지 없는지를 판별하면 된다. 문제에는 포화이진트리를 만들수 있는지 없는지 이렇게 물어보지 않고 있다. numbers 에 주어진 순서대로 하나의 이진트리로 해당 수를 표현할 수 있다면 1을, 표현할 수 없다면 0 이진트리에 속해있는 것이 포화이진트리이다. - 이진트리는 자식노드가 최대 2개인 트리이다. - 포화이진트리는 이진트리이면서 모든 레벨이 노드로 꽉 차 있어야 한다. 그렇기 때문에 이 문제는 해당 수를 이진수로 표현하고 포화이진트리로 형태로 만들면서 이것이.. Algorithm/프로그래머스 2023. 4. 11. 프로그래머스 - 택배배달과수거 문제 설명 최소한의 이동거리로 배달과 수거를 모두 마치는 거리를 구하는 문제이다. 최대길이가 10만이다. 단순히 구현하는 문제인데, 구현을 해나가는 과정이 쉽지않다. 그래서 나는 이렇게 시도해봤다. 배달 또는 수거할 제일 먼곳을 찾는데, 먼곳을 가는 과정에서 배달할 물건을 내려놓는다고 생각했다. 그리고 끝지점에서 다시 물건을 실으러 오면서 회수할 물건을 최대 담아내는 탐욕법을 이용했다. 풀이 public long solution(int cap, int n, int[] deliveries, int[] pickups) { TreeMap d = new TreeMap(); for (int i = 0; i < n; i++) { if( deliveries[i] ==0 ) continue; d.put(i + 1, d.. Algorithm/프로그래머스 2023. 4. 9. 이전 1 2 3 4 다음
