2023. 6. 5. 19:15ㆍAlgorithm
1. 저주의 숫자 3
(문제 설명, 제한사항, 입출력 예)
3의 배수와 숫자 3을 사용하지 않는 3x 마을 사람들이 있다.
주어진 정수 n을 3x 마을에서 사용하는 숫자로 바꿔서 구하라는 문제이다. (단, 정수 n의 범위는 1 이상, 100 이하)
(내가 생각한 풀이 과정)
고려해줘야 하는 조건은 두 가지이다.
3의 배수일 경우 (answer % 3 == 0)와 숫자 3이 들어가 있는 경우 (str(answer).count('3'))
3x 마을은 위 조건의 경우 해당 숫자를 건너뛰기 때문에 +1을 해주면 된다.
주어진 수 n이 0이 될 때까지 1씩 빼보면서 해당 조건을 확인하면서 얼마큼을 건너뛰어야 하는지를 파악할 수 있다.
(코드)
💡 내 코드
def solution(n):
answer = 0
while n > 0:
while str(answer).count('3') != 0 or answer % 3 == 0:
answer += 1
answer += 1
n -= 1
return answer-1
2. 평행
(문제 설명, 제한사항, 입출력 예)
점 네 개의 좌표를 담은 이차원 배열이 아래와 같이 주어진다.
[[x1, y1], [x2, y2], [x3, y3], [x4, y4]]
주어진 네 개의 점을 두 개씩이었을 때, 두 직선이 평행이 되는 경우가 있으면 1을 없으면 0을 반환하라는 문제이다.
단, 서로 다른 두 개 이상의 점이 겹치는 경우는 없다.
또한, 두 직선이 서로 겹치는 경우 (일치하는 경우)에도 1을 반환해야 하며,
임의의 두 점을 이은 직선이 x축 또는 y축과 평행한 경우는 주어지지 않는다고 한다.
(내가 생각한 풀이 과정)
"두 직선이 평행하다 = 두 직선의 기울기가 같다", "기울기 = y 값의 증가량 / x 값의 증가량"
이 두 점만 알고 있으면 쉽게 해결할 수 있는 문제이다.
네 개의 점을 두 개씩 잇는 경우는 총 3가지가 존재하므로(1-2, 3-4 / 1-3, 2-4 / 1-4, 2-3), 이 경우들의 기울기가 같은지 확인하고, 만약 세 조건에 모두 해당하지 않는 경우에는 0을 반환하면 된다.
(코드)
💡 내 코드
def solution(dots):
if (dots[0][1]-dots[1][1])/(dots[0][0]-dots[1][0]) == (dots[2][1]-dots[3][1])/(dots[2][0]-dots[3][0]): return 1
elif (dots[0][1]-dots[2][1])/(dots[0][0]-dots[2][0]) == (dots[1][1]-dots[3][1])/(dots[1][0]-dots[3][0]): return 1
elif (dots[0][1]-dots[3][1])/(dots[0][0]-dots[3][0]) == (dots[1][1]-dots[2][1])/(dots[1][0]-dots[2][0]): return 1
else: return 0
3. 겹치는 선분의 길이
(문제 설명, 제한사항, 입출력 예)
선분 3개가 평행선 위에 놓여있다고 하자.
세 선분의 시작과 끝 좌표가 [[start, end], [start, end], [start, end]] 형태로 들어있는 2차원 배열 lines가 주어질 때, 두 개 이상의 선분이 겹치는 부분의 길이를 구하라는 문제이다.
모든 선분의 길이는 1 이상이며, 평행선의 길이는 -100 이상, 100 이하의 조건으로 주어졌다.
(내가 생각한 풀이 과정)
이번 풀이는 내가 조금 어렵게 풀었기 때문에 예시와 함께 설명하겠다.
입출력 예 #1에 쓰여있는 [[0, 1], [2, 5], [3, 9]]가 lines의 매개변수로 입력되었다고 가정하자.
우선 떠올랐던 방식은 세 개의 선분이 지나가는 점을 리스트 형태로 구해놓고, 이 리스트들을 집합(set) 자료형의 교집합 기능을 활용해 겹치는 구간을 구해줄 생각이었다.
그래서 line1, line2, line3라는 변수를 설정해 두고, 선분이 지나가는 점을 리스트로 추가했다.
line1 = [0, 1, 2], line2 = [-3, -2, -1], line3 = [-2, -1, 0, 1]의 형태로 추가가 되는 것이다.
이후에는 line1과 line2가 겹치는 점, line2와 line3가 겹치는 점, line1과 line3가 겹치는 점을 찾아주었다.
겹치는 점의 개수보다 1을 뺀 만큼 선분이 겹치기 때문에 겹치는 점의 개수를 len()으로 찾고, 1을 빼주었다.
(-2와 -1 위치에서 겹치면, 선분이 겹치는 부분의 길이는 1이다.)
마지막으로, line1과 line2, line3가 동시에 겹치는 부분의 길이를 빼주었다. 이 부분은 앞선 확인하는 부분에서 중복으로 체크되었을 것이기 때문이다.
이 상태로 최종 반환값을 구하면 최종 답안을 구할 수 있다.
(코드)
💡 내 코드
def solution(lines):
answer = 0
line1 = list(range(lines[0][0], lines[0][1]+1))
line2 = list(range(lines[1][0], lines[1][1]+1))
line3 = list(range(lines[2][0], lines[2][1]+1))
if len(list(set(line1) & set(line2)))==0:
answer += 0
else:
answer += len(list(set(line1) & set(line2)))-1
if len(list(set(line2) & set(line3)))==0:
answer += 0
else:
answer += len(list(set(line2) & set(line3)))-1
if len(list(set(line1) & set(line3)))==0:
answer += 0
else:
answer += len(list(set(line1) & set(line3)))-1
if len(list(set(line1) & set(line2) & set(line3)))==0:
answer += 0
else:
answer -= (len(list(set(line1) & set(line2) & set(line3)))-1)*2
return answer
💡 다른 사람의 풀이 코드
범위를 구하고, 집합 자료형을 사용해서, 교집합을 이용한 부분은 나와 생각이 같았다.
하지만, 이렇게 효과적으로 코드 길이를 줄일 수 있다는 것에 놀랐다.
바로 이 점이 파이썬의 가장 큰 장점이 아닐까 생각해 본다.
def solution(lines):
sets = [set(range(min(l), max(l))) for l in lines]
return len(sets[0] & sets[1] | sets[0] & sets[2] | sets[1] & sets[2])
4. 유한소수 판별하기
(문제 설명, 제한사항, 입출력 예)
두 정수 a와 b가 주어질 때, a/b가 유한소수이면 1을 무한소수라면 2를 반환하라는 문제이다.
유한소수의 정의와 유한소수가 되기 위한 조건은 아래와 같다.
- 유한소수의 정의 : 소수점 아래 숫자가 계속되지 않고 유한개인 소수
- 유한소수의 조건 : 기약분수로 나타내었을 때, 분모의 소인수가 2와 5만 존재해야 한다.
(내가 생각한 풀이 과정)
주어진 유한소수의 조건("기약분수로 나타내었을 때, 분모의 소인수가 2와 5만 존재해야 한다.")을 그대로 이용했다.
1. 기약분수로 만들어줘야 한다. -> 두 수(a, b)의 최대 공약수(math 모듈의 gcd() 함수 사용)를 찾아 나눠준다.
2. 분모의 소인수를 찾아줘야 한다. -> 해당 수와 나누어 떨어져야 하고, 그 수가 소수(find_prime()이라는 자체 함수를 만듦)여야 한다.
3. 소인수가 2와 5만 있는지 확인해야 한다.
(코드)
💡 내 코드
import math
def find_prime(n):
for i in range(2, n):
if n % i == 0: return False
return True
def solution(a, b):
gcd = math.gcd(a, b)
a, b = a//gcd, b//gcd
check = [num for num in range(2, b+1) if b % num == 0 and find_prime(num)]
for n in check:
if n == 2 or n == 5: continue
else: return 2
return 1
💡 다른 사람의 풀이 코드
나와 같은 풀이 방식을 가졌지만, 코드만 다르다.
최대 공약수를 찾아 -> 분모를 기약분수의 수로 만들고 -> 2와 5만 나누어 떨어지는지 확인
from math import gcd
def solution(a, b):
b //= gcd(a,b)
while b%2==0:
b//=2
while b%5==0:
b//=5
return 1 if b==1 else 2