728x90
오늘은 알고리즘 테스트 시험을 봤다.
난이도 상, 중, 하 이렇게 세문제가 나왔으나 중, 하는 쉬웠다.
하지만 난이도가 상인 문제는 어려웠다.
상하좌우의 값을 비교해 가장 큰 값이라면 별을 출력하게 해야 하는 문제였다
처음에는 배열초과가 일어나지 않게 하기 위해 총 세부분으로 나누어 작업했다
1. 두 부분의 값만 비교하면 되는 꼭짓점
2. 세 부분의 값만 비교하면 되는 모서리
3. 상하좌우 모두 비교하여야 하는 안쪽 부분
public class Test_3 {
public void Solution(int[][] checkin){
String [][] answer = new String[checkin.length][checkin[0].length];
// 1 꼭짓점 부분 구현
// 1-1. [0, 0]
answer[0][0] = (checkin[0][0] > Math.max(checkin[0][1], checkin[1][0])
? "*" : String.valueOf(checkin[0][0]));
// 1-2 [0, max]....
// 2. 세가지 값만 비교하면 되는 모서리 부분 구현
for(int i = 1; i < checkin.length-1; i++) {
//첫번째 열
answer[0][i] = (checkin[0][i]
> Math.max(checkin[1][i]
, Math.max(checkin[0][i - 1], checkin[0][i + 1])))
? "*" : String.valueOf(checkin[0][i]);
//마지막 열 ....
// 3. 상하좌우를 모두 비교해야 하는 두번째 ~ 마지막 앞까지의 행과 열
for(int i = 1; i < checkin.length-1; i++){
for(int j = 1; j < checkin[i].length-1; j++){
answer[i][j] = (checkin[i][j] >
Math.max(
Math.max(checkin[i][j-1], checkin[i][j+1]),
Math.max(checkin[i-1][j], checkin[i+1][j])))
? "*" : String.valueOf(checkin[i][j]);
}
}
이렇게 푸는 문제가 아니란걸 문제를 풀면서도 확신했다.
어쨌든 올바르게 동작하기에 제출을 하고 난 후 어떻게 푸는 게 효율적인지 찾아보니
방향벡터(Directional Vector) 방식을 이용하여 푸는 문제라고 한다.
방향벡터는 특정 방향을 나타내기 위해 사용되며 (x, y) 형태로 표현한다.
예를 들어 (1, 0)은 x축으로만 1만큼, (0, -1)은 y축으로만 -1만큼 이동함을 나타낸다.
코드로 작성해봤다.
//상 우 하 좌
int[][] direction = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
// *을 넣기위해 max값 확인을 위한 boolean
boolean isMaxValue = true;
for (int i = 0; i < 4; i++) {
int dx = x + direction[i][0], dy = y + direction[i][1];
// 상, 하, 좌, 우 배열을 초과하는 위치가 있는 경우 continue;
if (dx < 0 || dx >= 5 || dy < 0 || dy >= 5) {
continue;
}
// 상, 하, 좌, 우 크거나 같은 값이 있는 경우 isMaxValue를 false로 반환
if (checkin[x][y] <= checkin[dx][dy]) {
isMaxValue = false;
break;
}
}
answer[x][y] = (isMaxValue)? "*" : String.valueOf(checkin[x][y]);
오늘 테스트로 방향벡터를 직접 구현해 봄으로써 어떤 원리로 동작하는지, 어떤 상황에 사용해야 할지 알 수 있었다.
'Algorithm' 카테고리의 다른 글
Algorithm - 프로그래머스 섬 연결하기(Greedy, Minimum Spanning Tree, Union Find) (0) | 2024.04.01 |
---|---|
Algorithm - 백준 DNA 비밀번호(12891), 슬리이딩 윈도우 (0) | 2024.03.26 |
프로그래머스: 포켓몬 (0) | 2023.06.21 |
프로그래머스 : 실패율 (42889) (0) | 2023.06.20 |
프로그래머스 : 신규 아이디 추천 (72410) (0) | 2023.06.19 |