[프로그래머스] 위클리 11주차 - 아이템 줍기 JAVA

[프로그래머스] 위클리 11주차 - 아이템 줍기 JAVA

역시 오랜만의 포스팅은 알고리즘이지용 ㅎㅎㅎ

JAVA 로 코테 푸는거 진짜 너무 어려워요.... JAVA 으아...

문제링크 :

https://programmers.co.kr/learn/courses/30/lessons/87694

[문제]

사각형이 최대 4개가 주어지고 사각형끼리 겹쳐서 주어지는데 그 최외곽을 따르면서 시작지점부터 목표지점까지 몇칸 이동했는지 구하면 된다.

[풀이]

풀이방법은 매우 심플하다.

사각형을 외곽선은 전부 1로 표시하고, 내부는 전부 -1로 표시해서 map을 만든다.

단, 기존에 이미 -1로 표시됐었다면 해당 사각형은 기존에 이미 그려놓은 사각형에 포함 관계라는 것이므로 1로 표시하지 않는다.

이렇게 map을 다 만들었다면 시작점부터 목표지점까지 1인 곳만 따라서 bfs를 돌면된다.

단, 함정이 있다.

문제에서 준 1번 예제처럼 사각형 3개가 한칸차이로 'ㄷ' 자를 만들면서 겹쳐져 있는 경우, 오른쪽 갔다가 위쪽갔다가 왼쪽가야 하는데 어떻게 구현했냐에 따라 다르지만 보통 위쪽으로 뚫고 가버리던가 위쪽을 무시하고 왼쪽으로만 가던가 할것이다.

-> 해결방법은 간단하다. 주어지는 모든 좌표를 X2 해서 풀어주면 된다. 그러면 한칸 차이로 나란히 선이 놓이지 않기 때문에 진행 방향에 혼동이 오지 않는다. 물론 결과 반환할때는 /2 해서 반환해야한다.

[시간 복잡도]

위 풀이 방법은 주어지는 사각형이 4개 까지고, 좌표는 모두 50미만이라는 입력 제한 조건을 가지고 있기 때문에 가능한 풀이 방법입니다. 더 시간복잡도를 줄이라고 하면 어떻게 해야 될지 모르겠는데... 짐작가시는 분은 제발 힌트좀 주세요ㅠㅠ

곱하기 2 를 하기때문에 50X2 = 100

100X100 = 10000

=> 사각형 하나 map 에 그리는데 드는 시간 = 10000

=> 사각형 4개니까 40000

BFS 도는 건 최외곽이니까 100*4*4(방향) = 1600

최대 1600곳을 방문한다.

총 11600 곳을 방문한다.

시간복잡도로 표현하면 아래와 같다.

O(N*N)

빅오의 엔제곱이라... 줄인다면 NlogN으로 줄일 수 있겠죠? ....짐작도 안가네요ㅋㅋㅋㅋ

[소스 코드]

import java.util.*; class Solution { public class Pair { int x,y; public Pair(int x, int y){ this.x = x; this.y = y; } } int[][] visited = new int[101][101]; int[] dx = {-1,0,1,0}; int[] dy = {0,1,0,-1}; int[][] map = new int[101][101]; int go(int cx, int cy, int ix, int iy) { Queue q = new LinkedList<>(); Pair p1 = new Pair(cx, cy); q.add(p1); visited[cx][cy] =1; int cnt = 0; while(!q.isEmpty()){ Pair cur = q.peek(); q.poll(); if( cur.x == ix && cur.y == iy) { return visited[ix][iy]/2; } for (int i=0; i<4; i++){ int nx = cur.x+dx[i]; int ny = cur.y+dy[i]; if( nx >100 || ny>100 || nx <0 || ny <0) continue; if (map[nx][ny] == 1 && visited[nx][ny] == 0) { p1 = new Pair(nx,ny); q.add(p1); visited[nx][ny] = visited[cur.x][cur.y]+1; } } } return cnt; //걍.. 리턴 할게 없어서... cnt 넣어놨습니다. 의미없습니다... ㅎㅎㅎㅎㅎ } void paintRectangle (int x1, int y1, int x2, int y2) { for (int i=x1; i<=x2; i++ ){ if(map[i][y1] != -1) map[i][y1] = 1; if(map[i][y2] != -1) map[i][y2] = 1; } for (int i=y1; i<=y2; i++) { if(map[x1][i] != -1) map[x1][i] = 1; if(map[x2][i] != -1) map[x2][i] = 1; } for (int i=x1+1; i<=x2-1; i++ ){ for (int j=y1+1; j<=y2-1; j++) { map[i][j] = -1; } } } public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) { characterX *= 2; characterY *= 2; itemX*=2; itemY*=2; for (int i=0; i

from http://cykei.tistory.com/98 by ccl(A) rewrite - 2021-10-20 22:01:16