오늘의 학습 키워드
</> 시뮬레이션
공부한 내용 본인의 언어로 정리하기
import java.util.*;
class Solution {
public int[] solution(String[] park, String[] routes) {
int H = park.length;
int W = park[0].length();
int startX = 0;
int startY = 0;
//시작 위치 찾기
for(int i = 0; i < H; i++){
for(int j = 0; j < W; j++){
if(park[i].charAt(j) == 'S'){
startX = j;
startY = i;
}
}
}
//현재 위치 설정
int currentX = startX;
int currentY = startY;
//routes의 방향과 거리를 분리
for(String route : routes){
String[] splitRoute = route.split(" ");
String direction = splitRoute[0];
//나중에 이동거리 계산을 위해서 String이 아닌 Int로 변환 수정하였음 "String distance = splitRoute[1];"
int distance = Integer.parseInt(splitRoute[1]);
//이동할 좌표
int movedX = currentX;
int movedY = currentY;
//이동거리 계산, 처음에 볼때 (0,0)에서 햇갈려서 X,Y의 +=도 햇갈렸었음..
for(int i = 0; i < distance; i++){
if (direction.equals("N")) {
movedY -= 1;
} else if (direction.equals("S")) {
movedY += 1;
} else if (direction.equals("W")) {
movedX -= 1;
} else if (direction.equals("E")) {
movedX += 1;
}
//범위 초과시 중단 || 장애물 만나면 중단
if(movedY < 0 || movedY >= H || movedX < 0 || movedX >= W || park[movedY].charAt(movedX) == 'X'){
movedX = currentX; // 원래 위치로 돌아가기
movedY = currentY; // 원래 위치로 돌아가기
break;
}
}
// 이동이 하고 위치 업데이트
currentX = movedX;
currentY = movedY;
}
return new int[]{currentY,currentX};
}
}
오늘의 회고
최근 문제 유형이 시뮬레이션이 되면서 갑자기 문제가 복잡해져서 이해하는데도 시간이 굉장히 오래걸리기도 하고 매번 짧게 한 메소드에서 끝나는 문제들로만 풀다가 여러개를 작성해야하니 생각도 재대로 안되고 의도나 어떻게 처리를 해야할지도 감이 안잡혀서 순수하게 내 실력으로 푸는게 아닌것 같다는 생각이 든다.
일단 오늘 문제는 로봇강아지가 공원 산책을 하려하는데 미리 입력된 명령에 따라 진행하게 되어있어 그 길을 따라 가며 최종 도착지의 위치를 배열로 반환을 해주는 것이다.
기본적으로 park에는 공원에서의 시작위치 그리고 장애물이 포함된 정보가 있고, routes에는 움직여야 할 명령들이 있다.
여기서 고려해야 할것은 공원을 빠져나가는 것과 장애물에 부딪히게 될 가능성들을 배제해주어야 하고 공원의 크기를 제한을 해주어야한다.
그래서 시작에는 공원의 최대크기와 시작위치를 조정해 주었다.
int H = park.length;
int W = park[0].length;
int startX = 0;
int startY = 0;이후 이동을 시작하기 전에 시작 위치를 먼저 찾아 준 다음 그 위치에서 움직어 주어야하며 공원 전체를 순회해서 시작위치인 S를 찾는다면 그 위치 값을 startX와 startY로 넣어주어야 한다. 이 반복문에서 i는 행 j는 열을 나타내므로 각각 올바른 위치에 넣어준다.
for(int i = 0; i < H; i++){
for(int j = 0; j < Y; j++){
if(park[i].charAt(j) == 'S'){
startX = j;
startY = i;
}
}
}이제 입력한 값을 현재위치로 설정해준다.
int currentX = startX;
int currentY = startY;이제 기본 위치는 끝났으므로 로봇강아지가 이동해야할 위치와 거리를 계산할 수 있게 구분해서 저장해준다.
routes의 예시를 보면 방향과 거리가 공백을 기준으로 나눠서 작성되어 있기 때문에 공백을 기준으로 나누어서 저장해준다.
for(String route : routes){
String[] splitRoute = route.split(" ");
String direction = splitRoute[0];
int distance = Integer.parseInt(splitRoute[1]);처음에는 distance로 String으로 저장해주었지만 나중에 이동거리 계산을 해야할때 정수값이 필요하므로 Integer로 변환을 해주었다.
분리가 끝났다면 이제 이동할 좌표를 시작하는 위치로 만들고 이동한 방향과 거리를 계산하여 반환해 주어야한다. 시작하는 위치의 값 또한 정수이므로 이동하는 값을 더해주며 계산해주도록 한다.
int movedX = currentX;
int movedY = currentY;
for(int i = 0; i < distance; i++){
if(direction.equals("N"){
movedY -= 1;
} else if (direction.equals("S")) {
movedY += 1;
} else if (direction.equals("W")) {
movedX -= 1;
} else if (direction.equals("E")) {
movedX += 1;
}
}더 가독성이 좋은 switch-case를 사용할 수도 있다.
for (int i = 0; i < distance; i++) {
switch (direction) {
case "N":
movedY -= 1;
break;
case "S":
movedY += 1;
break;
case "W":
movedX -= 1;
break;
case "E":
movedX += 1;
break;
}이동값을 다 계산해 주었다면 이제 처음 말한 제한사항에 대한 설정을 하고 그 범위를 초과할 경우 원래 위치로 다시 되돌아와서 이동을 더 이상 하지 못하게 중단시켜줄 필요가 있다.
if(movedY < 0 || movedY >= H || movedX < 0 || movedX >= W || park[movedY].charAt(movedX) == 'X')
movedX = currentX; // 원래 위치로 돌아가기
movedY = currentY; // 원래 위치로 돌아가기
break;
}
}if문의 제한 사항을 보면 최소, 최대값에 대한 제한과 장애물로 지정해놓은 X에 대한 값을 만났을 경우 원래 위치값으로 되돌리고 중단을 하도록 해놓았다.
이제 이동한 위치를 다시 현재위치로 업데이트 시켜준다.
currentX = movedX
currentY = movedY그렇게 이 과정까지 끝이 났다면 위치의 값을 반환해서 정답을 표시해주면 되겠다.
return new int[]{currentY, currentX};여기서도 currentX를 먼저 배열해주지 않은 이유는 반환하는 값을 (행,열)로 해주어야 하기 때문에 행 값인 currentY를 앞 순서로 반환해주게 되었다.
AI 코드리뷰
현재 코드의 장점
- 코드가 명확하고 읽기 쉽습니다.
- 문제의 요구사항을 잘 구현했습니다.
- 시작 위치를 찾는 방법과 이동 로직이 잘 분리되어 있습니다.
현재 코드의 단점
- 불필요한 반복문이 있어 효율성이 떨어집니다.
- 코드 중복이 있습니다 (예: 원래 위치로 돌아가는 로직).
- 일부 변수명이 명확하지 않습니다 (예: H, W).
시간 복잡도
- 시작 위치 찾기: O(H * W)
- 각 명령어 처리: O(N * M), 여기서 N은 routes의 길이, M은 각 이동의 최대 거리
- 전체 시간 복잡도: O(H W + N M)
개선 제안
개선된 코드 제안
import java.util.*;
class Solution {
private static final int[] DX = {0, 0, -1, 1}; // N, S, W, E
private static final int[] DY = {-1, 1, 0, 0};
private static final String DIRECTIONS = "NSWE";
public int[] solution(String[] park, String[] routes) {
int height = park.length;
int width = park[0].length();
int[] current = findStart(park);
for (String route : routes) {
char direction = route.charAt(0);
int distance = route.charAt(2) - '0';
int dirIndex = DIRECTIONS.indexOf(direction);
int newX = current[1] + DX[dirIndex] * distance;
int newY = current[0] + DY[dirIndex] * distance;
if (isValidMove(park, current[1], current[0], newX, newY, dirIndex)) {
current[1] = newX;
current[0] = newY;
}
}
return current;
}
private int[] findStart(String[] park) {
for (int i = 0; i < park.length; i++) {
int j = park[i].indexOf('S');
if (j != -1) return new int[]{i, j};
}
throw new IllegalArgumentException("No starting point found");
}
private boolean isValidMove(String[] park, int x, int y, int newX, int newY, int dirIndex) {
if (newX < 0 || newY < 0 || newY >= park.length || newX >= park[0].length()) {
return false;
}
int stepX = Integer.compare(newX, x);
int stepY = Integer.compare(newY, y);
while (x != newX || y != newY) {
x += stepX;
y += stepY;
if (park[y].charAt(x) == 'X') return false;
}
return true;
}
}개선된 버전의 장점
- 코드가 더 간결하고 효율적입니다.
- 방향에 대한 상수와 배열을 사용하여 코드 중복을 줄였습니다.
- 이동 유효성 검사를 별도의 메소드로 분리하여 가독성이 향상되었습니다.
- 불필요한 반복문을 제거하여 성능이 개선되었습니다.
개선된 버전의 단점
- 상수와 배열을 사용하여 약간 더 복잡해 보일 수 있습니다.
- 예외 처리를 추가하여 코드가 조금 더 길어졌습니다.
시간 복잡도
- 시작 위치 찾기: O(H * W)
- 각 명령어 처리: O(N * M), 여기서 N은 routes의 길이, M은 각 이동의 최대 거리
- 전체 시간 복잡도: O(H W + N M)
내일 공부할 것 :
시뮬레이션에 대해서도 공부할 필요가 있어보이며, 여러가지 과정이 추가 된다고 겁먹지 말고 차근차근 그림이라도 그려가면서 최대한 여러 방면으로 생각하며 두뇌를 유연하게 만들 필요성이 진짜 매우 크게 느껴진다. 될때 까지 부딪혀보며 알아보고 정리하면서 공부해야 할 것이다.
문제
https://school.programmers.co.kr/learn/courses/30/lessons/172928
