728x90
반응형
코딩 테스트 문제풀이의 목표
- 코딩 테스트 문제풀이를 하며 알고리즘에 대한 이해도를 높힌다
- 팀원들과 코드 리뷰를 하며 해당 코드를 짠 구체적인 이유를 제시한다
- https://github.com/raoneli1013/codingtest
문제 1 : https://school.programmers.co.kr/learn/courses/30/lessons/132267
# https://school.programmers.co.kr/learn/courses/30/lessons/132267
# 콜라 문제
# 문제 설명
# 오래전 유행했던 콜라 문제가 있습니다. 콜라 문제의 지문은 다음과 같습니다.
# 정답은 아무에게도 말하지 마세요.
# 콜라 빈 병 2개를 가져다주면 콜라 1병을 주는 마트가 있다.
# 빈 병 20개를 가져다주면 몇 병을 받을 수 있는가?
# 단, 보유 중인 빈 병이 2개 미만이면, 콜라를 받을 수 없다.
# 문제를 풀던 상빈이는 콜라 문제의 완벽한 해답을 찾았습니다.
# 상빈이가 푼 방법은 아래 그림과 같습니다. 우선 콜라 빈 병 20병을 가져가서
# 10병을 받습니다. 받은 10병을 모두 마신 뒤, 가져가서 5병을 받습니다.
# 5병 중 4병을 모두 마신 뒤 가져가서 2병을 받고, 또 2병을 모두 마신 뒤 가져가서
# 1병을 받습니다. 받은 1병과 5병을 받았을 때 남은 1병을 모두 마신 뒤 가져가면
# 1병을 또 받을 수 있습니다. 이 경우 상빈이는 총 10 + 5 + 2 + 1 + 1 = 19병의
# 콜라를 받을 수 있습니다.
# 콜라를 받기 위해 마트에 주어야 하는 병 수 a, 빈 병 a개를 가져다 주면
# 마트가 주는 콜라 병 수 b, 상빈이가 가지고 있는 빈 병의 개수 n이
# 매개변수로 주어집니다. 상빈이가 받을 수 있는 콜라의 병 수를
# return 하도록 solution 함수를 작성해주세요.
# 제한사항
# 1 ≤ b < a ≤ n ≤ 1,000,000
# 정답은 항상 int 범위를 넘지 않게 주어집니다.
a = 3
b = 2
n = 20
answer = 0
while n>=a:
answer += (n//a)*b
n = (n//a)*b + n%a
print (answer)
# 반복문으로 풀기
def solution(a, b, n):
answer = 0
while n>=a:
answer += (n//a)*b
n = (n//a)*b + n%a
return answer
# 일반화
# n병에서 처음 a병을 가져다주면 b병을 받음
# 재귀함수로 풀기
def bottle(n, a, b, sum=0):
if n < a: return sum
return bottle((n%a)+(n//a)*b, a, b, sum+(n//a)*b)
# 조금 더 일반화
# n - (a - b)*k < a 를 만족하는 k의 최소값을 구하면 됌
# k는 교환 횟수, k*b가 받는 총 병 수가 된다
# 정리하면
# k > (n-a)/(a-b) 를 만족하는 k의 최소값
# k = (n-a)//(a-b) + 1 이 됌
k = int((n-a)/(a-b)) + 1
answer = k*b
print(answer)
# 제출용 함수
def solution2(a, b, n):
k = int((n-a)/(a-b)) + 1
answer = k*b
return answer
문제 2 : https://school.programmers.co.kr/learn/courses/30/lessons/131705
# https://school.programmers.co.kr/learn/courses/30/lessons/131705
# 삼총사
# 문제 설명
# 한국중학교에 다니는 학생들은 각자 정수 번호를 갖고 있습니다.
# 이 학교 학생 3명의 정수 번호를 더했을 때 0이 되면 3명의 학생은 삼총사라고 합니다.
# 예를 들어, 5명의 학생이 있고, 각각의 정수 번호가 순서대로 -2, 3, 0, 2, -5일 때,
# 첫 번째, 세 번째, 네 번째 학생의 정수 번호를 더하면 0이므로
# 세 학생은 삼총사입니다. 또한, 두 번째, 네 번째, 다섯 번째 학생의 정수 번호를
# 더해도 0이므로 세 학생도 삼총사입니다. 따라서 이 경우 한국중학교에서는 두 가지
# 방법으로 삼총사를 만들 수 있습니다.
# 한국중학교 학생들의 번호를 나타내는 정수 배열 number가 매개변수로 주어질 때,
# 학생들 중 삼총사를 만들 수 있는 방법의 수를 return 하도록
# solution 함수를 완성하세요.
# 제한사항
# 3 ≤ number의 길이 ≤ 13
# -1,000 ≤ number의 각 원소 ≤ 1,000
# 서로 다른 학생의 정수 번호가 같을 수 있습니다.
number = [-2, 3, 0, 2, -5]
answer = 0
# itertools의 combinations로 3명 조합을 구하고
from itertools import combinations
for i in combinations(number, 3):
# 각 조합의 합이 0이면 answer +1 씩 해주면 될 듯
if sum(i) == 0 : answer+=1
print(answer)
# 제출용 함수
from itertools import combinations
def solution(number):
answer = 0
for i in combinations(number, 3):
if sum(i) == 0 : answer+=1
return answer
# 근데 솔직히 itertools쓰면 노잼임
# 그냥 한번 풀어보자
# 3명 combinations(조합)을 구하는 방법은 의외로 쉽다
# 대신 노가다가 있을 뿐
arr = []
for i in range(len(number)-2):
for j in range(i+1,len(number)-1):
for k in range(j+1,len(number)):
# number[i],number[j],number[k]가 이제 3명 combinations가 된다
# 이걸 모두 더했을 때 0 이 되면 answer +1
if number[i]+number[j]+number[k] == 0: answer +=1
print(answer)
# 제출용 함수2
def solution(number):
answer = 0
for i in range(len(number)-2):
for j in range(i+1,len(number)-1):
for k in range(j+1,len(number)):
if number[i]+number[j]+number[k] == 0: answer +=1
return answer
문제 3 : https://school.programmers.co.kr/learn/courses/30/lessons/140108
# https://school.programmers.co.kr/learn/courses/30/lessons/140108
# 문자열 나누기
# 문제 설명
# 먼저 첫 글자를 읽습니다. 이 글자를 x라고 합시다.
# 이제 이 문자열을 왼쪽에서 오른쪽으로 읽어나가면서,
# x와 x가 아닌 다른 글자들이 나온 횟수를 각각 셉니다.
# 처음으로 두 횟수가 같아지는 순간 멈추고, 지금까지 읽은 문자열을 분리합니다.
# s에서 분리한 문자열을 빼고 남은 부분에 대해서 이 과정을 반복합니다.
# 남은 부분이 없다면 종료합니다.
# 만약 두 횟수가 다른 상태에서 더 이상 읽을 글자가 없다면,
# 역시 지금까지 읽은 문자열을 분리하고, 종료합니다.
# 문자열 s가 매개변수로 주어질 때, 위 과정과 같이 문자열들로 분해하고,
# 분해한 문자열의 개수를 return 하는 함수 solution을 완성하세요.
# 제한사항
# 1 ≤ s의 길이 ≤ 10,000
# s는 영어 소문자로만 이루어져 있습니다.
s = "aaabbaccccabba"
# result = 3
i = 0
answer = 0
while len(s)>i:
if len(s[:i+1])==s[:i+1].count(s[0])*2:
answer+=1
s = s[i+1:]
i = 0
i += 1
if s: answer+=1
print(answer)
# 제출용 함수
def solution(s):
i = 0
answer = 0
while len(s)>i:
if len(s[:i+1])==s[:i+1].count(s[0])*2:
answer+=1
s = s[i+1:]
i = 0
i += 1
if s: answer+=1
return answer
문제 4 : https://school.programmers.co.kr/learn/courses/30/lessons/72410
# https://school.programmers.co.kr/learn/courses/30/lessons/72410
# 신규 아이디 추천
# 문제 설명
# 다음은 카카오 아이디의 규칙입니다.
# 아이디의 길이는 3자 이상 15자 이하여야 합니다.
# 아이디는 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.) 문자만 사용할 수 있습니다.
# 단, 마침표(.)는 처음과 끝에 사용할 수 없으며 또한 연속으로 사용할 수 없습니다.
# "네오"는 다음과 같이 7단계의 순차적인 처리 과정을 통해 신규 유저가 입력한 아이디가 카카오 아이디 규칙에 맞는 지 검사하고 규칙에 맞지 않은 경우 규칙에 맞는 새로운 아이디를 추천해 주려고 합니다.
# 신규 유저가 입력한 아이디가 new_id 라고 한다면,
# 1단계 new_id의 모든 대문자를 대응되는 소문자로 치환합니다.
# 2단계 new_id에서 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.)를 제외한 모든 문자를 제거합니다.
# 3단계 new_id에서 마침표(.)가 2번 이상 연속된 부분을 하나의 마침표(.)로 치환합니다.
# 4단계 new_id에서 마침표(.)가 처음이나 끝에 위치한다면 제거합니다.
# 5단계 new_id가 빈 문자열이라면, new_id에 "a"를 대입합니다.
# 6단계 new_id의 길이가 16자 이상이면, new_id의 첫 15개의 문자를 제외한 나머지 문자들을 모두 제거합니다.
# 만약 제거 후 마침표(.)가 new_id의 끝에 위치한다면 끝에 위치한 마침표(.) 문자를 제거합니다.
# 7단계 new_id의 길이가 2자 이하라면, new_id의 마지막 문자를 new_id의 길이가 3이 될 때까지 반복해서 끝에 붙입니다.
new_id = "abcdefghijklmn.p"
# result = "bat.y.abcdefghi"
# 1단계
new_id = new_id.lower()
# 2단계
id = ''
for i in new_id:
if i.isalpha() or i.isdigit() or i in ['-','_','.']:
id += i
# 3단계
while True:
id_org = id
id = id.replace('..','.')
if id == id_org : break
# 4단계
id = id.strip('.')
# 5단계
if not id: id+='a'
# 6단계
if len(id)>=16:
id = id[:15].rstrip('.')
# 7단계
if len(id)<=2:
id = id+id[-1]*(3-len(id))
answer = id
print(answer)
# 제출용 함수
def solution(new_id):
new_id = new_id.lower()
id = ''
for i in new_id:
if i.isalpha() or i.isdigit() or i in ['-','_','.']:
id += i
while True:
id_org = id
id = id.replace('..','.')
if id == id_org : break
id = id.strip('.')
if not id: id+='a'
if len(id)>=16:
id = id[:15].rstrip('.')
if len(id)<=2:
id = id+id[-1]*(3-len(id))
answer = id
return answer
728x90
반응형
