시뮬레이션
- 작은 의미로는 문제가 제시한 규칙에 따라 개체를 이동시키는 알고리즘을 말하며, 큰 의미로는 문제가 요구하는 대로 시행되도록 코드를 구현하는 알고리즘
4방향 탐색하는 법
방향 배열을 반들어 네 방향을 탐색하는 방법을 사용하기
문제 1.웅덩이
- 매개변수 nums에 n행 n열의 이차원 배열에 격자판 정보가 주어집니다.
- 각 격자에는 그 지역의 높이가 쓰여있습니다.
- 각 지역은 상하좌우 인접한 지역의 숫자가 모두 자신보다 클 경우 이 지역을 웅덩이 지역이라고 합니다.
- 격자의 가장자리는 1000으로 초기화 되었다고 가정한다.
만약 5*5 이차원 배열의 격자판 정보다 아래와 같다면 총 웅덩이의 수는 5개입니다.
int[] dx = {-1, 0, 1, 0};
int[] dy = {0, 1, 0, -1};
int answer = 0;
int n = nums.length;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
boolean flag = true;
for(int k = 0; k < 4; k++) {
int nx = i + dx[k];
int ny = j + dy[k];
if(nx >= 0 && nx < n && ny >= 0 && ny < n && nums[nx][ny] <= nums[i][j]) {
flag = false;
break;
}
}
if (flag == true) {
answer ++;
}
}
}
return answer; 문제를 처음 푸는 것이라서, 어떻게 풀어야할지 감도 안 잡혔는데 dx, dy를 활용하는 방식을 익히니 문제 푸는 것이 훨씬 수훨하게 느껴졌다.
처음에는 'nums[nx][ny] <= nums[i][j]' 이 부분을 왜 검사할까 했는데, 풀어보니 자신보다 작은 것 '한 개'만이라도 있으면 자신은 웅덩이가 아니기 때문에 검사한 것이라는 걸 이해했다. 문제를 좀 더 효율적으로 풀 수 있는 방식들을 연구해봐야겠다 :)
문제 2. 청소로봇(ver.1)
청소 로봇은 다음 규칙에 따라 이동합니다.
1. 'U' 명령은 로봇이 위쪽으로 한 칸 이동합니다.
2. 'R' 명령은 로봇이 오른쪽으로 한 칸 이동합니다.
3. 'L' 명령은 로봇이 왼쪽으로 한 칸 이동합니다.
4. 'D' 명령은 로봇이 아래쪽으로 한 칸 이동합니다.
매개변수 moves에 청소 로봇에 명령을 내린 문자들이 차례대로 나열된 명령 문자열이 주어지 면 이 명령 문자열을 청소 로봇이 모두 수행했을 때 최종 위치를 반환하는 프로그램을 작성하 세요. 격자판 밖으로 벗어나는 명령은 주어지지 않습니다.
이차원 배열 격자판 0행 0열이 청소 로봇의 시작 위치입니다.
int[] dx = {-1, 0, 1, 0};
int[] dy = {0, 1, 0, -1};
char[] dir = {'U','R','D','L'};
int x = 0;
int y = 0;
for(char c : moves.toCharArray()) {
for(int k = 0; k < 4; k++) {
if( c == dir[k]) {
x += dx[k];
y += dy[k];
}
}
return new int[] {x,y};처음에 문제를 풀 때는 char[] dir 배열을 사용하지 않고 그냥 else-if 문으로 케이스를 나눠서 작성했다. 배열로 작성한 후, 한꺼번에 이동하는 것이 더 효율적이고 이후에 코드 수정할 때도 좋을 것 같다고 생각했다.
그리고 문제를 보고 String을 어떻게 나눠야하나 고민이었는데 for-each 문으로 String을 배열로 바꿀 수 있는 방법이 있다는 걸 다시 알게 되었다. 잊지 않고 다른 문제에도 활용해보아야겠다.
문제 3. 청소로봇(ver.2)
청소 로봇은 다음 규칙에 따라 이동합니다.
1. 'U' 명령은 로봇이 위쪽으로 한 칸 이동합니다.
2. 'R' 명령은 로봇이 오른쪽으로 한 칸 이동합니다.
3. 'L' 명령은 로봇이 왼쪽으로 한 칸 이동합니다.
4. 'D' 명령은 로봇이 아래쪽으로 한 칸 이동합니다.
5. 만약 로봇이 명령을 수행할 경우 격자판 밖으로 나가는 경우라면 로봇은 해당 명령을 수행 하지 않고 무시합니다.
매개변수 n에 격자판 크기가 주어지고, moves에 청소 로봇에 명령을 내린 문자들이 차례대로 나열된 명령 문자열이 주어지면 청소 로봇이 최종적으로 멈춘 위치를 반환하는 프로그램을 작성하세요.
제한사항
- moves의 길이는 100을 넘지 않습니다.
- 3 <= n <= 50
n*n 크기의 이차원 배열 격자판 0행 0열이 청소로봇의 시작 위치입니다.
int[] dx = {-1, 0, 1, 0};
int[] dy = {0, 1, 0, -1};
char[] dir = {'U','R','D','L'};
int x = 0, y = 0;
int nx = 0, ny = 0;
for(char c : moves.toCharArray()) {
for(int k = 0; k < 4; k++) {
if( c == dir[k]) {
nx = x + dx[k];
ny = y + dy[k];
}
}
if( nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
x = nx;
y = ny;
}
return new int[] {x,y};위의 문제와 같은 문제처럼 보이지만, 2번 문제는 제한된 범위 내에서의 명령만 들어와서 작동하는 것이었다면? 3번 문제는 지정해준 범위를 벗어난 명령이 들어오면 실행하지 않도록 알고리즘을 짜야했다.
그래서 x와 y에 값을 대입해볼 수 있도록 nx와 ny를 따로 만들었다. nx와 ny의 값이 범위 내에 있는지 확인한 후, 범위 내에 존재한다면 x와 y의 값을 nx와 ny의 값으로 바꾸었다.
문제 4.로봇의 이동
로봇은 다음 규칙에 따라 이동합니다.
1. 'G' 명령을 주면 보고 있는 방향으로 한 칸 이동합니다. 격자 밖으로 나가는 명령은 하지 않습니다.
2. 'R' 명령을 주면 오른쪽으로 90도 회전합니다.
3. 'L' 명령을 주면 왼쪽으로 90도 회전합니다.
매개변수 moves에 로봇에 명령을 내린 문자들이 차례대로 나열된 명령 문자열이 주어지면 이 명령 문자열을 로봇이 모두 수행했을 때 최종 위치를 반환하는 프로그램을 작성하세요.
이차원 배열 격자판 0행 0열에 로봇이 3시 방향을 보고 있습니다.
int[] dx = {-1, 0, 1, 0};
int[] dy = {0, 1, 0, -1};
int x = 0, y = 0;
int d = 1;
for(char c : moves.toCharArray()) {
if(c == 'G') {
x = x + dx[d];
y = y + dy[d];
} else if (c == 'R') {
d = (d + 1) % 4;
} else if (c == 'L') {
d = (d + 3) % 4;
}
}
return new int[] {x,y};이번 문제에서는 로봇의 방향을 바꿔주는 작업이 필요했고, 'd'라는 인덱스로 dx와 dy의 값을 변경할 수 있도록 알고리즘을 짜는 방식을 학습했다.
로봇이 90도 회전할 때마다 d의 값에 1을 추가하여 로봇이 나아가는 방향을 변경해주었다. 근데 d값이 3을 넘어가면 dx, dy 배열에 없는 값이 나오므로 %4를 해주어 나머지값으로 d값이 설정될 수 있도록 하였다 :)
처음에 왼쪽으로 90도 회전하는 작업을 d = (d - 1) % 4로 작성했다가, 다른 케이스에서 0,0 에서부터 90도 회전을 하게 되면 음수가 나오게 됨을 깨닫고 왼쪽으로 90도 회전하는 방식이 아닌 오른쪽으로 270도 회전하는 방식을 택했다.
DAY 1을 배우고 느낀점
나는 정말 코테 공부를 너무나도 안 했고... 앞으로 죽기살기로 해야겠다는 생각을 하게됐다. 🥹 이렇게 무언가를 처음 배울 때마다 정말 막막하고 안 보이지만 1개를 배우면 2개는 응용할 수 있는 나라는 것을 알기 때문에..! 주어진 시간동안 잘 공부해서 코딩테스트 알고리즘을 잘 익힐 수 있으면 좋겠다!! 😣
