마지막 힌트에서 다 준 문제이다. 저 부분을 코드로 구현하고 위의 수식 중 mod M 부분만 추가하면 해결된다.
import sys
def change_ord(char): # 문자를 숫자로 출력하는 함수 a = 1, z = 26
return ord(char) - 96
L = int(sys.stdin.readline()) # 문자열의 길이를 입력받을 변수
str = sys.stdin.readline() # 문자열을 입력받을 변수
answer = 0 # 해쉬 값을 저장할 빈 변수
for i in range(L):
answer += change_ord(str[i]) * (31 ** i) # 힌트를 코드로 구현
# 1234567891
print(answer % 1234567891) # mod M 을 코드로 구현
arr안에 값들을 2진수로 변환하여 n자리수로 만들고 각각을 비교하여 # or 공백을 출력한다.
def solution(n, arr1, arr2):
answers = []
barr1 = [] # 2진수로 만들걸 저장할 빈 변수
barr2 = [] # 2진수로 만들걸 저장할 빈 변수
# 2진수로 만들어서 저장
for i in range(n):
a = bin(arr1[i])[2:] # bin() 한 결과값이 str이라 0b를 제외한 숫자만 남김
b = bin(arr2[i])[2:]
while (True): # bin()의 결과 앞자리 0은 생략되므로 자리수에 맞게 0으로 채워준다.
if len(a) != n:
a = "0" + a
else:
break
while (True):
if len(b) != n:
b = "0" + b
else:
break
barr1.append(a) # n자리로 만든 binary값을 리스트에 넣어준다.
barr2.append(b)
# 각각 비교해서 결과에 따라 # 출력
for j in range(n):
answer = "" # answer 초기화
for k in range(len(barr1[j])): # 2진수의 길이만큼 반복
if barr1[j][k] == "0" and barr2[j][k] == "0": # 2진수의 각 자리수의 결과 비교
answer += " "
else:
answer += "#"
answers.append(answer)
return answers
import sys
def change_ord(char): # 문자를 숫자로 출력하는 함수
return ord(char) - 55
value, numeral = sys.stdin.readline().split() # 입력
sum = 0 # 합계를 저장할 빈 변수
for i in range(len(value)):
try: # 현재 문자인 value[i]가 숫자로 변환이 되면 그대로 진행
sum += int(value[i]) * (int(numeral) ** (len(value) - i - 1))
except: # 변환이 되지 않으면 위에서 정의한 함수를 사용해 숫자로 변환
sum += change_ord(value[i]) * (int(numeral) ** (len(value) - i - 1))
print(sum)
거의 두 달만에 알고리즘 문제를 풀어보는 것 같다. 이것저것 시험보느라... 결과는 1승 1패가 예상되는데 아쉽다.
문제에서 마지막 입력에 0을 준다고 하는 것을 보니 전부 입력받고 -> 처리해서 -> 출력하는게 아니라
입력받을 때마다 처리하고 출력하는 작업을 반복하고 0이 입력되면 멈추라고 하는 것 같다.
팩토리얼은 math모듈에 구현되어 있지만 최대 길이가 5자리라고 해서 미리 계산해서 리스트로 만들었다.
import sys
fac = [120, 24, 6, 2, 1] # 길이가 최대 5자리이니 매번 계산하지 않고 미리 계산
while (True): # 탈출 조건이 없다면 무한 반복
input = sys.stdin.readline().strip() # 입력
if input[0] == '0': # 마지막 입력인 0이 들어오면 반복문 탈출
break
sum = 0 # 합계를 저장할 빈 변수 생성
for i in range(len(input)): # 받아온 입력의 자리수만큼 반복
sum += int(input[i]) * fac[i - len(input)] # 현재 자리의 수 * 해당 위치의 팩토리얼 값
print(sum)
import sys
# 입력값 넘겨받기
n = int(sys.stdin.readline())
value_n = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
value_m = list(map(int, sys.stdin.readline().split()))
# 개수세기 - 완전탐색 -> 시간초과로 실패
count = [0] * m
value_n.sort()
for i in range(m):
for j in range(n):
if value_m[i] == value_n[j]:
count[i] += 1
if value_m[i] < value_n[j]:
break
# 출력
for x in count:
sys.stdout.write(str(x) + " ")
최대한 시간을 줄이기 위해 sort도 해보고 입력 출력구문도 바꿔보았지만 최종적으로 실패했다.
dict를 이용한 2개의 for문
import sys
# 입력값 넘겨받기
n = int(sys.stdin.readline())
value_n = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
value_m = list(map(int, sys.stdin.readline().split()))
# 개수세기 - 딕셔너리에 해당 숫자를 가진 개수를 누적 COUNT해서 조회만 함
count = {}
for i in range(n):
try:
count[value_n[i]] += 1
except:
count[value_n[i]] = 1
for j in range(m):
try:
sys.stdout.write(str(count[value_m[j]]) + " ")
except:
sys.stdout.write(str(0) + " ")
count[value_n[i]]를 if문으로 확인하는 방법이 잘 안됐지만 결과적으로 이게 더 편한것 같다.
numbers로 만들 수 있는 숫자의 조합을 만들기 위해 재귀함수를 만들어보려고 했으나 실패했다.
순열로 경우의 수를 만들려고 방법을 찾아보니 itertools라는 내장 모듈이 있어서 사용했다.
itertools를 이용해 모든 자리 수에 해당하는 순열을 만들고 set으로 중복을 제거했다.
이후 소수판별은 2부터 해당 숫자전까지 순서대로 나눠서 나머지가 생기면 소수가 아닌 것으로 판별했다.
import itertools as iter
def solution(numbers):
answer = 0
cases = set([]) # numbers로 만들 수 있는 모든 숫자의 조합을 저장할 set(중복 제거할려고 set 씀)
# 순열을 이용해 모든 경우의 수를 만들어 set에 저장
for i in range(len(numbers)):
for j in list(map(''.join, iter.permutations(numbers, i + 1))):
cases.add(int(j))
# 소수판별 2와 3이상으로 구분
for x in cases:
if x == 2:
answer += 1
elif x > 2:
check = 0
# 나머지가 0이면 약수가 존재하므로 소수가 아니다
for y in range(2, x):
if x % y == 0:
check = 1
break
if check == 0:
answer += 1
return answer
조금 더 보완하자면 for y in range(2, x) 부분을
for y in range(2, round(x ** 0.5) + 1)로 고치면 조금 더 빠르다.
현재 다리 위에 어느 시점에 진입한 어떤 트럭이 있는지 저장하는 리스트를 만들어서 풀면 될 듯하다.
1. 현재 다리 위에 있는 트럭의 존재 여부 확인
Yes : 현재 시간과 진입 시간을 비교해서 다리 길이만큼 있었다면 다리를 탈출, 있지 않았다면 아직 다리 위
No : 행동없음
2. 진입 대기 중인 트럭의 존재 여부 확인
Yes : 현재 다리 위에 있는 트럭들의 무게와 진입 대기 중인 트럭의 무게를 합한 후
다리가 버틸 수 있는 중량과 비교하여 다리에 올릴지 말지 결정
No : 행동없음
3. 무한 반복 후 진입 대기 중인 트럭과 다리 위에 있는 트럭이 없다면 반복 종료
def solution(bridge_length, weight, truck_weights):
time = 0 # 몇번 반복했는지 확인
bridge_truck = [] # 다리에 진입한 트럭의 진입시점과 무게를 저장
while True:
if bridge_truck: # 1. 현재 다리 위에 있는 트럭의 존재 여부 확인
if (time - bridge_truck[0][0]) == bridge_length: # 현재 시간과 진입 시간을 비교
bridge_truck.pop(0) # 다리 길이만큼 있었다면 다리에서 탈출
if truck_weights: # 2. 진입 대기 중인 트럭의 존재 여부 확인
# 현재 다리 위에 있는 트럭들의 무게와 진입 대기 중인 트럭의 무게를 합한 후 다리가 버틸 수 있는 중량과 비교
if sum(i[1] for i in bridge_truck) + truck_weights[0] <= weight:
bridge_truck.append((time, truck_weights.pop(0))) # 버틸 수 있다면 다리에 진입
time += 1 # 시간 경과
if truck_weights or bridge_truck: # 진입 대기 중인 트럭과 다리 위에 있는 트럭의 존재여부 확인
pass
else:
break # 둘 다 비어있다면 반복종료
return time
앞에 데이터가 빠지기 전에 뒤에 데이터는 빠질 수 없으므로 큐를 응용해서 풀면 될 것같다.
1. progresses의 각각의 값에 대응하는 speeds의 값을 더 한다.
2. progesses의 0번째 값이 100을 넘었는가? Yes면 큐에서 내보내고 질문을 반복, No면 1번을 반복한다.
이 때 Yes가 몇 번인지 카운트한다.
3. count한 Yes의 횟수를 answer에 append한다.
4. 큐가 빌 때까지 반복
을 구현한다.
def solution(progresses, speeds):
answer = []
while progresses: # 4. 반복
count = 0
for i in range(len(progresses)): # 1. progresses의 각각의 값에 대응하는 speeds의 값을 더 한다.
progresses[i] += speeds[i]
for j in range(len(progresses)): # 2. progesses의 0번째 값이 100을 넘었는가?
if progresses[0] >= 100: # Yes면 큐에서 내보내고 질문을 반복, 반복횟수 count
count += 1
progresses.pop(0)
speeds.pop(0) # speeds를 같이 내보내야 1번이 제대로 돌아감
else:
break # No면 반복종료
if count != 0:
answer.append(count) # count한 Yes의 횟수를 answer에 append한다.
return answer
def solution(prices):
length = len(prices)
answer = [0] * length
stack = [0] # 스택이 비었는지 확인하는 if문을 for문에 넣기 싫어서 첫 index를 미리 넣어둠
for i in range(1, length): # index 0은 이미 stack에 있으므로 1부터 range를 돌림
if prices[stack[-1]] < prices[i]: # stack의 마지막 index의 price값과 현재 price값을 비교
stack.append(i)
else:
while prices[stack[-1]] > prices[i]: # stack의 마지막 index의 price값과 현재 price값을 비교
answer[stack[-1]] = i - stack[-1] # index의 차이가 answer에 들어감
stack.pop()
else:
stack.append(i) # while문이 끝나면 index를 다시 넣음
# stack에 남은 애들 처리
for i in stack:
answer[i] = length - i - 1
return answer
이렇게 돌렸는데 테스트 케이스는 통과하고 나머지는 런타임에러가 나왔다.
런타임에러에 대해 한참 찾아봤는데 모르겠어서 while문을 for문으로 바꿔보았다.
def solution(prices):
answer = [0] * len(prices)
stack = [0]
for i in range(1, len(prices)):
if prices[stack[-1]] < prices[i]:
stack.append(i)
else:
for j in range(len(stack)): # while에서 True, False로 반복한 부분을
if prices[stack[-1]] > prices[i]: # for와 if로 나눴다.
answer[stack[-1]] = i - stack[-1]
stack.pop()
stack.append(i)
for i in stack:
answer[i] = len(prices) - i - 1
return answer
...? while에서 True, False로 반복을 수행한 부분을 for, if로 나눴더니 통과되었다.
