DAY22 dp, 수학, 조건문, 배열

1️⃣ 저주의 숫자 3

 

문제 설명

3x 마을 사람들은 3을 저주의 숫자라고 생각하기 때문에 3의 배수와 숫자 3을 사용하지 않습니다. 3x 마을 사람들의 숫자는 다음과 같습니다.

10진법	3x 마을에서 쓰는 숫자	10진법	3x 마을에서 쓰는 숫자
1	1	6	8
2	2	7	10
3	4	8	11
4	5	9	14
5	7	10	16

 

정수 n이 매개변수로 주어질 때, n을 3x 마을에서 사용하는 숫자로 바꿔 return하도록 solution 함수를 완성해주세요.

 

제한사항

• 1 ≤ n ≤ 100

입출력 예

n	result
15	25
40	76

 

입출력 예 #1

• 15를 3x 마을의 숫자로 변환하면 25입니다.

입출력 예 #2

• 40을 3x 마을의 숫자로 변환하면 76입니다.

---

 

💻 나의 풀이

class Solution {
    public int solution(int n) {
        int answer = 0;
        int count = 0;
        
        while(count<n) {
            answer++;
            
            if(answer % 3 == 0 || Integer.toString(answer).contains("3")){
                continue;
            }
            count++;
        }
        return answer;
    }
}

 

 

 

 

🔎 다른 사람의 풀이

class Solution {
    public int solution(int n) {
        int answer = 0;

        for (int i = 1; i <= n; i++) {
            answer++;
            if (answer % 3 == 0 || String.valueOf(answer).contains("3")) {
                i--;
            }
        }

        return answer;
    }
}

 

굳이 count 변수를 사용할 필요 없이 1부터 n까지의 숫자를 반복하는 for 루프를 설정합니다. 그리고 각 반복에서 answer를 1씩 증가시킵니다.

그런데 만약 answer가 3의 배수이거나 3이 포함되어 있다면 현재 반복에서 i를 1 감소시킵니다.

 

---

 

2️⃣ 평행

 

문제 설명

점 네 개의 좌표를 담은 이차원 배열  dots가 다음과 같이 매개변수로 주어집니다.

• [[x1, y1], [x2, y2], [x3, y3], [x4, y4]]

주어진 네 개의 점을 두 개씩 이었을 때, 두 직선이 평행이 되는 경우가 있으면 1을 없으면 0을 return 하도록 solution 함수를 완성해보세요.

제한사항

• dots의 길이 = 4
• dots의 원소는 [x, y] 형태이며 x, y는 정수입니다.
  • 0 ≤ x, y ≤ 100
• 서로 다른 두개 이상의 점이 겹치는 경우는 없습니다.
• 두 직선이 겹치는 경우(일치하는 경우)에도 1을 return 해주세요.
• 임의의 두 점을 이은 직선이 x축 또는 y축과 평행한 경우는 주어지지 않습니다.

입출력 예

dots	result
[[1, 4], [9, 2], [3, 8], [11, 6]]	1
[[3, 5], [4, 1], [2, 4], [5, 10]]	0

 

입출력 예 #1

• 점 [1, 4], [3, 8]을 잇고 [9, 2], [11, 6]를 이으면 두 선분은 평행합니다.

입출력 예 #2

• 점을 어떻게 연결해도 평행하지 않습니다.

---

 

💻 나의 풀이

좌표의 두 개를 비교해서 각각 뺐을 때 나오는 값이 동일하면 평행한다는 생각으로 문제를 해결하려고 했었는데 잘 안됐다...기울기에 대한 아이디어까지는 떠올랐는데 결국 혼자 해결은 못했습니다. 😥

점점 난이도1 같은 문제들이 나오는거 같아요;

 

 

 

🔎 다른 사람의 풀이

import java.util.ArrayList;
import java.util.List;

class Solution {
	public int solution(int[][] dots) {
		int answer = 0;

		List<Double> slopes = new ArrayList<>();

		for (int i = 0; i < dots.length - 1; i++) {
			for (int j = i+1; j < dots.length; j++) {

				double sideX = dots[i][1] - dots[j][1];
				double sideY = dots[i][0] - dots[j][0];

				double slop = sideY / sideX;

				if (!slopes.contains(slop)) {
					slopes.add(slop);
				} else {
					answer = 1;
					break;
				}
			}
			if(answer==1) {
				break;
			}
		}
		return answer;
	}
}

 

두 점들의 평행 여부는 기울기를  확인하면 됩니다.

기울기 = 세로길이/가로길이

기울기가 0이 나오면 이미 존재하는 기울기로 인식하는 문제 떄문에 List자료형을 활용하고, 가로 세로 길이는 double 타입으로 지정해준다고 합니다.

점간의 거리 확인 시에는 서로 겹치면 안되기 때문에 외부 반복문은 마지막 index전까지만 반복해주고, 내부 반복문은 외부에서 오는 요소보다 한 index 높은 요소부터 검사해줍니다.

기울기는 slopes에 삽입되다가, 중복된 기울기 값(slope)이 들어오면 answer=1로 해주고, 반복문을 종료해줍니다. 

외부 반복문도 같은 조건으로 종료해줍니다.

 

참고 https://velog.io/@osy8814/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4JAVA%ED%8F%89%ED%96%89

 

그런데!

이 코드도 테스트12 부터는 실패네요.

 

 

class Solution {
    public int solution(int[][] dots) {
        int x1 = dots[0][0];
        int y1 = dots[0][1];
        int x2 = dots[1][0];
        int y2 = dots[1][1];
        int x3 = dots[2][0];
        int y3 = dots[2][1];
        int x4 = dots[3][0];
        int y4 = dots[3][1];
        int answer = 0;
        
        double slope1 = (double) (y2 - y1) / (x2 - x1);
        double slope2 = (double) (y4 - y3) / (x4 - x3);
        if (slope1 == slope2) answer = 1;
        
        slope1 = (double) (y3 - y1) / (x3 - x1);
        slope2 = (double) (y2 - y4) / (x2 - x4);
        if (slope1 == slope2) answer = 1;
        
        slope1 = (double) (y4 - y1) / (x4 - x1);
        slope2 = (double) (y2 - y3) / (x2 - x3);
        if (slope1 == slope2) answer = 1;
        
        return answer;
    }
}

 

1. 1,2 vs 3,4
2. 1,3 vs 2,4
3. 1,4 vs 2,3

 

조합할 수 있는 것들을 조합해서 다 적어주는 걸로 코드를 변경했습니다.

 

---

 

 

3️⃣ 겹치는 선분의 길이

 

문제 설명

선분 3개가 평행하게 놓여 있습니다. 세 선분의 시작과 끝 좌표가 [[start, end], [start, end], [start, end]] 형태로 들어있는 2차원 배열 lines가 매개변수로 주어질 때, 두 개 이상의 선분이 겹치는 부분의 길이를 return 하도록 solution 함수를 완성해보세요.

lines가 [[0, 2], [-3, -1], [-2, 1]]일 때 그림으로 나타내면 다음과 같습니다.

선분이 두 개 이상 겹친 곳은 [-2, -1], [0, 1]로 길이 2만큼 겹쳐있습니다.

 

제한사항

• lines의 길이 = 3
• lines의 원소의 길이 = 2
• 모든 선분은 길이가 1 이상입니다.
• lines의 원소는 [a, b] 형태이며, a, b는 각각 선분의 양 끝점 입니다.
  • -100 ≤ a < b ≤ 100

입출력 예

lines	result
[[0, 1], [2, 5], [3, 9]]	2
[[-1, 1], [1, 3], [3, 9]]	0
[[0, 5], [3, 9], [1, 10]]	8

 

입출력 예 #1

• 두 번째, 세 번째 선분 [2, 5], [3, 9]가 [3, 5] 구간에 겹쳐있으므로 2를 return 합니다.

입출력 예 #2

• 겹친 선분이 없으므로 0을 return 합니다.

입출력 예 #3

• 첫 번째와 두 번째 선분이 [3, 5] 구간에서 겹칩니다.
• 첫 번째와 세 번째 선분 [1, 5] 구간에서 겹칩니다.
• 두 번째와 세 번째 선분 [3, 9] 구간에서 겹칩니다.
• 따라서 [1, 9] 구간에 두 개 이상의 선분이 겹쳐있으므로, 8을 return 합니다.

---

💻 나의 풀이

class Solution {
    public int solution(int[][] lines) {
        int[] rail = new int[200];
        for (int[] line : lines) {
            for (int j = (line[0] + 100); j < (line[1] + 100); j++) {
                rail[j]++;
            }
        }

        int answer = 0;
        for (int value : rail) {
            if (value > 1) answer++;
        }
        return answer;
    }
}

 

선분의 시작점과 끝점의 범위가 -100 ≤ a < b ≤ 100 인데 음수의 인덱스 값을 표현할 수 없기 때문에 0~200 범위의 배열을 만들어주고 입력받은 좌표에 100을 더해 배열에 선분을 그리도록 해줍니다.

이렇게 입력받은 좌표를 전부 입력하게 되면 배열 중 1보다 큰 수가 있는 것은 선분이 겹쳤다는 것입니다.

 

 

---

 

4️⃣ 유한소수 판별하기

 

문제 설명

소수점 아래 숫자가 계속되지 않고 유한개인 소수를 유한소수라고 합니다. 분수를 소수로 고칠 때 유한소수로 나타낼 수 있는 분수인지 판별하려고 합니다. 유한소수가 되기 위한 분수의 조건은 다음과 같습니다.

• 기약분수로 나타내었을 때, 분모의 소인수가 2와 5만 존재해야 합니다.

두 정수 a와 b가 매개변수로 주어질 때, a/b가 유한소수이면 1을, 무한소수라면 2를 return하도록 solution 함수를 완성해주세요.

 

제한사항

• a, b는 정수
• 0 < a ≤ 1,000
• 0 < b ≤ 1,000

입출력 예

a	b	result
7	20	1
11	22	1
12	21	2

 

입출력 예 #1

• 분수 7/20은 기약분수 입니다. 분모 20의 소인수가 2, 5 이기 때문에 유한소수입니다. 따라서 1을 return합니다.

입출력 예 #2

• 분수 11/22는 기약분수로 나타내면 1/2 입니다. 분모 2는 소인수가 2 뿐이기 때문에 유한소수 입니다. 따라서 1을 return합니다.

입출력 예 #3

• 분수 12/21는 기약분수로 나타내면 4/7 입니다. 분모 7은 소인수가 7 이므로 무한소수입니다. 따라서 2를 return합니다.

---

Hint

• 분자와 분모의 최대공약수로 약분하면 기약분수를 만들 수 있습니다.
• 정수도 유한소수로 분류합니다.

---

🔎 다른 사람의 풀이

import java.util.*;

class Solution {
    public int solution(int a, int b) {
        int finalB = b / GCD(a, b);
        
        while( finalB != 1) {
            if(finalB % 2 == 0) {
                finalB /= 2;
            }else if (finalB % 5 == 0) {
                finalB /= 5;
            }else {
                return 2;
            }
        }
        
        return 1;
    }
    // 유클리드 호제법!! 두 수의 최대 공약수 구하기
    private int GCD(int a, int b) {
        if (b == 0) {    // b가 0일 때, a와 0 사이의 최대공약수는 a 자체이다.
            return a;
        } else {
            return GCD(b, a % b);   // a를 b로 나눈 나머지와 b 사이의 최대공약수는 a와 b 사이의 최대공약수와 동일하다.
        }
    }
}

 

• 기약분수는 더이상 나뉘지 않는 분수고
• 유클리드 호제법은 두 수의 최대공약법을 구하는 공식이다.
• 유클리드 호제법으로 최대공약수를 구해서 비를 나눠준 값을 finalB로 선언한다.
• 반복문을 돌려서 finalB가 1이 되면 탈출하게 만들고
• 2로 나눠지면 2로 나누고 5로 나눠지면 5로 나누다가
• 1이 되면 탈출 => 이것은 유한소수다.
• 2와 5로 나눠질수 없는 수가 등장하면 2를 반환 => 이것은 무한소수다.
• 참고로 유한소수는 기약분수인 분모의 소인수가 2와 5로만 되어있어야 한다.

 

💡 유클리드 호제법(Euclidean Algorithm)

1. GCD(a, b) = GCD(b, a % b) : a를 b로 나눈 나머지와 b 사이의 최대공약수는 a와 b 사이의 최대공약수와 동일하다.
2. GCD(a, 0) = a : b가 0일 때, a와 0 사이의 최대공약수는 a 자체이다.

 

class Solution {
    public int solution(int a, int b) {
        int answer = 0;

        for (;b%2 == 0;) {
            b = b/2;
        }
        for (;b%5 == 0;) {
            b = b/5;
        }

        if ((a/(double)b)%1 == 0) {
            answer = 1;
        } else {
            answer = 2;
        }

        return answer;
    }
}