프로그래머스 입문 Day 22 파이썬

프로그래머스

저주의 숫자 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입니다.

solution.py

def solution(n):
    answer = 0
    for i in range(n):
        answer += 1
        while answer % 3 == 0 or '3' in str(answer):
            answer += 1
    return answer

---

평행

문제 설명

점 네 개의 좌표를 담은 이차원 배열  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

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

문제 분석

의사 코드(pseudo code)
1 네 개의 점 입력
2 서로 다른 두 점 선택
3 각 쌍마다
  a 첫 번재 선분 기울기 구하기
  b 두 번재 선분 기울기 구하기
  c 기울기가 같으면 1 반환 다르면 0 반환

solution.py

def solution(dots):
    def temp(a, b, c, d):
        return (b[1] - a[1]) * (d[0] - c[0]) == (d[1] - c[1]) * (b[0] - a[0])
    
    return int(
        is_parallel(dots[0], dots[1], dots[2], dots[3]) or
        is_parallel(dots[0], dots[2], dots[1], dots[3]) or
        is_parallel(dots[0], dots[3], dots[1], dots[2])
    )

복잡도 분석

temp 함수의 사칙연산 6회, 비교 1회의 시간 복잡도는 O(1)입니다.
함수 내에서 생성되는 지역 변수 a, b, c, d 등의 상수 크기 변수의 공간 복잡도는 O(1)입니다.
따라서 최종 시간 복잡도와 공간 복잡도는 O(1)입니다.

---

겹치는 선분의 길이

문제 설명

선분 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 합니다.

문제 분석

의사 코드(pseudo code)
1 선분의 전체 범위 리스트 생성
2 각 선분의 범위 배열 1 더하기
3 배열에서 값이 2 이상인 개수 세기
4 개수 반환

solution.py

def solution(lines):
    answer = [0] * 201
    
    for start, end in lines:
        for i in range(start + 100, end + 100):
            answer[i] += 1
            
    return sum(1 for j in answer if j >=2 )

복잡도 분석

각 선분에 대한 구간 순회의 시간 복잡도는 O(1)입니다.
전체 선분 범위를 지정하기 위한 배열 등의 공간 복잡도는 O(1)입니다.
따라서 최종 시간 복잡도와 공간 복잡도는 O(1)입니다.

---

유한소수 판별하기

문제 설명

소수점 아래 숫자가 계속되지 않고 유한개인 소수를 유한소수라고 합니다.

분수를 소수로 고칠 때 유한소수로 나타낼 수 있는 분수인지 판별하려고 합니다.

유한소수가 되기 위한 분수의 조건은 다음과 같습니다.

• 기약분수로 나타내었을 때, 분모의 소인수가 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

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

solution.py

def solution(a, b):
    def gcd(x, y):
        while y:
            x, y = y, x % y
        return x

    g = gcd(a, b)
    b //= g

    for i in [2, 5]:
        while b % i == 0:
            b //= i

    return 1 if b == 1 else 2