[Programmers/Lv. 0] 코딩테스트 입문 Day 25 - 시뮬레이션, 조건문, 수학 (Python)

1. 문자열 밀기

---

(문제 설명, 제한사항, 입출력 예)

문자열 A와 B가 주어질 때, A를 밀어서 B가 될 수 있다면, 밀어야 하는 최소 횟수를 구하라는 문제이다.
만약, 밀어서 B가 될 수 없으면 -1을 반환하면 된다.

 

(내가 생각한 풀이 과정)

차례대로 조건을 세 개로 나누어서 문제를 풀었다.

첫 번째, A와 B가 같은 경우 -> 0을 반환
두 번째, A와 B를 한 칸씩 밀면서 두 문자열을 비교 -> shift의 숫자대로 밀면서 문자열을 "A[-shift:] + A[0:-shift]" 형태로 비교
세 번째, A의 길이만큼 밀었는데도 (한바퀴 돈 경우) 같은 값이 나오지 않는 경우 -> -1 반환 (될 수 없다고 판단)

 

(코드)

💡 내 코드

def solution(A, B):
    shift = 1
    if A == B: return 0

    while shift < len(A):
        if A[-shift:]+A[0:-shift] == B:
            return shift
        else: 
            shift += 1
    return -1

 

💡 다른 사람의 풀이 코드

문자열에 있는 find() 함수 자체를 이용한 방법이다.
문자열 A를 2배로 늘려두고 find() 함수를 활용해서 첫 인덱스의 위치를 얼마나 밀었는지로 판단한 좋은 풀이법이다. 
특히, find() 함수는 찾는 문자가 존재하지 않는다면 -1을 반환한다는 조건이 있기 때문에 문제에도 부합했다.

solution = lambda a, b:(b*2).find(a)

 

---

2. 종이 자르기

---

(문제 설명, 제한사항, 입출력 예)

M x N 크기의 큰 종이를 1 x 1 크기로 자르려고 할 때, 최소로 가위질해야 하는 횟수를 구하라는 문제이다.
단, 종이를 겹쳐서 자를 수는 없다.

 

(내가 생각한 풀이 과정)

순서대로 종이를 자른다 생각하면서 문제를 풀었다.

예시로 2 x 5 사이즈의 종이가 있다고 하자.
우선 2인 부분을 길게 한번 잘라줘야하니 (2-1)번 만큼의 가위질을 해주고,
2개로 나누어진 부분을 이제 각 (5-1)번씩의 가위질을 해줘야 하니 ((5-1)*2)번 만큼의 가위질을 더 해줬다고 생각하면 된다.

즉, 정리하면 2는 두 수 M, N의 최솟값, 5는 두 수 M, N의 최댓값으로 치환하면 문제를 풀 수 있다.

 

(코드)

💡 내 코드

def solution(M, N):
    return (min(M, N)-1)+((max(M, N)-1)*min(M, N))

 

💡 다른 사람의 풀이 코드

풀이 과정을 생각하기보다 수 자체의 규칙을 찾을 수도 있다.
(2, 2)일 때는 3을 반환, (2, 5)일 때는 9를 반환, (1, 1)일 때는 0을 반환... 이런 식으로 규칙을 찾으면 식을 도출할 수도 있다.

def solution(M, N):
    return (M * N) - 1

 

---

3. 연속된 수의 합

---

(문제 설명, 제한사항, 입출력 예)

두 정수 num과 total이 주어질 때, 연속된 수 num개를 더한 값이 total이 될 때, 
정수 배열을 오름차순으로 담아 구하라는 문제이다.

예를 들어 num은 3이고, total은 12일 때 -> 연속된 3개의 정수를 더해 12를 만드는 정수 배열을 오름차순으로 담아 구하라는 뜻!

 

(내가 생각한 풀이 과정)

연속된 숫자의 합 = 공차가 1인 등차수열의 합

공차 d가 1이라고 생각하고, 등차수열의 합 공식을 역으로 이용하면서 풀었다.
예제 1) num=3, total=12인 경우 : 3a + 3 = 12 (a+(a+1)+(a+2)) -> a = (12-3)/3 = 3
예제 2) num=5, total=15인 경우 : 5a + 10 = 15 (a+(a+1)+(a+2)+(a+3)+(a+4)) -> a = (15-10)/5 = 1

정리하자면, 첫째 항 a를 찾고 num 만큼 반복을 하면 배열을 찾을 수 있기 때문에 첫째 항 a를 찾는 풀이방법을 사용했다.
첫째 항 a는 "공차가 1인 등차수열의 합"을 구한다고 생각하여 풀었으며,
식은 "a = (total - 1부터 정수 num까지의 합) / num"의 형태로 도출되었다.

 

(코드)

💡 내 코드

def solution(num, total):
    return [(total-sum(range(1, num)))/num+i for i in range(num)]

 

---

4. 다음에 올 숫자

---

(문제 설명, 제한사항, 입출력 예)

등차수열 혹은 등비수열이 주어질 때, 마지막 원소 다음으로 올 숫자를 구하라는 문제이다.
등차수열 혹은 등비수열이 아닌 경우는 없다.

 

(내가 생각한 풀이 과정)

등차수열인 경우와 등비수열인 경우를 조건으로 나누어서 판별해주면 된다.

등차수열인 경우 -> 인덱스 [1]-[0]의 값과 인덱스 [2]-[1]의 값이 같은 경우 = 공차가 같은 경우
(common 배열의 길이가 3 이상이라는 조건이 있음) -> 마지막 원소의 값 + 공차 = 최종 반환 값

위의 경우가 아닌 경우 -> 등비수열인 경우로 판단! -> 마지막 원소의 값 x 공비 (인덱스 [1]/[0]의 값)

 

(코드)

💡 내 코드

def solution(common):
    if common[1]-common[0] == common[2]-common[1]:
        return common[-1]+(common[1]-common[0])
    else:
        return common[-1]*(common[1]/common[0])

 

---