문제 설명
게임 캐릭터를 4가지 명령어를 통해 움직이려 합니다. 명령어는 다음과 같습니다.
- U: 위쪽으로 한 칸 가기
- D: 아래쪽으로 한 칸 가기
- R: 오른쪽으로 한 칸 가기
- L: 왼쪽으로 한 칸 가기
캐릭터는 좌표평면의 (0, 0) 위치에서 시작합니다. 좌표평면의 경계는 왼쪽 위(-5, 5), 왼쪽 아래(-5, -5), 오른쪽 위(5, 5), 오른쪽 아래(5, -5)로 이루어져 있습니다.
예를 들어, "ULURRDLLU"로 명령했다면
- 다음과 같이 움직입니다.
- 8번 명령어부터 9번 명령어까지 다음과 같이 움직입니다.
이때, 우리는 게임 캐릭터가 지나간 길 중 캐릭터가 처음 걸어본 길의 길이를 구하려고 합니다.
제한사항
- dirs는 string형으로 주어지며, 'U', 'D', 'R', 'L' 이외에 문자는 주어지지 않습니다.
- dirs의 길이는 500 이하의 자연수입니다.
나의 풀이
class Solution {
public int solution(String dirs) {
int lenOfDirs = dirs.length();
int x=0, y=0, bx=0, by=0;
int dot = 0;
HashSet<String> set = new HashSet<String>();
for(int i=0;i<lenOfDirs;i++) {
char dir = dirs.charAt(i);
if (dir == 'U') y++;
else if (dir == 'D') y--;
else if (dir == 'R') x++;
else x--; //dir == 'L'
if (x>5) x = 5;
if (x<-5) x = -5;
if (y>5) y = 5;
if (y<-5) y = -5;
String str1 = x+""+y+" "+bx+""+by;
String str2 = bx+""+by+" "+x+""+y;
bx = x;
by = y;
if(str1.equals(str2) && !set.contains(str1)) dot++;
set.add(str1);
set.add(str2);
}
return (set.size()-dot)/2;
}
}
캐릭터의 위치를 (x,y) 좌표로 계산하고, HashSet을 이용해 선을 저장했다.
String 부분을 StringBuilder로 더하려고 했는데 수정을 깜빡했다..(ㅠㅠ)
처음에는 HashSet에 거쳐간 점을 저장했었는데 예외처리하기가 번거롭다.
같은 점을 또 지났으나 지나온 길은 다를때 같은...
선은 두 점의 좌표를 String 형태로 묶어서 표시한다.
bx, by: 이전 위치의 점 좌표
x, y: 현재 위치의 점 좌표
로 취급해서 "점좌표 점좌표"를 저장한다.
점1-점2를 잇는 선과 점2-점1를 잇는 선이 같으므로 xy bxby, bxby xy 둘 다 HashSet에 저장한다.
만약 xy와 bxby가 동일하다는건 x나 y가 이동할 수 있는 위치를 벗어나려고 했던 시도이므로 dot에 카운트를 해준다.
이후에 Hashset의 크기를 구하면 구해야하는 선의 2배 크기이다.
(점1-점2 선분과 점2-점1 선분이 다르므로)
점1과 점2가 같은 경우 점1-점1 같은 형식의 선이 저장되어있으므로 크기에서 빼준다 (dot)
코드가 깔끔하다는 생각은 안든다ㅠㅠ
다른 사람 코드를 보며 몇 가지 개선 사항이 추가적으로 생각났다.
- String말고 StringBuilder 사용
- x, y가 범위를 벗어나면 set에 추가하지 않기
- x, y와 bx, by가 같으면 set에 추가하지 않기
HashSet에 무조건 추가하고 나서 계산식을 생각했는데 애초에 추가할 필요가 없었다.
개선 후 코드
class Solution {
public int solution(String dirs) {
int lenOfDirs = dirs.length();
int x=0, y=0, bx=0, by=0;
HashSet<String> set = new HashSet<String>();
for(int i=0;i<lenOfDirs;i++) {
char dir = dirs.charAt(i);
if (dir == 'U') y++;
else if (dir == 'D') y--;
else if (dir == 'R') x++;
else x--; //dir == 'L'
if (x>5) { x = 5; continue; }
if (x<-5) { x = -5; continue; }
if (y>5) { y = 5; continue; }
if (y<-5) { y = -5; continue; }
String str1 = makeLine(x,y,bx,by);
String str2 = makeLine(bx,by,x,y);
bx = x;
by = y;
set.add(str1);
set.add(str2);
}
return set.size()/2;
}
public String makeLine (int x, int y, int bx, int by) {
StringBuilder sb = new StringBuilder();
sb.append(x).append(y).append(" ").append(bx).append(by);
return sb.toString();
}
}
개선하니까 훨씬 빨리지는걸 볼 수 있다!!
다른 사람 코드
class Solution {
public int solution(String dirs) {
Map<String, int[]> map = new HashMap<>();
map.put("U", new int[] {0, 1});
map.put("D", new int[] {0, -1});
map.put("R", new int[] {1, 0});
map.put("L", new int[] {-1, 0});
String[] arr = dirs.split("");
Set<String> set = new HashSet<>();
int cx = 0;
int cy = 0;
for(int i=0; i<arr.length; i++) {
String s = arr[i];
int x = map.get(s)[0];
int y = map.get(s)[1];
cx += x;
cy += y;
if(cx < -5 || cx > 5) {
cx -= x;
continue;
}
if(cy < -5 || cy > 5) {
cy -= y;
continue;
}
set.add(""+(cx-x)+ ""+ (cy-y)+ ""+cx + ""+cy);
set.add(""+cx + ""+cy+""+(cx-x)+ ""+ (cy-y));
}
return set.size()/2;
}
}
출처: https://programmers.co.kr/learn/courses/30/lessons/49994/solution_groups?language=java
'Memo > 코테' 카테고리의 다른 글
부족한 금액 계산하기 (0) | 2021.09.16 |
---|---|
프린터 (0) | 2021.06.22 |
[Kakao] 신규 아이디 추천 (0) | 2021.05.26 |
[Codility] CountDiv (0) | 2021.04.22 |
[Codility] TapeEquilibrium (0) | 2021.04.21 |