[내 풀이]
# 피보나치로 푸는 거였구나 ..
def solution(n):
table = [0]*(n+1)
table[1] = 1
table[2] = 2
for i in range(3,n+1):
table[i] = table[i-2]+table[i-1]
return table[n]
[내 풀이]
from collections import Counter
def solution(k, tangerine):
answer = 0
box = 0
counter = Counter(tangerine).most_common()
for a, b in counter:
box += b
answer += 1
if box >= k:
return answer
[참고 풀이]
# tangerine.sort(key = lambda t: (-counter[t], t)) 를 통해서 개수 많은 순으로 정렬해 둠 => 그 박스에 어떤 과일이 몇 개씩 들어가는지 까지 값을 정리할 수 있다.
from collections import Counter
def solution(k, tangerine):
counter = Counter(tangerine)
tangerine.sort(key = lambda t: (-counter[t], t))
return len(set(tangerine[:k]))
[내 풀이]
# 내 풀이는 오류가 발생할 경우 바로 False를 리턴해서 더 빠를 듯 하다.
from collections import deque
def check(s):
stk = []
for x in s:
if x in ['(', '{', '[']:
stk.append(x)
else:
if len(stk) == 0:
return False
if x == ')':
if stk.pop() != '(':
return False
if x == '}':
if stk.pop() != '{':
return False
if x == ']':
if stk.pop() != '[':
return False
if stk == []:
return True
def solution(s):
s = deque(s)
ans = 0
for i in range(len(s)):
if check(''.join(s)):
ans += 1
s.rotate(-1)
return ans
[참고 풀이]
# is_valid() 라는 네이밍 센스
def is_valid(s):
stack = []
for ch in s:
if not stack:
stack.append(ch)
elif stack[-1] == '(':
if ch==')': stack.pop()
else: stack.append(ch)
elif stack[-1] == '{':
if ch=='}': stack.pop()
else: stack.append(ch)
elif stack[-1] == '[':
if ch==']': stack.pop()
else: stack.append(ch)
return False if stack else True
# s[i:]+s[:i]가 s.rotate(-1)랑 같은 의미를 갖는구나.
def solution(s):
answer = 0
for i in range(len(s)):
answer += is_valid(s[i:]+s[:i])
return answer
[내 풀이] - 실제로 내 코드가 더 빨랐다.
테스트 1 〉
통과 (18.41ms, 10.2MB)
테스트 2 〉
통과 (14.05ms, 10.2MB)
테스트 3 〉
통과 (13.94ms, 10.2MB)
테스트 4 〉
통과 (17.59ms, 10.3MB)
테스트 5 〉
통과 (37.85ms, 10.1MB)
테스트 6 〉
통과 (19.11ms, 10.2MB)
테스트 7 〉
통과 (23.70ms, 10.1MB)
테스트 8 〉
통과 (29.64ms, 10.1MB)
테스트 9 〉
통과 (52.90ms, 10.1MB)
테스트 10 〉
통과 (66.60ms, 10.1MB)
테스트 11 〉
통과 (114.03ms, 10.2MB)
테스트 12 〉
통과 (0.01ms, 10.2MB)
테스트 13 〉
통과 (0.02ms, 10.3MB)
테스트 14 〉
통과 (0.01ms, 10.2MB)
[참고 풀이]
테스트 1 〉
통과 (137.33ms, 10.2MB)
테스트 2 〉
통과 (143.11ms, 10.1MB)
테스트 3 〉
통과 (139.97ms, 10.2MB)
테스트 4 〉
통과 (146.90ms, 10.1MB)
테스트 5 〉
통과 (141.71ms, 10.1MB)
테스트 6 〉
통과 (141.60ms, 10.4MB)
테스트 7 〉
통과 (138.04ms, 10.3MB)
테스트 8 〉
통과 (139.06ms, 10.3MB)
테스트 9 〉
통과 (179.51ms, 10.3MB)
테스트 10 〉
통과 (137.70ms, 10.1MB)
테스트 11 〉
통과 (130.80ms, 10.3MB)
테스트 12 〉
통과 (0.00ms, 10.1MB)
테스트 13 〉
통과 (0.01ms, 10.2MB)
테스트 14 〉
통과 (0.01ms, 10.2MB)
[내 풀이]
from collections import deque
def solution(cacheSize, cities):
time = 0
cache = []
cities = [x.lower() for x in cities]
if cacheSize==0: return len(cities)*5
for city in cities:
if city not in cache:
time += 5
if len(cache)==cacheSize:
cache.pop(0)
cache.append(city)
else:
time += 1
cache.remove(city)
cache.append(city)
return time
[참고 풀이]
# deque에 maxlen을 지정할 수 있다. 용량 초과하면 가장 옛날 것부터 popleft() 된다.
# deque에서도 remove가 된다.
def solution(cacheSize, cities):
import collections
cache = collections.deque(maxlen=cacheSize)
time = 0
for i in cities:
s = i.lower()
if s in cache:
cache.remove(s)
cache.append(s)
time += 1
else:
cache.append(s)
time += 5
return time
정규표현식이 정말x100 잘 정리되어있다. 이 글만 정독해도 정규표현식 금방 마스터할 수 있다. 그 동안 정확하지 않은(?) 단편적인 정보만 읽어서 헷갈렸던 부분이 모두 해결됐던 글이다.
# 내 풀이
import re
from collections import Counter
def solution(str1, str2):
p = re.compile('[a-zA-Z]{2}')
aCnt = Counter([str1[i:i + 2].lower() for i in range(len(str1) - 1) if p.match(str1[i:i + 2])])
bCnt = Counter([str2[i:i + 2].lower() for i in range(len(str2) - 1) if p.match(str2[i:i + 2])])
keys = aCnt.keys() | bCnt.keys()
n = sum(min(aCnt[key], bCnt[key]) for key in keys)
d = sum(max(aCnt[key], bCnt[key]) for key in keys)
return (int((n / d) * 65536) if d != 0 else 65536)
# 참고 풀이
import re
import math
def solution(str1, str2):
str1 = [str1[i:i+2].lower() for i in range(0, len(str1)-1) if not re.findall('[^a-zA-Z]+', str1[i:i+2])]
str2 = [str2[i:i+2].lower() for i in range(0, len(str2)-1) if not re.findall('[^a-zA-Z]+', str2[i:i+2])]
gyo = set(str1) & set(str2)
hap = set(str1) | set(str2)
if len(hap) == 0 :
return 65536
gyo_sum = sum([min(str1.count(gg), str2.count(gg)) for gg in gyo])
hap_sum = sum([max(str1.count(hh), str2.count(hh)) for hh in hap])
return math.floor((gyo_sum/hap_sum)*65536)
[내 풀이]
# 3:39 - 3:58
def solution(msg):
dic = [chr(i) for i in range(ord('A'), ord('A') + 26)]
temp = ''
answer = []
for m in msg:
if temp + m in dic:
temp += m
continue
else:
answer.append(dic.index(temp) + 1)
dic.append(temp + m)
temp = m
answer.append(dic.index(temp) + 1)
return answer
[참고 풀이]
#처음 정의할 땐 귀찮지만, d로 값 빼오는 게 이후 가독성이 훨씬 좋다. (dic.index(temp)와 비교됨)
#temp+=m과 동일한 원리지만, 한 글자 더 추가한다는 것이 더 명확하게 전달되기 때문에 이렇게 표현하는 게 가독성이 더 좋았을 듯 하다.
def solution(msg):
alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
d = {k:v for (k,v) in zip(alphabet, list(range(1,27)))} #처음 정의할 땐 귀찮지만, d로 값 빼오는 게 이후 가독성이 훨씬 좋다. (dic.index(temp)와 비교됨)
answer = []
while True:
if msg in d:
answer.append(d[msg])
break
for i in range(1, len(msg)+1):
if msg[0:i] not in d: #temp+=m과 동일한 원리지만, 한 글자 더 추가한다는 것이 더 명확하게 전달되기 때문에 이렇게 표현하는 게 가독성이 더 좋았을 듯 하다.
answer.append(d[msg[0:i-1]])
d[msg[0:i]] = len(d)+1
msg = msg[i-1:]
break
return answer
[내 풀이]
def tenToN(x, n):
nums = {k:v for k, v in zip(range(0,17), ['0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'])}
str = ''
while x>=n:
str += nums[x%n]
x = x//n
str += nums[x%n]
return str[::-1]
def solution(n, t, m, p):
answer = ''
num_list = []
num = 0
while len(num_list)<t*m:
for x in tenToN(num, n):
num_list.append(x)
num += 1
return ''.join(num_list[p-1::m][:t])
[참고 풀이]
def solution(n, t, m, p):
data = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "A", "B", "C", "D", "E", "F"]
numbers = "0"
for number in range(1, t*m):
temp = []
while number > 0:
temp.append(data[number%n])
number //= n
numbers += "".join(reversed(temp))
return numbers[p-1:t*m:m]
# 내 풀이
def solution(record):
nickById = {(rec + ' ').split(' ')[1]: (rec + ' ').split(' ')[2] for rec in record if
(rec + ' ').split(' ')[0] != 'Leave'}
answer = []
for rec in record:
action, id, nick = (rec + ' ').split(' ')[:3]
if action == 'Enter':
answer.append("%s님이 들어왔습니다." % (nickById[id]))
if action == 'Leave':
answer.append("%s님이 나갔습니다." % (nickById[id]))
return answer
# 내 풀이2
# printer를 이용하니 if문이 줄어 상대적으로 깔끔해 보이는 듯 하다.
def solution(record):
nickById = {(rec + ' ').split(' ')[1]: (rec + ' ').split(' ')[2] for rec in record if
(rec + ' ').split(' ')[0] != 'Leave'}
printer = {'Enter': '님이 들어왔습니다.', 'Leave': '님이 나갔습니다.'}
answer = []
for rec in record:
action, id, nick = (rec + ' ').split(' ')[:3]
if rec.split(' ')[0] != 'Change':
answer.append(nickById[id]+printer[action])
return answer
# 참고 풀이
# 출력 문구도 딕셔너리 활용
def solution(record):
answer = []
namespace = {}
printer = {'Enter':'님이 들어왔습니다.', 'Leave':'님이 나갔습니다.'}
for r in record:
rr = r.split(' ')
if rr[0] in ['Enter', 'Change']:
namespace[rr[1]] = rr[2]
for r in record:
if r.split(' ')[0] != 'Change':
answer.append(namespace[r.split(' ')[1]] + printer[r.split(' ')[0]])
return answer
def solution(fees, records):
cars = []
answer = []
dic_IN = {}
dic_TIME = {}
# dic_IN : 차량 별 입차시간 (출차 시 기록 삭제)
for rec in records:
hhmm, car, io = rec.split(' ')
if car not in cars:
cars.append(car)
m = 60*int(hhmm[:2]) +int(hhmm[3:5])
if io == 'IN':
dic_IN[car] = m
elif io == 'OUT':
M = dic_IN.pop(car)
dic_TIME[car] = dic_TIME.get(car, 0) + m-M
# dic_TIME : 차량 별 주차시간
for key in dic_IN.keys():
m = dic_IN[key]
dic_TIME[key] = dic_TIME.get(key, 0) + 23*60+59-m
# answer : 주차요금 계산
for car in sorted(cars): # 주차요금 계산
v = dic_TIME[str(car)]
if v <= fees[0]:
answer.append(fees[1]) # 기본요금
else:
v -= fees[0] # 추가요금
if v % fees[2] != 0: # 올림처리
v += (fees[2] - v % fees[2])
answer.append(fees[1] + (v // fees[2]) * fees[3])
return answer
# 내 풀이
# 일부 실패
def solution(dirs):
answer = 0
moves = {'U':(0,1), 'D':(0,-1), 'R':(1,0), 'L':(-1,0)}
visited = dict()
x, y = 0, 0
for d in dirs:
dx, dy = moves[d]
nx, ny = x+dx, y+dy
if nx<-5 or nx>5 or ny<-5 or ny>5:
continue
visited[(x,y,nx,ny)] = visited.get((x,y,nx,ny), 0) + 1
x, y = nx, ny
return len(visited.keys())
# 내 풀이2
def solution(dirs):
answer = 0
moves = {'U':(0,1), 'D':(0,-1), 'R':(1,0), 'L':(-1,0)}
visited = dict() #집합으로 표현했으면 add 만으로 중복 처리가 된다.
x, y = 0, 0
for d in dirs:
dx, dy = moves[d]
nx, ny = x+dx, y+dy
if nx<-5 or nx>5 or ny<-5 or ny>5: # if a<=x<=b and c<=y<=d 로 표현하는 게 더 깔끔했다.
continue
visited[(x,y,nx,ny)] = visited.get((x,y,nx,ny), 0) + 1
x, y = nx, ny
jungbok = 0
for key in visited.keys():
a, b, c, d = key
if (c, d, a, b) in visited.keys():
jungbok += 0.5
return len(visited.keys()) - jungbok
# 참고 풀이
def solution(dirs):
s = set()
d = {'U': (0,1), 'D': (0, -1), 'R': (1, 0), 'L': (-1, 0)}
x, y = 0, 0
for i in dirs:
nx, ny = x + d[i][0], y + d[i][1]
if -5 <= nx <= 5 and -5 <= ny <= 5:
s.add((x,y,nx,ny))
s.add((nx,ny,x,y))
x, y = nx, ny
return len(s)//2
# 내 풀이
# 구상단계부터 너무 꼬아서 생각해버림:
# 한 번 배운 스킬은 다시 배우지 않기 때문에 제약 조건에서 삭제해버릴 수 있다는 것을 간과했기 때문이다.
# 그래서 이미 나올 수 없는 제약 조건을 처음부터 끝까지 확인하느라 복잡해졌다. (skill_list.pop(0))을 하지 않아서.
# 그 외 구조는 모두 같았다.
def solution(skill, skill_trees):
answer = 0
for tree in skill_trees:
for i, t in enumerate(tree):
if t not in skill:
continue
if any(x not in tree[:i] for x in skill[:skill.index(t)]):
break
else:
answer += 1
return answer or -1
# 참고풀이
# 제약이 있는 원소들을 모두 찾아낸 다음에, 제약 조건을 처음부터 삭제해나가는 방식 (pop(0))
# 훨씬 직관적
def solution(skill, skill_trees):
answer = 0
for skills in skill_trees:
skill_list = list(skill)
for s in skills:
if s in skill:
if s != skill_list.pop(0):
break
else:
answer += 1
return answer
# 내 풀이
import re
def solution(files):
answer = files[:]
p1 = re.compile('[^0-9]+')
p2 = re.compile('[0-9]+')
answer.sort(key=lambda file:(p1.search(file).group().lower(), int(p2.search(file).group()), files.index(file)))
return answer
# 참고풀이
# 1,2,3 순위의 정렬 기준이 있다고 했을 때,
# 3순위의 정렬 기준은 '원래 리스트 순서'라면
# 2순위 정렬, 1순위 정렬 순으로 정렬을 하면 1,2,3순위로 정렬이 된다. 는 접근 방법이 새로웠다.
import re
def solution(files):
a = sorted(files, key=lambda file : int(re.findall('\d+', file)[0]))
b = sorted(a, key=lambda file : re.split('\d+', file.lower())[0])
return b
정석 풀이를 까먹을 때 쯤 다시 풀고 복습해보자 / 답이 안나와서 해설을 봐버렸다 ㅠㅠ
# 내 풀이
# 참고풀이
# stack
def solution(numbers):
stack = []
answer = [0] * len(numbers)
for i in range(len(numbers)):
while stack and numbers[stack[-1]] < numbers[i]:
answer[stack.pop()] = numbers[i]
stack.append(i)
while stack:
answer[stack.pop()] = -1
return answer
# 순수 구현 문제
# 내 풀이
def solution(m, n, board):
board = [list(row) for row in board]
while True:
temp = set()
for i in range(m-1):
for j in range(n-1):
if board[i][j] == '': continue
if board[i][j] == board[i][j+1] == board[i+1][j] == board[i+1][j+1]:
temp.update([(i,j), (i,j+1), (i+1,j), (i+1,j+1)])
if not temp:
break
for i, j in temp:
board[i][j] = ''
temp = list(temp)
temp.sort(key=lambda x:(x[1], -x[0]))
for j in range(n):
cnt = 0
for i in range(m-1,-1,-1):
if board[i][j] == '':
cnt += 1
else:
if cnt == 0: continue
board[i+cnt][j] = board[i][j]
board[i][j] = ''
return m*n-sum([1 for i in range(m) for j in range(n) if board[i][j] != ''])
# 참고풀이
def solution(m, n, board):
x = board
x2 =[]
for i in x:
x1 = []
for i2 in i:
x1.append(i2)
x2.append(x1)
point = 1
while point != 0:
list = []
point = 0
for i in range(m - 1):
for j in range(n - 1):
if x2[i][j] == x2[i][j + 1] == x2[i + 1][j] == x2[i + 1][j + 1] != '팡!':
list.append([i, j])
point += 1
for i2 in list:
i, j = i2[0], i2[1]
x2[i][j], x2[i][j + 1], x2[i + 1][j], x2[i + 1][j + 1] = '팡!', '팡!', '팡!', '팡!'
for i3 in range(m):
for i in range(m - 1):
for j in range(n):
if x2[i + 1][j] == '팡!':
x2[i + 1][j], x2[i][j] = x2[i][j], '팡!'
cnt = 0
for i in x2:
cnt += i.count('팡!')
return cnt
# 내 풀이
# 똑같은 풀이인데 dp[i]에 값을 넣을 때 미리 나머지(10000007)을 계산한 후 넣은 것과 마지막에 %계산해 준 거랑 시간 차이가 엄청 심했다.
# 큰 숫자끼리 연산하는 게 훨씬 시간이 오래 걸리는 듯 하다. 그렇기 때문에 미리 나머지 계산을 해서 값을 저장 후 연산이 되도록 하자.
def solution(n):
answer = 0
dp = [0]*(n+1)
dp[0], dp[1] = 1, 2
for i in range(2,n):
dp[i] = dp[i-2]+dp[i-1]
return dp[n-1]%1000000007
# 내 풀이2
def solution(n):
answer = 0
dp = [0]*(n+1)
dp[0], dp[1] = 1, 2
for i in range(2,n):
dp[i] = (dp[i-2]+dp[i-1])%1000000007
return dp[n-1]
내 풀이1
내 풀이2
# 내 풀이
# 원리 파악이 중요했던 문제
def solution(numbers):
for i, num in enumerate(numbers):
try:
num = '0'+str(bin(num))[2:]
f = num.rindex('0')
if num[f+1]=='1':
numbers[i] = int('0b'+num[:num.rindex('01')]+'10'+num[num.rindex('01')+2:], 2)
except:
numbers[i] = int('0b'+num[:num.rindex('0')]+'1'+num[num.rindex('0')+1:], 2)
return numbers
# 참고풀이
# 비트 쉬프트 연산<< 2배 >>:1/2배
def solution(numbers):
answer = []
for idx, val in enumerate(numbers):
answer.append(((val ^ (val+1)) >> 2) +val +1)
return answer
[내 풀이]
- DP로 접근하려고 해서 시간 초과가 났었던 문제
[참고 풀이]
- n이 1억 단위인 것을 보고 O(logN) 을 떠올렸어야 한다.
- 복잡할 줄 알았지만, n /= 2 될 것이라는 것을 예측할 수 있었어야 했다.
def solution(n):
cnt = 0
while n>0:
if n%2 == 0:
n /= 2
else:
cnt += 1
n = (n-1)//2
return cnt
[내 풀이]
def solution(A, B): # arr1, arr2 로 그대로 두면 가독성이 좋지 않다 : A, B로 바꿔 표현해주기
answer = []
for i, A_row in enumerate(A):
temp = []
# *B : 가장 바깥 [] 를 날려준다. -> [1,2][3,4][5,6]
# zip(*B)) : 행과 열을 서로 바꿔 준 효과 !! [[1,2],[3,4],[5,6]] : [행,행,행] -> [(1,3,5),(2,4,6)] : [열,열]
for j, B_col in enumerate(zip(*B)):
k = 0
for a, b in zip(A_row, B_col):
k += a*b
temp.append(k)
answer.append(temp)
return answer
[참고 풀이]
- 같은 풀이이지만 리스트 컴프리헨션을 활용해서 짧게 표현한 풀이.
def productMatrix(A, B):
return [[sum(a*b for a, b in zip(A_row,B_col)) for B_col in zip(*B)] for A_row in A]
[내 풀이]
# 소수는 n<=1 일 때 false (n==1은 모자라다)
# 정규식 안 써도 간단하게 split('0') 쓰면 됐었다.
import re
def tenton(n, k):
s = ""
while n > 0:
s += str(n % k)
n //= k
return s[::-1]
def isPrime(n):
if n == 1:
return False
for i in range(2, int(n ** (1 / 2)) + 1): # 범위 n으로 잡았더니 효율성에 걸렸다. 최소한으로 잡자!
if n % i == 0:
return False
else:
return True
def solution(n, k):
p = re.compile('[1-9]+')
s = tenton(n, k)
lst = p.findall(s)
return sum([1 for x in lst if isPrime(int(x))])
[참고 풀이]
# n을 k진법으로 나타낸 문자열 반환
def conv(n, k):
s = ''
while n:
s += str(n%k)
n //= k
return s[::-1]
# n이 소수인지 판정
def isprime(n):
if n <= 1: return False
i = 2
while i*i <= n:
if n%i == 0: return False
i += 1
return True
def solution(n, k):
s = conv(n,k)
cnt = 0
for num in s.split('0'):
if not num: continue # 빈 문자열에 대한 예외처리
if isprime(int(num)): cnt += 1
return cnt
[내 풀이]
def solution(number, k):
stk = []
cnt = 0
for i, n in enumerate(number):
while stk and stk[-1]<n:
stk.pop()
cnt += 1
if cnt == k:
return ''.join(stk) + number[i:]
stk.append(n)
return ''.join(stk[:-(k-cnt)])
[참고 풀이]
# 나 처럼 제거한 숫자의 수 cnt 를 증가시키면서 cnt == k를 찾는 것이 아니라
# 변수 k를 그대로 사용하면서 조건이 만족할 때마다 k를 줄인 것이 코드 압축과 가독성에 좋은 효과를 줬던 듯하다.
def solution(number, k):
stack = [number[0]]
for num in number[1:]:
while len(stack) > 0 and stack[-1] < num and k > 0:
k -= 1
stack.pop()
stack.append(num)
if k != 0:
stack = stack[:-k]
return ''.join(stack)
[참고 풀이] #chat GPT
# number의 자릿수를 표현할 때: digit
def solution(number, k):
stack = []
for digit in number:
while stack and stack[-1] < digit and k > 0:
stack.pop()
k -= 1
stack.append(digit)
# 만약 k개의 수를 모두 제거하지 못했다면 남은 k개의 수를 뒤에서부터 제거
while k > 0:
stack.pop()
k -= 1
return ''.join(stack)
댓글