Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- SpringBoot
- springdatajpa
- 백준
- JPQL
- AOP
- QueryDSL
- http
- db
- Servlet
- Android
- Thymeleaf
- java
- spring
- 김영한
- 인프런
- 그리디
- Exception
- 스프링 핵심 기능
- Greedy
- 스프링
- 자바
- Spring Boot
- JDBC
- Proxy
- 스프링 핵심 원리
- 알고리즘
- jpa
- pointcut
- transaction
- kotlin
Archives
- Today
- Total
개발자되기 프로젝트
[프로그래머스] 키패드 누르기 본문
1. 문제
스마트폰 전화 키패드의 각 칸에 다음과 같이 숫자들이 적혀 있습니다.
이 전화 키패드에서 왼손과 오른손의 엄지손가락만을 이용해서 숫자만을 입력하려고 합니다.
맨 처음 왼손 엄지손가락은 * 키패드에 오른손 엄지손가락은 # 키패드 위치에서 시작하며, 엄지손가락을 사용하는 규칙은 다음과 같습니다.
- 엄지손가락은 상하좌우 4가지 방향으로만 이동할 수 있으며 키패드 이동 한 칸은 거리로 1에 해당합니다.
- 왼쪽 열의 3개의 숫자 1, 4, 7을 입력할 때는 왼손 엄지손가락을 사용합니다.
- 오른쪽 열의 3개의 숫자 3, 6, 9를 입력할 때는 오른손 엄지손가락을 사용합니다.
- 가운데 열의 4개의 숫자 2, 5, 8, 0을 입력할 때는 두 엄지손가락의 현재 키패드의 위치에서 더 가까운 엄지손가락을 사용합니다.
4-1. 만약 두 엄지손가락의 거리가 같다면, 오른손잡이는 오른손 엄지손가락, 왼손잡이는 왼손 엄지손가락을 사용합니다.
순서대로 누를 번호가 담긴 배열 numbers, 왼손잡이인지 오른손잡이인 지를 나타내는 문자열 hand가 매개변수로 주어질 때, 각 번호를 누른 엄지손가락이 왼손인 지 오른손인 지를 나타내는 연속된 문자열 형태로 return 하도록 solution 함수를 완성해주세요.
[제한사항]
- numbers 배열의 크기는 1 이상 1,000 이하입니다.
- numbers 배열 원소의 값은 0 이상 9 이하인 정수입니다.
- hand는 "left" 또는 "right" 입니다.
- "left"는 왼손잡이, "right"는 오른손잡이를 의미합니다.
- 왼손 엄지손가락을 사용한 경우는 L, 오른손 엄지손가락을 사용한 경우는 R을 순서대로 이어붙여 문자열 형태로 return 해주세요.
입출력 예
numbers | hand | result |
[1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5] | "right" | "LRLLLRLLRRL" |
[7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2] | "left" | "LRLLRRLLLRR" |
[1, 2, 3, 4, 5, 6, 7, 8, 9, 0] | "right" | "LLRLLRLLRL" |
입출력 예에 대한 설명
입출력 예 #1
순서대로 눌러야 할 번호가 [1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5]이고, 오른손잡이입니다.
왼손 위치오른손 위치눌러야 할 숫자사용한 손설명
* | # | 1 | L | 1은 왼손으로 누릅니다. |
1 | # | 3 | R | 3은 오른손으로 누릅니다. |
1 | 3 | 4 | L | 4는 왼손으로 누릅니다. |
4 | 3 | 5 | L | 왼손 거리는 1, 오른손 거리는 2이므로 왼손으로 5를 누릅니다. |
5 | 3 | 8 | L | 왼손 거리는 1, 오른손 거리는 3이므로 왼손으로 8을 누릅니다. |
8 | 3 | 2 | R | 왼손 거리는 2, 오른손 거리는 1이므로 오른손으로 2를 누릅니다. |
8 | 2 | 1 | L | 1은 왼손으로 누릅니다. |
1 | 2 | 4 | L | 4는 왼손으로 누릅니다. |
4 | 2 | 5 | R | 왼손 거리와 오른손 거리가 1로 같으므로, 오른손으로 5를 누릅니다. |
4 | 5 | 9 | R | 9는 오른손으로 누릅니다. |
4 | 9 | 5 | L | 왼손 거리는 1, 오른손 거리는 2이므로 왼손으로 5를 누릅니다. |
5 | 9 | - | - |
따라서 "LRLLLRLLRRL"를 return 합니다.
입출력 예 #2
왼손잡이가 [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2]를 순서대로 누르면 사용한 손은 "LRLLRRLLLRR"이 됩니다.
입출력 예 #3
오른손잡이가 [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]를 순서대로 누르면 사용한 손은 "LLRLLRLLRL"이 됩니다.
2. 아이디어
- *, 0, #을 어떻게 처리할 것인가.
- 이 문제의 핵심은 L, R을 표현하는 것 보다는 2, 5, 8, 0 을 누를 경우 현재 버튼에서 이동 거리를 판단하는 것.
- 결국 현재 위치로부터 2, 5, 8, 0까지 이동 거리를 알아야 함.
- 하지만 동일한 규칙을 적용하기 위해서는 *, 0, #이 방해됨
- ex)초기 *에서 0으로 이동하는 경우 1칸인데 이를 어떻게 표현?
- ex)2에서 0으로 이동하는 경우 3칸 이동인데, 4에서 0으로 이동하는 것도 3칸이동임. 어떻게 구분?
- 또한 키패드는 결국 3으로 나눴을 때 나머지가 1, 2, 0인 숫자를 세로로 배열한 것으로 볼 수 있다.
- 즉 숫자의 차이를 3으로 나눴을 때 몫 만큼 종으로 움직이고 나머지 만큼 횡으로 이동.
- ex) 1 -> 5 : 숫자 차이 = 4, 4/3의 몫 = 1, 4/3의 나머지 = 1 --> 아래로 한 칸, 옆으로 한 칸
- 그러나 이 논리를 적용하려 해도 *, 0, #이 방해된다.
- 즉, *, 0, #을 어떻게 바꾸는지가 중요함.
- 간단하다. * -> 10, 0 -> 11, # -> 12로 바꾸면 해당 논리를 적용할 수 있다.
- 입력되는 숫자의 배열에서 0을 11로 변경
- Hand라는 클래스를 만들어서 현재 위치를 가지고 있도록 하자.
- left의 초기 위치는 10(*)
- right의 초기 위치는 12(#)
3. 코드
class Solution {
public String solution(int[] numbers, String hand) {
String answer = "";
for (int i=0; i<numbers.length; i++){
if (numbers[i] == 0){
numbers[i] = 11;
}
}
Hand left= new Hand(10);
Hand right = new Hand(12);
for (int i=0; i< numbers.length; i++){
answer += pressButton(hand, left, right, numbers[i]);
}
return answer;
}
private String pressButton(String hand, Hand left, Hand right, int number) {
if (number == 1 || number == 4 || number == 7){
left.position= number;
return "L";
}else if (number == 3 || number == 6 || number == 9){
right.position= number;
return "R";
}else { // 10,2, 5, 8인 경우
int leftDistance = getDistance(number, left);
int rightDistance = getDistance(number, right);
if (leftDistance < rightDistance){
left.position= number;
return "L";
}else if (leftDistance > rightDistance){
right.position= number;
return "R";
}else {
if (hand.equals("left")){
left.position= number;
return "L";
}else {
right.position= number;
return "R";
}
}
}
}
public int getDistance(int number, Hand hand){
int subtract = Math.abs(number- hand.position);
int y = subtract / 3; //세로 이동
int x = subtract % 3; //가로 이동
return x+y;
}
public static class Hand{
int position;
public Hand(int position) {
this.position = position;
}
}
}
4. 정리
- 결국 예전에 수학 문제 풀듯이 문제를 해결할 수 있는 형태로 바꾸는 것도 중요함.
- 키패드의 경우 어떤 공통된 논리를 적용할 수 있도록 *, 0, #을 어떻게 처리할 지 고민.
- 키패드는 3배수를 기억하자 ㅋㅋㅋ
5. 코드 개선
- 기존 코드는 answer += "L" 과 같이 작성했다.
- 이를 StringBuffer의 append()로 바꿔보자.
- 왜냐? String의 +연산자는 속도가 느리기 때문.
- 왜느림? String은 인스턴스가 한 번 생성되면 그 값을 변경할 수 없는 불변 클래스(immutable class)이다.
- 따라서 +연산자와 같이 인스터스 값에 변화를 주면( String a = "abc"+"d") 새로운 인스턴스("abcd")를 생성한다.
- 이때 기존 String a가 새로운 인스턴스를 참조하게 된다.
- 이처럼 String은 불변 클래스기 때문에 값을 변경할 경우 새로운 인스턴스를 생성해야해서 느리다.
- 반면 StringBuilder, StringBuffer 인스턴스는 가변적이기 때문에 상대적으로 값을 벼경하는 연산이 빠르다.
public String solution(int[] numbers, String hand) {
StringBuilder answer = new StringBuilder();
for (int i=0; i<numbers.length; i++){
if (numbers[i] == 0){
numbers[i] = 11;
}
}
Hand left= new Hand(10);
Hand right = new Hand(12);
for (int i=0; i< numbers.length; i++){
answer.append(pressButton(hand, left, right, numbers[i]));
}
return answer.toString();
}
5. GitHub : 211204 KeyPad
'코테준비' 카테고리의 다른 글
[프로그래머스] 없는 숫자 더하기 (0) | 2021.12.05 |
---|---|
[프로그래머스] 인형뽑기 게임 (0) | 2021.12.05 |
[프로그래머스] 숫자 문자열과 영단어 (0) | 2021.12.04 |
[프로그래머스] 신규 아이디 추천 (0) | 2021.12.04 |
[프로그래머스] 로또의 최고 순위와 최저 순위 (0) | 2021.12.03 |
Comments