22.02.21 ~ 22.02.28
📌 키패드 누르기[카카오 인턴]
문제 설명
스마트폰 전화 키패드의 각 칸에 다음과 같이 숫자들이 적혀 있습니다.
이 전화 키패드에서 왼손과 오른손의 엄지손가락만을 이용해서 숫자만을 입력하려고 합니다.
맨 처음 왼손 엄지손가락은 * 키패드에 오른손 엄지손가락은 # 키패드 위치에서 시작하며, 엄지손가락을 사용하는 규칙은 다음과 같습니다.
- 엄지손가락은 상하좌우 4가지 방향으로만 이동할 수 있으며 키패드 이동 한 칸은 거리로 1에 해당합니다.
- 왼쪽 열의 3개의 숫자 1, 4, 7을 입력할 때는 왼손 엄지손가락을 사용합니다.
- 오른쪽 열의 3개의 숫자 3, 6, 9를 입력할 때는 오른손 엄지손가락을 사용합니다.
- 가운데 열의 4개의 숫자 2, 5, 8, 0을 입력할 때는 두 엄지손가락의 현재 키패드의 위치에서 더 가까운 5. 엄지손가락을 사용합니다.
4-1. 만약 두 엄지손가락의 거리가 같다면, 오른손잡이는 오른손 엄지손가락, 왼손잡이는 왼손 엄지손가락을 사용합니다.
순서대로 누를 번호가 담긴 배열 numbers, 왼손잡이인지 오른손잡이인 지를 나타내는 문자열 hand가 매개변수로 주어질 때, 각 번호를 누른 엄지손가락이 왼손인 지 오른손인 지를 나타내는 연속된 문자열 형태로 return 하도록 solution 함수를 완성해주세요.
[제한사항]
numbers 배열의 크기는 1 이상 1,000 이하입니다.
numbers 배열 원소의 값은 0 이상 9 이하인 정수입니다.
hand는 "left" 또는 "right" 입니다.
"left"는 왼손잡이, "right"는 오른손잡이를 의미합니다.
왼손 엄지손가락을 사용한 경우는 L, 오른손 엄지손가락을 사용한 경우는 R을 순서대로 이어붙여 문자열 형태로 return 해주세요.
내가 생각했던 풀이 방향
1,4,7 -> left
3,6,9 -> right
2,5,8,0 -> 현재 왼/오 엄지 위치와 목적지의 거리 중 짧은 것
거리를 담는 변수: (x,y) 좌표 기준으로 차이만큼.
현재 위치와 목적지의 거리를 구하는 방법에 대해 제일 오래 고민했다. 아예 키패드 모양의 2차원 배열을 작성해두고 각 목적지의 좌표를 활용하고 싶었는데, 단순히 숫자로 2차원 배열을 써서는 각 좌표(즉 인덱스)를 알아내기 어려울 것 같았다. 그 부분을 제일 어렵게 생각했고 그러느라 시간을 제일 많이 썼다^^..
다른 사람의 풀이 1
class Solution {
// 0부터 9까지 좌표 {y,x}
int[][] numpadPos = {
{3,1}, //0
{0,0}, //1
{0,1}, //2
{0,2}, //3
{1,0}, //4
{1,1}, //5
{1,2}, //6
{2,0}, //7
{2,1}, //8
{2,2} //9
};
//초기 위치
int[] leftPos = {3,0};
int[] rightPos = {3,2};
String hand;
public String solution(int[] numbers, String hand) {
this.hand = (hand.equals("right")) ? "R" : "L";
String answer = "";
for (int num : numbers) {
String Umji = pushNumber(num);
answer += Umji;
if(Umji.equals("L")) {leftPos = numpadPos[num]; continue;}
if(Umji.equals("R")) {rightPos = numpadPos[num]; continue;}
}
return answer;
}
//num버튼을 누를 때 어디 손을 사용하는가
private String pushNumber(int num) {
if(num==1 || num==4 || num==7) return "L";
if(num==3 || num==6 || num==9) return "R";
// 2,5,8,0 일때 어디 손가락이 가까운가
if(getDist(leftPos, num) > getDist(rightPos, num)) return "R";
if(getDist(leftPos, num) < getDist(rightPos, num)) return "L";
//같으면 손잡이
return this.hand;
}
//해당 위치와 번호 위치의 거리
private int getDist(int[] pos, int num) {
return Math.abs(pos[0]-numpadPos[num][0]) + Math.abs(pos[1]-numpadPos[num][1]); //(1)
}
}1번 풀이는 내가 생각했던 방향과 비슷하다.
아예 각 키패드 자리의 좌표를 2차원 배열에 담아두고, 목적지의 좌표를 가지고 getDist라는 함수를 거쳐서 현재 위치와 목적지 사이의 거리를 구했다.
다만, getDist의 기능에 해당하는 (1)과 같은 코드를 나는 생각하지 못했고, 이 풀이는 생각했다는 점에서 아쉬웠다. 처음부터 끝까지 좌표로 끌고 나갈거면 이런 식으로 진행했어야 한다.
pos[0] - numpadPos[num][0]는 각 y좌표의 차이, pos[1]-numpadPos[num][1]는 각 x좌표의 차이.
다른 사람의 풀이 2
class Solution {
public String solution(int[] numbers, String hand) {
String answer = new String();
int left=10, right=12; //(1)
for(int number: numbers){
if(number == 0) {
number=11;
}
if(number%3 == 1){
answer += "L";
left = number;
}
else if(number % 3 == 0){
answer += "R";
right = number;
}
else {
int left_distance = getDistance (left, number);
int right_distance = getDistance (right, number);
if (left_distance > right_distance) {
answer += "R";
right = number;
}
else if (left_distance < right_distance) {
answer += "L";
left = number;
}
else {
if (hand.equals("left")) {
answer += "L";
left = number;
}
else {
answer += "R";
right = number;
}
}
}
}
return answer;
}
public int getDistance(int start, int end){ //(2)
int x = (start - 1) / 3;
int y = (start - 1) % 3;
int endX = end / 3;
int endY = 1;
return Math.abs(x-endX) + Math.abs(y-endY);
}
}(1) 맨 처음 왼손과 오른손의 시작점은 '*'과 '#'다. 이를 숫자 키패드에 연속성을 이루도록 10, 12로 생각하고 가운데에 있는 '0'은 11이라고 부르기로 한다. 그러면 1부터 12까지 있는 키패드라고 생각하고 문제를 풀 수 있다.
핵심적인 원리는 풀이 1과 비슷하다. 대신 1,4,7은 3으로 나눴을 때의 나머지가 항상 1이라는 점을 활용해서 왼손을 사용하게 되는 경우를 구분했다. 오른손은 3,6,9이므로 3으로 나눴을 때의 나머지가 항상 0.
가장 복잡한 2,5,8,0을 누를 때는 각 경우에 대해 if 문으로 나눠두었다. 물론 현재 위치와 목적지 사이의 거리를 기준으로 해야하니까 이 풀이도 getDistance(인수1, 인수2)로 거리를 구한다.
(2) 거리를 구할 때, x좌표는 1을 뺀 상태에서 3으로 나눈 몫을 구하는데.. 1을 빼주는 이유를 잘 모르겠다. 진짜 x 좌표를 구하기 위해서인가?
📌 약수의 개수와 덧셈
초기 코드
class Solution {
public int solution(int left, int right) {
int answer = 0;
return answer;내가 작성한 코드
import java.util.ArrayList;
class Solution {
public int solution(int left, int right) {
int answer = 0;
for (int i = left; i <= right; i++) {
if (cnt(i) % 2 == 0) { //(1)
answer += i;
}
else {
answer -= i;
}
}
return answer;
}
public int cnt (int num) {
ArrayList arr = new ArrayList();
for (int i = 1; i <= num; i++) {
if (num % i == 0 && !arr.contains(i)) { //(2)
arr.add(i);
if (i != num/i) {
arr.add(num/i);
}
}
}
return arr.size();
}
}(1) 약수의 개수 구하는 함수의 결과값이 짝수냐 홀수냐를 기준으로 더하거나 뺀다.
(2) cnt라는 함수를 통해 약수의 개수 구하기 -약수를 배열에 담고, 없는 값이면 추가. 이때 중복을 제거하기 위해 contains()를 써서 원소 추가하기 전 미리 검사하는 조건문을 달았다. 중복을 허용하지 않는 자료형인 Set을 사용할까 고민했던 지점이다.
다른 사람의 풀이 1
import java.util.*;
class Solution {
int yaksu(int x) {
if(x == 1) return 1;
Set<Integer> set = new HashSet<>(); //(1)
for(int i = 1; i <= x / 2; i++) {
if(x % i == 0) {
set.add(i);
set.add(x / i);
}
}
return set.size();
}
public int solution(int left, int right) {
int answer = 0;
for(; left <= right; left++)
answer += left * (yaksu(left) % 2 == 0 ? 1 : -1); //(2)
return answer;
}
}(1) 이 풀이에서는 중복을 허용하지 않는다는 점을 반영해서 HashSet<>에 약수를 담았다. 이렇게도 해볼걸!
(2) answer에 숫자를 더하거나 빼지 않았다. 조건에 따라 양수/음수를 만들도록 1/-1을 곱해서 부호를 정해주고, 그 값을 answer에 누적시킨다. 나는 경우에 따라 더하거나 빼야하는 상황에 자꾸 조건문만 쓰려고 하는데 삼항연산자를 활용해서 한줄로 쓰는 것도 좀 더 고려했으면 좋겠다.
다른 사람의 풀이 2
class Solution {
public int solution(int left, int right) {
int answer = 0;
for (int i=left;i<=right;i++) {
//제곱수인 경우 약수의 개수가 홀수
if (i % Math.sqrt(i) == 0) {
answer -= i;
}
//제곱수가 아닌 경우 약수의 개수가 짝수
else {
answer += i;
}
}
return answer;
}
}이 풀이는 숫자의 특성 자체를 고려해서 깔끔하게 작성했길래 가져왔다!
각 약수가 무엇인지는 궁금하지 않고, 개수만 확인하면 되므로 저런 방향으로도 문제가 풀리더라. 약수의 개수가 홀/짝으로 갈리도록 만드는 지점이 뭔지 고민해봤으면 좋았을 것 같다.
📌 내적
초기 코드
class Solution {
public int solution(int[] a, int[] b) {
int answer = 0;
return answer;
}
}내가 작성한 코드
class Solution {
public int solution(int[] a, int[] b) {
int answer = 0;
for (int i = 0; i < a.length; i++) {
answer += a[i] * b[i];
}
return answer;
}
}내적이 무엇인지 문제 설명에서 식이 다 나와있어서 그것만 반복문으로 만들어주면 되는 거라 쉬웠다.
📌 소수만들기
초기 코드
class Solution {
public int solution(int[] nums) {
int answer = 0;
return answer;
}내가 작성한 코드
import java.util.HashSet;
import java.util.Set;
class Solution {
public int solution(int[] nums) {
int answer = 0;
//3개만 필요함. 순서대로 할 필요는 없지만 각 조합끼리 중복되지 않게 하는 것도 필요.
// 조합을 저장할까?
// 소수 판별 함수 별도로 만들까?
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
for (int k = j + 1; k < nums.length; k++) {
if (prime(nums[i], nums[j], nums[k]))
answer += 1;
}
}
}
return answer;
}
public boolean prime(int a, int b, int c) {
int sum = 0;
sum = a + b + c;
Set<Integer> set = new HashSet<Integer>();
for (int i = 1; i <= sum; i++) {
if (sum % i == 0) {
set.add(i);
set.add(sum/i);
}
}
if (set.size() == 2) {
return true;
}
return false;
}
}다른 사람의 풀이
import java.util.Arrays;
class Solution {
public int solution(int[] nums) {
int ans = 0;
for(int i = 0; i < nums.length - 2; i ++){ //(1)
for(int j = i + 1; j < nums.length - 1; j ++){
for(int k = j + 1; k < nums.length; k ++ ){
if(isPrime(nums[i] + nums[j] + nums[k])){
ans += 1;
}
}
}
}
return ans;
}
public Boolean isPrime(int num){
int cnt = 0;
for(int i = 1; i <= (int)Math.sqrt(num); i ++){ //(2)
if(num % i == 0) cnt += 1;
}
return cnt == 1;
}
}내 풀이랑 거의 비슷하다.
하지만 내가 놓쳤던 점은, (1)의 3주 반복문에서 각 반복횟수를 인덱스가 넘치게 지정해줬다는 거다. 이 풀이에서처럼, i는 맨 마지막 인덱스까지 도달하면 안되고 그 전전 인덱스에서 멈춰야 한다. 그래야 마지막에 k가 인덱스 범위를 뛰어넘지 않고 마지막 인덱스에 무사히 도달하기 때문이다. 나처럼 셋 다 nums.length로 제한했다면 IndexRange 오류를 만날 가능성이 있다. 물론 여기서는 3중 반복문이라 j나 k가 혼자서 인데스 범위 밖으로 튀어나갈일은 없었겠지만 다음엔 꼭 인덱스 오류 챙겨야겠다.
(2) 나는 제곱근이나 나눈 몫이 중복으로 담기는 걸 막기 위해 Set 컬렉션의 HashSet에 담았다. 하지만 이 풀이는 약수를 제곱근 이전까지만 따져서 몫이 중복되는 것도 방지했다. Math.sqrt(num)이라는 함수로 제곱근을 구할 수 있다는 점을 활용! 이렇게 하면, 나처럼 set.size() == 2라고 조건문을 써주지 않아도 되고 별도로 set 선언해서 써줄 필요도 없다. num이 i로 나눠 떨어지면 cnt를 1 늘려줘서 약수의 개수를 세는 방식이고 return cnt == 1; 에서 cnt가 1일 때만 (소수일 때만) true를 리턴하는 아주 효율적인..코드...!
📌 소수 찾기
초기 코드
class Solution {
public int solution(int n) {
int answer = 0;
return answer;
}
}내가 작성한 코드 (오답)
class Solution {
public int solution(int n) {
int answer = 0;
for (int i = 2; i <= n; i++) {
if (isprime(i)) {
answer++;
}
}
return answer;
}
public boolean isprime(int n) {
int cnt = 0;
for (int i = 1; i <= (int)Math.sqrt(n); i++) {
if (n % i == 0) {
cnt++; //(1)
}
}
return cnt == 1;
}
}
실행이 되긴 되는데 효율성에서 잔뜩 실패다..!! 반복문을 많이 돌리는 게 실패 원인인가 싶었다.
그리고 (1)에서 보듯, n의 약수 개수인 cnt를 계속 누적시키는 것은 불필요한 작업이다. 소수인지 아닌지만 알면 되고 특정 숫자인 n의 약수 개수를 저장해둘 필요가 없다.
사실.. 애초에 2부터 시작해서 모든 숫자들에 대해 소수 검사를 하는 행위 자체가 비효율적이라고 한다^^..
[질문하기]에서 얻은 힌트 1! (출처: https://programmers.co.kr/questions/21359)
- 1보다 큰 모든 자연수는 소수의 곱으로 이루어져 있다.
이것은 가장 기본적인 정리입니다. 이 정리가 의미하는 바는 무엇일까요? 대부분의 사람들은 소수를 구하기 위해서 2부터 차례대로 증가시켜서 나누어보는 방법을 이용할 것 입니다. 그러나 이 방식은 굉장히 비효율적인입니다. 그렇지만 1보다 큰 자연수는 소수의 곱으로 이루어져 있기 때문에 소수로만 나누면 됩니다. 예를 들어서, 10이 소수인지 아닌지를 알기 위해서 10보다 작은 소수만을 이용하면 됩니다. 실제로 10보다 작은 소수는 4개입니다. 그러니깐 4개만 이용하면 됩니다. 그리고 100이 소수인지 아닌지를 알기 위해서 99개의 자연수를 모두 이용한 것 대신에 25개의 소수만 이용하면 됩니다.- 어떤 자연수 n이 있을 때, √n 보다 작은 모든 소수들로 나누어 떨어지지 않으면 n은 소수입니다.
언뜻 이해하기 힘들겠지만 한 번 이해하면 쉽습니다. 증명을 생략하고 예를 들겠습니다. 먼저 101이 소수인지 아닌지 판별하기 위해서 우리는 √101을 구하면 10.xxx이 됩니다. 자 10보다 작은 소수는 뭐가 있을까요? 일단 2, 3, 5, 7이 있습니다. 그런데 딱 봐도 이 4개의 소수로만 101이 나누어 떨어지지 않습니다. 그러므로 101소수입니다. 위의 방식을 이용하면 25개의 소수를 모두 이용해야 하지만 지금은 4개만 이용해도 쉽게 계산이 됩니다.
[질문하기]에서 얻은 힌트 2! (출처: https://programmers.co.kr/questions/26173)
[에라토스테네스의 체를 통한 해결방법 정리]
만약 위 불필요한 계산을 하지않고
배열로 정리하여 모든 수들을 각 방의 번호에 대입합니다. ex)a[0] = 0, a[1] = 1, a[2] = 2 ... a[n] = n
그리고 1은 소수가 아니니 0이라고 정의해봅시다. a[1] = 0
그럼 나머지 방들은 각 방마다 자신의 번호의 수가 있을 겁니다.
조건문으로 만약 방의 값이 0이 아니라면 지속한다고 해봅시다.
2번째 방의 값은 0이 아님 -> 소수이기 때문에 2라고 두고
n범위 까지의 수 범위에서 2의 배수인 수들의 방안의 값을 0이라고 정의합니다 -> (a)
3번째 방의 값은 0이 아님 -> 소수이기 때문에 3이라고 둠
n범위 까지의 수 범위에서 3의 배수인 수들의 방안의 값을 0이라고 정의합니다 -> (b)
4는 (a)에서 0이라고 정의 -> 소수가 아니라고 정의 했기 때문에 넘어갑니다. -> 계산하지 않아도 됨 -> 시간 절약
5번째 방의 값은 0이 아님 -> 소수이기 때문에 5이라고 둠
n범위 까지의 수 범위에서 5의 배수인 수들의 방안의 값을 0이라고 정의합니다
6은 (a),(b)에서 0이라고 정의 -> 소수가 아니라고 정의 했기 때문에 넘어갑니다. -> 계산하지 않아도 됨 -> 시간 절약
7번째 방의 값은 0이 아님 -> 소수이기 때문에 7이라고 둠
n범위 까지의 수 범위에서 7의 배수인 수들의 방안의 값을 0이라고 정의합니다
8은 (a)에서 0이라고 정의 -> 소수가 아니라고 정의 했기 때문에 넘어갑니다. -> 계산하지 않아도 됨 -> 시간 절약
9은 (b)에서 0이라고 정의 -> 소수가 아니라고 정의 했기 때문에 넘어갑니다. -> 계산하지 않아도 됨 -> 시간 절약
10은 (a)에서 0이라고 정의 -> 소수가 아니라고 정의 했기 때문에 넘어갑니다. -> 계산하지 않아도 됨 -> 시간 절약
...
처럼 8,9,10에서 1부터 계산하지 않고도 소수라고 정의할 수 있습니다.
그렇게 되면 주어진 범위 내에서 모든 소수를 찾으셨을텐데
소수가 아닌 수는 0이라고 정의했기 때문에
조건문으로 배열안에 있는 수가 0이 아니라면
answer++
라고 정의해주시고 마지막에 return answer; 라고 해주시면 n의 범위에서 소수의 갯수를 모두 더한 answer값이 제출 될겁니다.
에라토스테네스.. 처음 들어봤다. 맨 앞부터 하나씩 다 뒤져가는 건 비효율적이라니! 여태껏 그렇게 풀어왔는데ㅠㅠ.. 이제는 새로운 방법으로 엄청 많은 범위에 대해서도 소수 판별을 할 줄 알게 되었다.
다른 사람의 풀이 (정답-에라토스테네스의 체 활용)
(출처: https://programmers.co.kr/questions/26173)
class Solution {
public int solution(int n) {
int answer = 0; // 정답 정의
int[] arr = new int[n+1]; // int타입의 arr은 n+1개의 갯수만큼 int타입으로 공간을 가짐
// 모든 수를 배열에 저장
for(int i=0;i<=n;i++){ // int타입 i; 0부터 n이하까지 반복; i++
arr[i]=i; // arr의 i번째 방은 i이다
}// 0번째 방은 =1, n-1번째 방은 =n이 된다
// 1은 소수가 아니라서 0이라고 정의 --> 0이라고 함
arr[1]=0; // arr의 1번째 방은 0
// 소수 찾기 시작
for(int i=2;i<=n;i++){//2부터 계산해줌 int타입 i는 2; i가 n이하까지 반복; i++
// 만약 이전에 찾았던 소수의 배수 값일 경우 계산없이 다음 수로 이동
if(arr[i]==0)continue; // arr[i]번째 방이 0이라면 반복문의 처음으로 이동
// 에라토스테네스의 체를 통해 배수의 수는 소수가 아니라고 정의
for(int j=i*2;j<=n;j+=i){ // int타입 j가 i*2이고; j가 n이하까지 반복; j = j+i -> 계산을 하지않고 소수가 아닌 값을 찾음
arr[j]=0; // arr의 j번째 방은 0 -> 소수가 아니라면
}
}
// 정답 계산
for(int i=0;i<arr.length;i++){ // int타입 i는 arr의 길이 미만동안 반복 i++
if(arr[i]!=0){ // arr의 i번째 방이 0이 아니라면 -> 소수
answer++; // answer++
}
}
return answer;
}
}
행마다 주석까지 완벽하게 달려있는 친절한 정답코드..!
오늘 배운점: 소수 판별할 때 모든 수를 검사하는 건 비효율적이고, 에라토스테네스의 체를 활용하면 효율성이 대폭 개선된다 🥲.
