문제는 프로그래머스에 가서 읽어보자.
https://school.programmers.co.kr/learn/courses/30/lessons/161990
정답여부: 정답
시간: 8분
Feedback
나도 모르게 if문을 발라버렸다. 자존심에 스크래치 났다. 이대로라면, 오늘 꿀잠을 잘 수 없기 때문에 조금 더 생각해보기로 했다.
헷갈리는 이유
- 드래그 하는 기준은 좌표인데, 파일은 공간에 위치한다.
- 하지만, 이건 말장난일 뿐 사실 문제를 제대로 읽어보면 딱히 중요한 정보는 아니였다.
- 문제에서 가끔 이렇게, 물체를 주고 격자점으로 풀라고 하는 경우가 많은데, 우리가 필요한 정보가 무엇인지 정확히 파악할 필요가 있다.
- 우리가 필요한 정보는 격자점 -> 격자점 까지의 거리이다. 즉, 우리는 격자점의 정보가 필요하다. 파일이 발견되면, 해당 파일을 드래그하기 위해, 드래그포인트를 갱신시키면 된다.
파일을 일단 놓아보자.
파일이 위치하게 되면, 왼쪽 위 모서리와 오른쪽 밑 모서리가 드래그 가능한 공간이 된다.
- 즉, 우리는 파일을 발견하면, 해당 2개의 좌표를 비교하면 된다는 이야기가 된다.
시작점, 끝점 조건 찾기
하지만, 좌표를 어떻게 비교할지는 직접 파일을 놔보면서 몇 개의 케이스를 생각해보자.
- 두 좌표의 거리가 최소 거리가 되게끔 하려면 어떻게 드래그를 하면 될까?
- 우선, 파일을 모두 드래그 해야하므로, 시작점의 후보를 뽑아보자.
- 파란 체크가 되어있는 부분은 다 가능하지만, 우리는 두 파일을 드래그하는
최소거리를 구하는 것이다. 즉, 지금 주황 형광색 시작지점이 최소거리가 될 수 있는 지점인걸 알 수 있다.
- 또, 파일을 모두 드래그 해야하므로, 시작 지점은 가장 좌표가 작은(0에 가까운) 파일의 x,y 값보다 작거나 같아야한다는 걸 알 수 있다.
- 여기서, 최소거리가 되기 위해서는? → **가장 좌표가 작은(0에 가까운) 파일의 x,y 값이면 된다.
끝점은 어떻게 생각할 수 있을까 ?
- 끝점은 더 쉽다. 파일을 모두 드래그 해야하므로 초록색의 1,2번 후보지가 있을 수 있다.
- 이것도 가장 오른쪽 하단(n,n에 가까운) 파일의 x,y값보다 크거나 같아야한다는걸 알 수 있다.
- 하지만, 최소거리이므로, x,y좌표의 최댓값이다.
2개까지만 놓는것도 괜찮지만, 혹시라도 모를 예외나 반례가 발생할 수 있다. 3개까지 놓아보자.
예상대로, 새로운 파일의 시작점과 끝점을 드래그 해야하는 Point와 비교해서 시작점은 최솟값으로 갱신,끝점은 최댓값으로 갱신하는걸 알 수 있다.
개선 전 코드
class Solution {
public int[] solution(String[] wallpaper) {
int[] answer = new int[4];
boolean firstTime = true;
for(int x=0;x<wallpaper.length;x++){
for(int y=0;y<wallpaper[x].length();y++){
//없는 경우 무시
if(wallpaper[x].charAt(y)=='.')
continue;
//파일발견
int sx = x;
int sy = y;
int ex = x+1;
int ey = y+1;
if(firstTime){
answer[0] = sx;
answer[1] = sy;
answer[2] = ex;
answer[3] = ey;
firstTime = false;
}
if(sx<answer[0]){
answer[0] = sx;
}
if(sy<answer[1]){
answer[1] = sy;
}
if(answer[2]<ex){
answer[2] = ex;
}
if(answer[3]<ey){
answer[3] = ey;
}
}
}
return answer;
}
}개선 후 코드
class Solution {
public int[] solution(String[] wallpaper) {
int minX = Integer.MAX_VALUE;
int minY = Integer.MAX_VALUE;
int maxX = Integer.MIN_VALUE;
int maxY = Integer.MIN_VALUE;
for(int x=0;x<wallpaper.length;x++){
for(int y=0;y<wallpaper[x].length();y++){
//없는 경우 무시
if(wallpaper[x].charAt(y)=='.')
continue;
//파일발견
minX = Math.min(minX,x);
minY = Math.min(minY,y);
maxX = Math.max(maxX,x);
maxY = Math.max(maxY,y);
}
}
int[] answer = {minX,minY,maxX+1,maxY+1};
return answer;
}
}