def solution(board, moves):
answer = 0
crab_lst = []
for m in moves:
for i in range(len(board)):
if board[i][m-1] != 0:
crab_lst.append(board[i][m-1])
board[i][m-1] = 0 # 인형을 뽑았으니 0으로 처리
# 뽑은 인형이 2개 이상일 때만 터짐 발생
if len(crab_lst) > 1:
if crab_lst[-1] == crab_lst[-2]: # last 2개가 같으면
crab_lst.pop()
crab_lst.pop()
answer += 2
break # 한 번 뽑았다면 다음 move로 넘어가야 함
return answer
먼저 우리가 몇 번째 위치에서 인형을 집을지 저장해 둔 moves에서 for문을 진행합니다.
주의해야 할 점은, moves는 n번 위치를 나타내기 때문에 실제로 우리가 board 배열에서 해당 위치를 찾을 때는 -1 해줘야 한다는 점입니다. (list에서는 첫 번째가 index 기준 0이므로)
다음으로는 board의 길이 만큼 for문을 진행하게 되는데, 이는 moves에서 지정된 위치에서 board의 맨 위부터 내려가면서 인형이 있는 위치를 찾아가는 것이라고 생각해 주시면 됩니다.
그래서 if board[i][m-1] != 0이 나오게 됩니다. 즉, 0이 아닌 경우(인형이 있는 경우)에 도달하면 if문에 걸리게 되는 것이죠.
인형이 있으면, 이를 뽑힌 인형이 저장되는 crab_lst에 저장해 주고, 인형이 뽑혔으므로 해당 위치는 인형이 없어지게 되니 이 자리를 0으로 채워줍니다.
그리고 문제에서 만약 뽑힌 인형이 동일한 두개가 연달아 있으면 인형이 사라진다고 했으므로, crab_lst가 2 이상은 되어야 인형이 터지는 일이 발생합니다. 이를 반영해 if len(crab_lst) > 1 : 의 조건을 걸어줍니다.
list이므로 가장 마지막과 마지막에서 두 번째는 [-1]와 [-2]로 index 접근이 가능하며, 둘이 같으면 pop으로 빼주고 answer에 2를 더해줍니다.
그리고 break를 꼭 해줘야 하는데, 이는 해당 번째 위치에서 인형은 한 번만 뽑기 때문입니다. 해당 break가 없으면 moves에 해당하는 m 번째 위치에서 인형을 계속 뽑게 됩니다.
def distance(start, end):
mat = [["1", "2", "3"],
["4", "5", "6"],
["7", "8", "9"],
["*", "0", "#"]]
start_loc = []
end_loc = []
dist = 0
for idx, r in enumerate(mat):
if str(start) in r:
start_loc.append(idx)
start_loc.append(r.index(str(start)))
if str(end) in r:
end_loc.append(idx)
end_loc.append(r.index(str(end)))
dist = abs(end_loc[0]-start_loc[0]) + abs(end_loc[1]-start_loc[1])
return dist
def solution(numbers, hand):
answer = ''
left_list = ["1", "4", "7"]
right_list = ["3", "6", "9"]
center_list = ["2", "5", "8", "0"]
r_loc = "#"
l_loc = "*"
for idx, num in enumerate(numbers):
if str(num) in left_list:
answer += "L"
l_loc = str(num)
elif str(num) in right_list:
answer += "R"
r_loc = str(num)
else: # center에 해당하는 경우
dist_l = distance(l_loc, num)
dist_r = distance(r_loc, num)
if dist_l < dist_r:
answer += "L"
l_loc = str(num)
elif dist_l > dist_r:
answer += "R"
r_loc = str(num)
else:
if hand == 'left':
answer += "L"
l_loc = str(num)
else:
answer += "R"
r_loc = str(num)
return answer
문제에서 정의하기로는 좌측에 위치한 1, 4, 7인 경우는 무조건 왼손으로, 3 6 9인 경우는 무조건 오른손으로 타이핑하면 된다고 했기 때문에, 이런 경우는 단순히 if문을 통해서 해결하면 됩니다.
이때, answer만 갱신하는 것이 아니라, 왼손과 오른손의 위치 또한 갱신해주어야 합니다.
2, 5, 8, 0의 경우는 오른손과 왼손 중 가까운 손을 사용해야 하기 때문입니다.
만약 왼손이나 오른손으로 확정되지 않는, 2, 5, 8, 0의 경우는 거리를 계산해야 하는데요.
이 부분은 별도로 distance라는 함수로 빼서 정의하였습니다.
def distance(start, end):
mat = [["1", "2", "3"],
["4", "5", "6"],
["7", "8", "9"],
["*", "0", "#"]]
start_loc = []
end_loc = []
dist = 0
for idx, r in enumerate(mat):
if str(start) in r:
start_loc.append(idx)
start_loc.append(r.index(str(start)))
if str(end) in r:
end_loc.append(idx)
end_loc.append(r.index(str(end)))
dist = abs(end_loc[0]-start_loc[0]) + abs(end_loc[1]-start_loc[1])
return dist
해당 함수는 start 지점부터 end 지점까지의 거리를 계산해 주는 함수입니다.
먼저 키패드에 해당하는 matrix를 문자열로 정의하였습니다. *와 #이 존재하므로, 일괄적으로 문자열로 정의하는 게 낫다고 판단했습니다.
그리고 matrix를 row 단위로 돌면서, 해당 row에 start나 end가 있으면 해당 위치를 (x, y)의 형태로 저장하도록 했습니다.
마지막으로는 |x1-x0| + |y1-y0|을 계산해서 return 하도록 했습니다.
어차피 한 칸을 이동하는게 1로 계산되고, 별도의 제약이 없기 때문에 이렇게 계산해도 충분하다고 판단했습니다.
일반적인 distance를 계산하는 방식처럼 루트를 사용하거나 하지 않기 때문에, 1칸씩 격자로 이동하기 때문이죠.
이 distance라는 함수를 활용해서 start를 왼손 위치로 잡고, end는 우리가 쳐야 하는 숫자로 입력하면 왼손 기준의 거리를 계산할 수 있고, start를 오른손 위치로 잡고, end를 우리가 쳐야 하는 숫자로 입력하면 오른손 기준의 거리를 계산할 수 있습니다.
이 둘 간의 거리를 바탕으로 왼손과 오른손을 결정하면 됩니다.
문제에 나와 있듯이, 만약 두 거리가 같을 경우는 왼손잡이인지 오른손잡이인지만 판단해서 결정해 주면 되겠죠.
사실상 문제 자체가 어려운 케이스는 아닌데, 2, 5, 8, 0인 경우에 각각 왼손, 오른손으로 부터 해당 키패드까지의 거리를 구하는 코드만 잘 짜면 되는 문제라고 보입니다.
def solution(number, limit, power):
# number : 기사단원의 수
# limit: 공격력 제한 수치
# power: 제한 수치를 초과한 기사가 사용할 무기
answer = 0
num_lst = []
# 약수 개수 구하기
for n in range(1, number + 1):
prime_num = []
for i in range(1, int((n**0.5) + 1)):
if n % i == 0:
prime_num.append(i) # 앞쪽
if i != n // i:
prime_num.append(n // i) # 뒤쪽
num_lst.append(len(prime_num)) # 약수 개수 정리
# 약수 개수 모아놓고 limit 넘으면 교체
for idx, p in enumerate(num_lst):
if p > limit:
num_lst[idx] = power
return sum(num_lst)
약수를 구할 때, 1부터 n까지 다 따지면서 나눠지는지 여부를 확인하는 것이 소수의 원리에 맞는 방법입니다.
하지만, 코딩테스트에서 다루는 문제들은 대부분 시간복잡도 문제가 있어 이를 그대로 다 계산하면 시간복잡도 제한에 걸리게 됩니다.
위 문제도 당연히 시간복잡도 이슈에 직면하게 됩니다.
하나의 수는 보통 약수의 짝이 존재합니다.
예를 들어, 8의 약수를 구한다고 한다면 1, 2, 4, 8가 되는데, 1과 8 / 2와 4는 각각 짝으로 생각할 수 있습니다.
따라서, 약수를 구할 때 1부터 8까지 모두 따지는 것보다 짝이 있다는 개념을 활용해서 이를 조금 더 빠르게 판단할 수 있습니다.
그래서 보통 사용하는 방법은, 구하려고 하는 수의 제곱근을 계산하여 제곱근 까지만 계산해 보는 방법입니다.
제곱근이 직관적인 16을 예시로 들겠습니다.
16의 약수는 1, 2, 4, 8, 16입니다. 위에서 설명드린 바와 같이, 1과 16 / 2와 8은 짝입니다. 4는 4와 짝이지만 같은 수 이므로 한 번만 카운팅 하게 되지요.
이처럼 어떤 수의 약수를 생각할 때는, 어떤 수의 제곱근 까지만 생각하면 모든 약수를 구할 수 있다는 것입니다.
이를 코드로 구현한 부분이 이것입니다.
for i in range(1, int((n**0.5) + 1)):
if n % i == 0:
prime_num.append(i) # 앞쪽
if i != n // i:
prime_num.append(n // i) # 뒤쪽
우리가 구하려는 수는 n이고, n의 제곱근 까지만 반복문을 진행한다는 사실을 알 수 있습니다.
n이 i로 나눠지면, 이를 prime_num이라는 list에 저장합니다.
그리고 이 경우에, 만약 i가 n을 i로 나눈 몫과 같지 않으면, n을 i로 나눈 몫을 소수로 추가합니다.
이를 16을 예시로 들어 설명 드리겠습니다.
for i in range(1, 4+1) 이 될 것이고, 첫 번째로 16이 1로 나눠지는지를 검토합니다. 이때 나눠지므로, 소수로 인정합니다.
그리고 1이 16을 1로 나눴을 때의 값과 다른지 확인합니다. 이 때는 다르므로, 16을 1로 나눈 16도 소수로 인정합니다.
두 번째로 16이 2로 나눠지는지를 검토합니다. 이 때 나눠지므로, 소수로 인정합니다.
그리고 2가 16을 2로 나눴을 때의 값(8)과 다른지 확인, 다르므로 8도 소수로 인정합니다.
세 번째로 16이 3으로 나눠지는지를 검토합니다. 안되므로 넘어갑니다.
네 번째로 16이 4로 나눠지는지를 검토합니다. 이 때 나눠지므로, 소수로 인정합니다.
그리고 4가 16을 4로 나눴을 때의 값과 다른지 확인합니다. 이 때는 같기 때문에 소수에 추가하지 않습니다.
if i != n // i를 하는 이유를 4의 케이스를 생각해 보시면 이해가 빠를 것 같습니다.
문제에서 일단 약수의 개수를 list로 만들어주고, limit보다 큰 경우는 power라고 하는 변수 값으로 바꿔준 다음 sum 해주면 문제 풀이는 끝이 납니다.
사실상 시간 복잡도의 제약에 걸리지 않고 소수의 개수를 구할 수 있는지가 관건인 문제라고 보시면 됩니다.
def solution(n, m, section):
answer = 0
while section: # section이 남은 경우만 반복
start_point = section[0] # 출발 지점
# 출발 지점에서 m만큼 갔는데 이게 n을 넘기는 경우
if start_point + (m-1) > n:
start_point -= (start_point + (m-1)) - n # 넘친 만큼 빼줌
# m만큼 진행하기
for i in range(m):
arrival = start_point + i
if arrival in section:
section.remove(arrival) # 있으면 제거
answer += 1
return answer
일단 section이 남은 경우에만 계속 진행하면 되기 때문에, while에서 section의 길이를 받아 1보다 클 때만 반복문이 진행되도록 하였습니다.
그 후, section은 오름차순 정렬 되어 있으므로, 첫 번째 요소를 start_point로 잡았습니다.
단, start_point에서 m만큼 갔을 때 이것이 n을 넘는 경우가 발생할 수 있습니다.
이런 경우 if 문으로 따로 빼서, start_point의 값을 조정해 주는 작업을 진행하였습니다.
예를 들어, n이 3이고 m이 3이면서 section이 [2]라면, start_point가 2로 잡힐 것이고, 여기서 3칸을 칠하게 되면 2, 3, 4의 3 칸을 칠해야 하는 상황이 되므로 n을 넘게 됩니다.
그래서, 넘친 만큼인 1 만큼을 빼줘서 start_point를 1로 조정하고, 여기서 3칸을 칠하게 만들면 됩니다.
다음으로는, m만큼 칠해야 하니 반복문을 통해서 진행해 주고, 도착지점을 arrival로 저장, 만약 arrival이 section에 있다면 이를 remove 해주는 방식으로 진행하였습니다.
하지만, 약 6개 정도의 test case에서 시간 에러가 나는 문제가 발생했습니다.
그래서 어떤 부분이 문제일까.. 하고 고민해 보니 arrival이 section에 있는지 판단하는 in이 문제가 될 수 있겠다고 판단했습니다.
왜냐하면 in의 경우 list 안의 위치를 찾아야 하는데, 만약 section이 매우 크다면 한번 작업에 많은 연산을 요구하게 됩니다.
문제에서 1 <= section의 길이 <= n로 되어 있는데, n이 최대 10만이 가능하니 remove 연산은 10만 개짜리 list에서 하나를 찾는 작업을 계속해서 반복해야 합니다.
따라서 이 부분을 개선하는 방향으로 고민하였습니다.
개선된 풀이:
def solution(n, m, section):
answer = 0
while section: # section이 남은 경우만 반복
start_point = section[0] # 출발 지점
# 출발 지점에서 m만큼 갔는데 이게 n을 넘기는 경우
if start_point + (m-1) > n:
start_point -= (start_point + (m-1)) - n # 넘친 만큼 빼줌
target_section = section[:m] # section에서 최대한 지워져도 m개 까지만 가능하니까.
# target_section에서 m개 범위 안에 들면 제거
for tar in target_section:
if start_point <= tar <= start_point + m - 1:
section.remove(tar)
answer += 1
return answer
일단 모든 section을 다 돌지 않아야 한다는 게 이전 풀이에서의 교훈이기 때문에, 그럼 과연 section을 다 돌지 않으려면 어떻게 해야 하는가 를 고민했습니다.
start_point 지점 기준으로 결국 m개만 칠하게 되는 것이고, 이는 결국 section에서 m개만 검토하면 된다는 결론이 나옵니다. 왜냐면 section은 이미 오름차순 정렬이 되어 있기 때문에, m개보다 더 많은 양은 검토할 필요가 없습니다.
따라서 지울지 말지 검토해야 하는 section을 target_section으로 만들고, m개만 뽑아냈습니다.
section[:m]으로 하게 되면, 혹시라도 section이 m개 보다 작더라도 에러가 나지 않습니다.
그리고 target_section에 있는 각각 요소들을 start_point 기준으로 m개 색칠하는 범위 내에 들어가 있는지를 판단해서 제거해 주는 방식으로 진행했습니다.
def solution(dartResult):
answer = 0
num = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
s_ = [] # score 저장
b_ = [] # 보너스 저장
o_ = [] # 옵션 저장
# 문자열이 존재하는 경우 while문
while dartResult:
# 숫자 관련
if len(dartResult) >= 2 and str(dartResult[:2]) == '10':
s_.append(10); dartResult = dartResult[2:] # 첫 번째 숫자 10으로 빼고 문자열 밀기
elif int(dartResult[0]) in num:
s_.append(int(dartResult[0])); dartResult = dartResult[1:]
# 보너스 관련
if str(dartResult[0]) == 'S':
b_.append('S')
elif str(dartResult[0]) == 'D':
b_.append('D')
elif str(dartResult[0]) == 'T':
b_.append('T')
dartResult = dartResult[1:] # 얘는 공통이라
# 옵션 관련
if len(dartResult) >= 1 and str(dartResult[0]) == '*':
o_.append('*')
dartResult = dartResult[1:]
elif len(dartResult) >= 1 and str(dartResult[0]) == '#':
o_.append('#')
dartResult = dartResult[1:]
else:
o_.append(" ")
sol_ = []
for i in range(3):
# 제곱 작업 우선 진행
if b_[i] == 'S':
sol_.append(s_[i] ** 1)
elif b_[i] == 'D':
sol_.append(s_[i] ** 2)
elif b_[i] == 'T':
sol_.append(s_[i] ** 3)
for i in range(3):
# 아무것도 없는 경우, 아무 작업 안함
if o_[i] == " ":
continue
# 첫 번째 나오고 스타상인 경우
if o_[i] == '*' and i == 0:
sol_[i] = sol_[i] * 2
elif o_[i] == '*' and i != 0:
sol_[i-1] = sol_[i-1] * 2 # 전에 얻은 점수 2배
sol_[i] = sol_[i] * 2 # 해당 점수 2배
# 아차상
if o_[i] == '#':
sol_[i] = sol_[i] * -1
return sum(sol_)
딱 봐도 문제 풀이 자체가 매우 긴 것을 확인하실 수 있습니다.
정직하게 문제에 나온 그대로를 코드로 구현한 것이라고 볼 수 있는데요.
score와 보너스, 옵션을 저장할 list를 별도로 지정하고 문자열에 대해서 while문을 돌면서 이 문자열을 score와 보너스, 옵션으로 분해하는 작업을 우선적으로 진행합니다.
먼저 숫자 관련 부분을 보시면,
while dartResult:
# 숫자 관련
if len(dartResult) >= 2 and str(dartResult[:2]) == '10':
s_.append(10); dartResult = dartResult[2:] # 첫 번째 숫자 10으로 빼고 문자열 밀기
elif int(dartResult[0]) in num:
s_.append(int(dartResult[0])); dartResult = dartResult[1:]
문자열의 길이가 2 이상이고(해당 조건 없으면 dartResult [:2]에서 index 에러가 발생합니다), 앞에 두 글자가 10인 경우는 score 부분을 10으로 append 하고, 문자열을 밀어줍니다.
10이 아닌 0부터 9인 경우는 in num으로 조건을 걸어서 숫자를 빼는 식으로 진행했습니다.
보너스 관련해서는 그다음 문자열이 S D T 중 하나이면 이를 보너스 관련 list에 추가해 주고, 문자열을 하나 밀었습니다.
S D T 중 뭐든 간에 1칸을 밀어주니 if 문에 넣지 않고 if문 바깥쪽에 미는 코드를 위치했습니다.
# 옵션 관련
if len(dartResult) >= 1 and str(dartResult[0]) == '*':
o_.append('*')
dartResult = dartResult[1:]
elif len(dartResult) >= 1 and str(dartResult[0]) == '#':
o_.append('#')
dartResult = dartResult[1:]
else:
o_.append(" ")
옵션 관련해서는 * 이거나 #인 경우 이를 옵션 관련 list에 추가하도록 했습니다.
len을 점검하는 코드가 있는 이유는, 옵션은 선택사항이라 옵션 자체가 아예 없는 경우가 있습니다. 이럴 때는 dartResult에 문자열 자체가 안 남아버려서 dartResult [0]로 접근이 안되고 index 에러가 발생합니다. 따라서 이를 방지하고자 문자열이 1개 이상 남은 경우에만 뽑아내도록 했습니다.
sol_ = []
for i in range(3):
# 제곱 작업 우선 진행
if b_[i] == 'S':
sol_.append(s_[i] ** 1)
elif b_[i] == 'D':
sol_.append(s_[i] ** 2)
elif b_[i] == 'T':
sol_.append(s_[i] ** 3)
그다음 부분은 먼저 제곱 작업을 우선적으로 진행해서, 값들을 sol_에 추가했습니다.
for i in range(3):
# 아무것도 없는 경우, 아무 작업 안함
if o_[i] == " ":
continue
# 첫 번째 나오고 스타상인 경우
if o_[i] == '*' and i == 0:
sol_[i] = sol_[i] * 2
elif o_[i] == '*' and i != 0:
sol_[i-1] = sol_[i-1] * 2 # 전에 얻은 점수 2배
sol_[i] = sol_[i] * 2 # 해당 점수 2배
# 아차상
if o_[i] == '#':
sol_[i] = sol_[i] * -1
return sum(sol_)
옵션에 별도로 없는 경우는 아무 작업 안 하고 continue로 넘어가도록 하였고,
*이 첫 번째 나오는 경우는 자기 자신의 값만 2배, *이 첫 번째가 아닌 곳에 나오는 경우는 전에 얻은 점수와 지금 점수를 모두 2배 하도록 했습니다.
그리고 #이 나오는 경우는 -1을 곱해주도록 했고, 마지막에는 sum 해서 결과가 나오도록 했습니다.
어떻게 보면 문제에 나온 내용을 말 그대로 충실히 진행해서 나온 코드라고 보시면 될 것 같습니다.
하지만 코드 수가 길고, 효율적이지는 못해서 더 효율적인 코드가 필요합니다.
개선된 코드:
import re
def solution(dartResult):
bonus = {'S' : 1, 'D' : 2, 'T' : 3}
option = {'' : 1, '*' : 2, '#' : -1}
p = re.compile('([0-9]+)([SDT])([*#]?)')
dart = p.findall(dartResult)
for i in range(len(dart)):
if dart[i][2] == '*' and i > 0: # i가 0보다 클때는 전에꺼 2배 해줌
dart[i-1] *= 2
dart[i] = int(dart[i][0]) ** bonus[dart[i][1]] * option[dart[i][2]] # 보너스로 제곱해주고 option에 맞게 곱해줌
answer = sum(dart)
return answer
개선된 코드는 정규표현식을 활용한 코드입니다.
이는 p = re.compile() 코드를 보시면 알 수 있습니다.
정규표현식을 compile하는 re.compile은 ( )를 통해 구분이 되는데요. 즉, 해당 코드에서는 크게 ([0-9]+) 부분과 ([SDT]) 부분, ([*#]?) 부분으로 총 3 부분으로 나눠집니다.
[0-9]는 0부터 9까지 숫자 중에 일치되는 경우를 찾는 정규표현식입니다. 여기서 +는 1개 이상을 뜻하므로, ([0-9]+)는 숫자이면서 1개 이상인 경우를 찾게 됩니다.
+가 들어가서 0~9인 숫자 뿐만 아니라 10인 경우도 찾을 수 있게 됩니다.
다음으로 ([SDT])는 S D T 중에 일치되는 경우를 찾게 되는 정규표현식입니다.
마지막으로 ([*#]?)는 두 번째 정규표현식 파트와 비슷하니 대충 유추하실 수 있겠지만, *이나 #인 경우를 찾습니다.
단, ? 는 나오지 않을 수도 있고, 1번 나올 수도 있습니다.
문제에서 옵션의 경우 *이거나 #이고, 혹은 아예 없을 수 있다고 했기 때문에, 이를 구현하기 위해 ?를 사용했다고 볼 수 있습니다.
1개 이상일 때는 +를, 0개 혹은 1개 일 때는 ?를 사용한다고 기억하면 좋겠습니다.
그러고 나서 p.findall()를 활용해 dartResult에서 compile 한 정규표현식 규칙을 만족하는 경우를 모두 찾은 것을 dart에 저장합니다.
dart를 print 해보면 다음과 같이 나오는 것을 확인할 수 있습니다.
보시면 전체적으로는 list이고, 안에는 3개의 element로 이루어진 튜플인 것을 알 수 있습니다.
이에 대해서 for문을 수행하게 됩니다.
다음으로 if dart[i][2] == '*' and i > 0: 부분인데요. 이는 i가 0보다 클 때는 *이 적용되었을 때 이전 score에도 2배를 해줘야 하기 때문에 dart[i-1] *= 2를 해준다고 보시면 됩니다.
그리고 dart[i] = int(dart[i][0]) ** bonus[dart[i][1]] * option[dart[i][2]]로 구현을 해서 최종 마지막 점수를 내는 것을 확인할 수 있습니다.
score 값에 bonus에 해당하는 dictionary에서 찾아 이를 제곱으로 곱해주고, 마지막으로 option에 해당하는 *이나 #인 경우는 2배 혹은 -1배를 적용해 주는 코드입니다.
마지막으로는 sum을 해서 결과를 내주면 됩니다.
확실히 정규표현식을 활용하면 조금 더 손쉽게 score와 보너스, 옵션을 찾을 수 있었고, 이를 dictionary를 활용해서 간편하게 최종 점수를 계산할 수 있었습니다.
def solution(N, stages):
fail = {}
for i in range(1, N+1):
pass_cnt = 0
succ_cnt = 0
for s in stages:
# stage가 i보다 크면 지나왔고, 해당 스테이지도 성공한 것
if s > i:
pass_cnt += 1
succ_cnt += 1
# 같기만 하면 지나오기만 한 것
elif s == i:
pass_cnt += 1
# 한번도 안 지나간 stage는 0으로 처리해야 하므로 별도로 if문으로 뺀다
if pass_cnt != 0:
fail[i] = (pass_cnt - succ_cnt) / pass_cnt
else:
fail[i] = 0
fail_rate = sorted(fail, key=lambda x: fail[x], reverse = True)
return fail_rate
스테이지가 N개 있으므로, N개에 대해서 for문을 진행해야 하는 문제입니다.
반복문을 진행할 때, pass를 몇 명 했는지, 스테이지를 깬 사람은 몇 명인지 저장하기 위해서 변수를 설정해 줍니다.
그리고 결과에 대한 list인 stages에 대해서 반복문을 적용하면서, 각각이 i보다 크면 해당 stage를 지나왔고 성공한 것이므로 각각을 1개씩 올려주며, 같은 경우는 지나오기만 했으므로 pass_cnt를 하나 올려주는 방식으로 접근합니다.
그리고 실패율을 저장하는 dictionary인 fail에 대해서 값들을 저장해 줍니다.
만약 pass_cnt가 0인 경우는 해당 stage에 도달한 사람이 아무도 없으므로, 실패율을 0으로 저장합니다.
마지막으로 fail은 dictionary인데, 이를 for문으로 print 하면 key값이 나오게 됩니다.
그런데 fail의 키 값은 1, 2, 3... 등의 각 stage의 이름이므로, fail의 각 stage를 key로 잡아서 sort를 하면 문제에서 얘기하는 대로 실패율이 높은 순으로 배열을 return 할 수 있습니다.
하지만 위 풀이는 시간 복잡도 관점에서 간당간당하게 풀어진 케이스라, 조금 더 시간 복잡도 관점에서 생각해 볼 필요가 있어서 다양한 코드들을 참고해서 더욱 효과적인 풀이를 만들어냈습니다.
새로 만든 풀이:
from collections import Counter
def solution(N, stages):
# stage 사람 수 저장
cnt = len(stages)
stage_dict = Counter(stages)
failure = {}
for i in range(1, N + 1):
if cnt != 0:
# 딱 i인 경우라면 도전은 했지만 못 깬 경우니까 실패율의 분자가 됨.
failure[i] = stage_dict[i] / cnt
# stage i에 있는 인원은 그만큼 차감해줌(이미 해당 stage에서 count 했으니까)
cnt -= stage_dict[i]
else:
failure[i] = 0
# dictionary를 그냥 뽑으면 key가 나오게 된다.
# 그래서 failure[i]를 하면 value 기준으로 sort 되고, 나오는 것은 key가 된다.
return sorted(failure, key=lambda i: failure[i], reverse=True)
collections 패키지에 있는 Counter라는 함수는 중복된 데이터가 저장된 list에 사용하면 각 원소가 몇 번씩 나오는지 저장된 객체를 만들어 냅니다.
여기서 stages의 경우 중복된 값이 존재하는 경우가 많을 수 있고, 이럴 때는 굳이 모든 요소들을 다 for문으로 살펴볼게 아니라 Counter를 활용하게 되면 말 그대로 stages에 존재하는 요소의 가짓수 정도만 for문을 돌리면 되니까, 최소한 전체를 for문으로 돌리는 것보다는 시간 복잡도를 줄일 수 있게 됩니다.
그리고 풀이 아이디어 관점에서도 변경이 있었습니다.
먼저 stages에 있는 개수를 cnt로 저장하고, stages를 Counter 함수를 이용해서 dictionary 형태의 객체를 만들어냅니다.
그리고 동일하게 N개의 stage에 대해서 for문을 진행합니다.
cnt가 0인 경우는 해당 stage에 도달한 케이스가 0개 이므로, 이는 실패율을 0으로 저장해 줍니다.
그렇지 않은 경우는, stages에서 i에 해당하는 값의 개수를 실패율의 분자로 사용하고, cnt를 분모로 사용합니다.
저도 처음에 이 내용이 이해가 안 갔는데, 예시를 들어서 생각해 보겠습니다. (첫 번째 Test case)
for문에서 i가 1인 경우 (stage 1인 경우), 현재 stages에서 1인 경우가 1개 있으므로 stage_dict[1]은 1이 될 것이고, cnt는 8이 됩니다. 따라서 이 경우에는 실패율이 1/8로 계산됩니다.
for문에서 i가 2인 경우 (stage 2인 경우), 현재 stages에서 2인 경우가 3개 있으므로 stage_dict[2]은 3이 될 것이고, cnt는 stage 1에서 한 명 있었으니 이를 제외하고 7이 될 것입니다. 따라서 이 경우에는 실패율이 3/7로 계산됩니다.
여기서 stages에서 i에 해당하는 값의 개수를 실패율의 분자로 사용하는 이유는, stages에서 각 자연수는 사용자가 현재 도전 중인 스테이지의 번호를 나타내기 때문입니다.
즉, 해당 스테이지를 도전하고 있는 사람의 수 이기 때문에, 이를 정의된 실패율의 분자인 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수와 동일한 것이죠.
그리고 여기서 카운팅 된 만큼은 전체 인원수에서 빼줘야 하므로, cnt에서 그만큼을 빼주면 됩니다.
마지막으로 실패율이 저장된 dictionary를 value 기준으로 내림차순으로 저장해 주면 정답이 됩니다.
처음 제가 풀었던 답안의 경우 시간 복잡도가 가장 높은 테스트 22에서 8116.53ms를 받았고, 개선한 답안의 경우 테스트 22에서 12.09ms를 받았으니, 거의 600배 이상 시간 복잡도 차이를 보였습니다.
Counter라고 하는 함수를 잘 활용하면, 여러모로 다른 문제에서도 시간 복잡도를 줄일 수 있을 것 같습니다.
def solution(strings, n):
answer = []
# 1. n번째 요소를 먼저 모은다.
element = []
for s in strings:
element.append(s[n])
# 2. 요소들을 set으로 묶은 다음에 sort한다.
ele_lst = sorted(list(set(element)))
# 3. 정렬된 요소 list에서 하나씩 빼면서, strings을 돌며 해당하는 요소랑 같은 애들을 빼고
# 뺀 애들을 오름차순으로 정렬한 다음 answer에 다시 insert한다.
for ele_l in ele_lst:
sample_part = []
for s in strings:
if s[n] == ele_l:
sample_part.append(s)
answer.extend(sorted(sample_part))
return answer
처음에는 단순히 n번째 요소만 가지고 sort하는 방식을 생각했는데, 문제에서 '인덱스 n의 문자가 같은 문자열이 여럿 일 경우, 사전순으로 앞선 문자열이 앞쪽에 위치합니다.'라는 조건이 있었습니다.
그래서 단순히 n번째 요소만 가지고 sort를 하게 되면 문제가 발생합니다.
이를 해결하기 위해서 단계적으로 접근하는 방법을 생각해 보았는데요.
먼저 n번째 요소를 list에 담고, 이를 set으로 묶은 다음 list로 만들고 오름차순으로 만들어줍니다.
그런 다음, 이 정렬된 요소 list에서 하나씩 빼면서, strings에 대해 for문을 돌면서 n번째 요소가 정렬된 요소 list에서 나온 요소와 같은 경우만 append 한 다음, 이를 sort 해서 answer에 extend해주는 방식을 생각했습니다.
list에서 extend를 하는 경우는 list 안에 있는 element들을 그대로 list 안에 넣어줄 때 사용합니다. (많이 사용하는 append와의 차이점)
순차적으로 봤을 땐 나쁘지 않은 풀이인 것 같으나, 아무래도 조금 더 간단한 풀이가 있으니 간단하게 풀 수 있는 방법도 괜찮을 것 같습니다.
