2020-04-20 알고리즘 문제풀이 스터디
문제풀이 사이트: 프로그래머스
(출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges)
def exam_paper(lenA, su):
# len of pattern
lenP = len(su)
if lenA < lenP:
su = su[:lenA]
lenP = len(su)
loopCnt = lenA // lenP
restCnt = lenA % lenP
paper = []
for i in range(0, loopCnt):
paper += su
if len(paper) < lenA:
paper += su[:restCnt]
return paper
def solution(answers):
lenA = len(answers)
su = {}
su[1] = [1, 2, 3, 4, 5]
su[2] = [2, 1, 2, 3, 2, 4, 2, 5]
su[3] = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]
suCorrec = {}
paper1 = exam_paper(lenA, su[1])
suCorrec[1] = 0
paper2 = exam_paper(lenA, su[2])
suCorrec[2] = 0
paper3 = exam_paper(lenA, su[3])
suCorrec[3] = 0
for i in range(0, lenA):
if answers[i] == paper1[i]:
suCorrec[1] += 1
if answers[i] == paper2[i]:
suCorrec[2] += 1
if answers[i] == paper3[i]:
suCorrec[3] += 1
answer = sorted(suCorrec.items(), key=(lambda suCorrec: suCorrec[1]), reverse=True)
maxn = answer[0][1]
result = []
for key, value in answer:
if maxn == value:
result.append(key)
return result
# 정답지의 길이에 맞춰 각 수포자들의 답안지를 작성한다.
def exam_paper(lenA, su):
# len of pattern
lenP = len(su)
# 만약 정답지의 길이가 수포자들 패턴 길이보다 짧다면
if lenA < lenP:
su = su[:lenA]
lenP = len(su)
loopCnt = lenA // lenP
restCnt = lenA % lenP
paper = []
for i in range(0, loopCnt):
paper += su
if len(paper) < lenA:
paper += su[:restCnt]
return paper
def solution(answers):
lenA = len(answers)
# 각 수포자들의 패턴
su = {]
su[1] = [1, 2, 3, 4, 5]
su[2] = [2, 1, 2, 3, 2, 4, 2, 5]
su[3] = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]
suCorrec = {}
# 1번 수포자의 패턴대로 검색
paper1 = exam_paper(lenA, su[1])
suCorrec[1] = 0
# 2번 수포자의 패턴대로 검색
paper2 = exam_paper(lenA, su[2])
suCorrec[2] = 0
# 3번 수포자의 패턴대로 검색
paper3 = exam_paper(lenA, su[3])
suCorrec[3] = 0
for i in range(0, lenA):
if answers[i] == paper1[i]:
suCorrec[1] += 1
if answers[i] == paper2[i]:
suCorrec[2] += 1
if answers[i] == paper3[i]:
suCorrec[3] += 1
answer = sorted(suCorrec.items(), key=(lambda suCorrec: suCorrec[1]), reverse=True)
maxn = answer[0][1]
result = []
for key, value in answer:
if maxn == value:
result.append(key)
return result
문제 자체의 난이도 보다는 파이썬에 대한 미숙으로 한참 헤맸다.
특히 마지막 정렬 로직 부분. value를 기준으로 정렬해야 하는데 key를 기준으로 정렬하다 보니 계속 에러가 났다. 파이썬의 정렬 함수에 익숙해지는 좋은 계기가 됐다.
def isRight(p):
if p == '':
return p
stack = []
for i, c in enumerate(p):
if c == '(':
stack.append(i)
elif c == ')':
if not stack:
return False
stack.pop()
if stack:
return False
return True
def separate(p):
count = 0
for i, v in enumerate(p):
if v == ')':
count -= 1
elif v == '(':
count += 1
if count == 0:
return i
def solution(p):
if p == '' or isRight(p):
return p
u, v = p[:separate(p)+1], p[separate(p)+1:]
if isRight(u):
return u + solution(v)
else:
temp = '('
temp += solution(v)
temp += ')'
u = u[1:-1]
utemp = ''
for c in u:
if c == '(':
utemp += ')'
elif c == ')':
utemp += '('
temp += utemp
return temp
# 올바른 괄호 문자열인지 검사
def isRight(p):
if p == '':
return p
stack = []
for i, c in enumerate(p):
if c == '(':
stack.append(i)
elif c == ')':
if not stack:
return False
stack.pop()
if stack:
return False
return True
# p를 u, v로 분리
def separate(p):
count = 0
for i, v in enumerate(p):
if v == ')':
count -= 1
elif v == '(':
count += 1
if count == 0:
return i
def solution(p):
if p == '' or isRight(p):
return p
u, v = p[:separate(p)+1], p[separate(p)+1:]
if isRight(u):
return u + solution(v)
else:
temp = '('
temp += solution(v)
temp += ')'
u = u[1:-1]
utemp = ''
for c in u:
if c == '(':
utemp += ')'
elif c == ')':
utemp += '('
temp += utemp
return temp
올바른 괄호 문자열을 검사하는 로직을 짜는 것부터 헤맸다. 스택의 개념을 이렇게 쓸 수도 있구나! 라고 생각하게 한 문제였다.
다른 블로거들이 이 문제에 대해 공통적으로 하는 말이 '문제 설명만 잘 따라가면 풀 수 있는 문제'였다.
처음엔 문제 이해가 어려웠지만, 문제를 이해하고 나니 그 말 대로였다. 또 배웠다 ㅎㅎ