1. 시각
메모
--> 너무 많이 풀어봐서 5분컷 걍외움 이문제
정수 n이 입력되면
00시 00분 00초 ~ n시 00분 00초까지 모든 시각 중
3이 하나라도 포함되는 경우의 수 구하기
--> 브루트포스 문제인듯
알고리즘
n 입력받고
for time range(0~n)
for minute range(0~59)
for sec range(0~59)
current = str(time)+str(minute)+str(sec)
if '3' in current:
ans++솔루션 - 내가 푼
- python
n = int(input())
ans = 0
for time in range(n+1): # n시까지니까
for minute in range(60):
for sec in range(60):
current = str(time)+str(minute)+str(sec)
if '3' in current:
ans += 1
print(ans)
문자열 압축 (2020카카오 코테)
메모
1개단위부터 n개 단위까지 다 해봐야함
이때, n개단위만큼씩 끊어서 진행하고, 남은게 n보다 적으면 뒤에는 그냥 붙여줌
2a2ba2c len = 7
2ababcdcd len = 9
- 주어지는 문자열의 길이 1,000이므로, 브루트포스 가능!
알고리즘
- 음성인식 했을 때처럼 stride를 주자 => 방법은 range( , ,여기!)
arr = input
for i in range(1, len(arr)+1): # 로 모든길이까지 보도록 시작해야함
for j in range(0, len(arr), i):
current.append(arr[j:j+i]) # <-- 스트라이드!!!-
stride 준걸 각각 리스트에 저장해두고,
앞뒤로 같은 경우 -> 숫자++
같지 않은 경우
-> 알파벳 개수가 1개라면 -> 알파벳만 push
-> 알파벳 개수가 2개이상이라면 ->숫자+알파벳을 push -
마지막꺼 누락되므로 넣어줘야함
-
tmp_answer목록을 "".join()으로 통합해서 answer에 len()형태로 넣어줌
-
return min()
솔루션 코드 - 내가 푼
- 개어렵다
- 여차저차 풀긴 했는데 테케 하나 놓침 -> 뭔지모름
def solution(arr):
answer = []
tmp_answer = []
current = []
num = 1
if len(arr) == 1:
return 1
for i in range(1, (len(arr)//2 + 1)): # 로 모든길이까지 보도록 시작해야함
for j in range(0, len(arr), i):
current.append(arr[j:j+i])
for c in range(len(current) - 1):
if current[c] == current[c+1]:
num += 1
else:
if num == 1: # 1개인 경우
tmp_answer.append(current[c])
else:
tmp_answer.append(str(num)+current[c])
num = 1
if num == 1: # 1개인 경우
tmp_answer.append(current[-1])
else:
tmp_answer.append(str(num)+current[-1])
answer.append(len("".join(tmp_answer)))
current = []
tmp_answer = []
return min(answer)
솔루션 코드 - 동빈나
- 나랑 생각한 큰 알고리즘 틀은 같은데 차이점은
- stride(=step)에 따른 일종의 chunk를 미리 만들어서(prev = s[0:step]) 계산해나감
- 청크단위로 비교!
- 그리고 나는 귀찮게 리스트에 계속 append하면서 진행했는데
- 이 코드는 문자열로 처리해버려서 덜 복잡
- 그래서 마지막에 리스트 내에서 min()이 아니라, 바로바로 min(a, b) 수행
def solution(s):
answer = len(s)
# 1개 단위(step)부터 압축 단위를 늘려가며 확인
for step in range(1, len(s) // 2 + 1):
compressed = ""
prev = s[0:step] # 앞에서부터 step만큼의 문자열 추출 (=청크!)
count = 1
# 단위(step) 크기만큼 증가시키며 이전 문자열과 비교
for j in range(step, len(s), step):
# 이전 상태와 동일하다면 압축 횟수(count) 증가 (청크단위로 비교!)
if prev == s[j:j + step]:
count += 1
# 다른 문자열이 나왔다면(더 이상 압축하지 못하는 경우라면)
else:
compressed += str(count) + prev if count >= 2 else prev
prev = s[j:j + step] # 다시 상태 초기화
count = 1
# 남아있는 문자열에 대해서 처리
compressed += str(count) + prev if count >= 2 else prev
# 만들어지는 압축 문자열이 가장 짧은 것이 정답
answer = min(answer, len(compressed))
return answer
Do My Best