2020-04-17 ~ 19 알고리즘 문제풀이 스터디
- 문제풀이 사이트: 프로그래머스
(출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges)
1. 시저 암호
문제 정의
문제 풀이
코드
def solution(s, n):
result = ""
for i in range(len(s)):
char = s[i]
if (char.isupper()):
result += chr((ord(char) + n - 65) % 26 + 65)
elif char == " ":
result += char
else:
result += chr((ord(char) + n - 97) % 26 + 97)
return result코드 with 주석
def solution(s, n):
result = ""
for i in range(len(s)):
char = s[i]
# 대문자일 경우 암호화
if (char.isupper()):
result += chr((ord(char) + n - 65) % 26 + 65)
# 빈 칸일 경우 암호화 하지 않고 문자열에 삽입
elif char == " ":
result += char
# 소문자일 경우 암호화
else:
result += chr((ord(char) + n - 97) % 26 + 97)
return result생각
문자들은 각각에 대응되는 숫자 코드가 있다는 것을 떠올렸다.
'문자 -> 숫자 코드 -> 암호화 레벨 적용 -> 문자'로 진행하면 된다는 것까진 알았다.
그러나 a~z 안에서만 순환해야 한다는 점 때문에
어떻게 접근해야 할 지 몰라 시저암호를 파이썬으로 구현한 사이트를 찾아보았다.
시저암호 - 파이썬
2. 멀쩡한 사각형
문제 정의
문제 풀이
코드
def gcd(a, b):
while b > 0:
a, b = b, a % b
return a
def solution(w, h):
n = gcd(w, h)
if n == 1:
return w*h - (w + h - 1)
height = h // n # 12 // 4
weight = w // n # 8 // 4
answer = w*h - (n * (height + weight - 1))
return answer코드 with 주석
# a, b의 최대 공약수 구하기
def gcd(a, b):
while b > 0:
a, b = b, a % b
return a
def solution(w, h):
# w, h의 최대 공약수 구하기
n = gcd(w, h)
# 만약 최대 공약수가 1이면
if n == 1:
return w*h - (w + h - 1)
height = h // n # 12 // 4
weight = w // n # 8 // 4
answer = w*h - (n * (height + weight - 1)) # 겹치는 사각형 제거
return answer생각
주어진 직사각형과 대각선을 통해 그래프로 나타낼 수 있다는 것을 몰랐다.
출처: https://leedakyeong.tistory.com/entry/프로그래머스-멀쩡한-사각형-in-python [슈퍼짱짱]
놀랍다 놀라워..
문제를 풀고 다른 사람들의 풀이를 보니
마지막 겹치는 사각형을 구하는 공식은 더 간단히 표현할 수 있다는 것을 알았다.
굳이 높이와 길이를 둘의 최대공약수로 각각 나누어 그 최소값들이 갖는 못 쓰는 사각형의 개수를 구하기 보다는,
그냥 주어진 '사각형 넓이 - (높이 + 길이 - 최대공약수)'로 표현해도 된다는 것을 알았다.
3. 체육복
문제 정의
문제 풀이
코드
def solution(n, lost, reserve):
answer = 0
lostA = [r for r in lost if r not in reserve]
reserveA = [l for l in reserve if l not in lost]
for i in range(0, len(lostA)):
if lostA[i] - 1 in reserveA:
ri = reserveA.index(lostA[i]-1)
reserveA.pop(ri)
elif lostA[i] + 1 in reserveA:
ri = reserveA.index(lostA[i]+1)
reserveA.pop(ri)
answer = n - (len(lost) - (len(reserve) - len(reserveA)))
return answer코드 with 주석
def solution(n, lost, reserve):
answer = 0
// 체육복을 도난당한 학생들 중에 여분을 갖고 온 사람이 있는지 검사.
lostA = [r for r in lost if r not in reserve]
reserveA = [l for l in reserve if l not in lost]
for i in range(0, len(lostA)):
# 도난 당한 학생에게 빌려줄 수 있는 학생이 있는지 검사.
# 있다면 빌려준 뒤, 빌려준 학생의 번호를 여분을 가진 학생 번호 목록에서 제거
if lostA[i] - 1 in reserveA:
ri = reserveA.index(lostA[i]-1)
reserveA.pop(ri)
elif lostA[i] + 1 in reserveA:
ri = reserveA.index(lostA[i]+1)
reserveA.pop(ri)
# 체육활동을 할 수 있는 사람의 수 구하기.
answer = n - (len(lost) - (len(reserve) - len(reserveA)))
return answer생각
처음엔 헤맸다. 막상 생각해보니 복잡하게 풀 필요가 없는 문제였다.
처음에 도난 학생 목록과 여분을 가져온 학생 목록을 체크하는 곳에서 런타임 에러를 많이 냈다.
여분을 가져온 학생 목록을 for문 - range로 순회하면서 두 목록에서 일치하는 값을 지웠는데,
리스트의 인덱스는 그만큼 줄어들게 되니 for문에서 없는 index를 조회하면서 생기는 오류였다.
이 부분을 굉장히 의식하며 코딩하게 하는 시간이 됐다. 좋은 기회.
런타임 에러를 피하고자 코드가 더러워지니, 다른 사람의 풀이를 참조하여 한 줄 for문으로 바꿨다.
한 줄로 표현하는 for문은 내겐 생소하다. 하지만 코드를 굉장히 간단하게 표현할 수 있다는 장점이 있다. 익숙해져야겠다.
파이썬의 list 내장 함수들에도 각각의 시간 복잡도를 생각해보는 계기가 됐다.
list.remove()의 경우 시간 복잡도는 O(n)이다.
list.pop()의 경우 O(1)이다.
처음에는 remove() 함수로 구현을 했다가 pop()으로 변경했다.
