20200407 알고리즘
1. 주식가격
문제 설명
초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.
제한사항
- prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
- prices의 길이는 2 이상 100,000 이하입니다.
입출력 예
| prices | return |
|---|---|
| [1, 2, 3, 2, 3] | [4, 3, 1, 1, 0] |
입출력 예 설명
- 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
- 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
- 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
- 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
- 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.
Solution1 ( 시간복잡도 O(n) )
def solution(prices):
size = len(prices)
stack = list()
answer = [0] * size
for i in range(size):
while stack and prices[stack[-1]] > prices[i]:
j = stack.pop()
answer[j] = i - j
stack.append(i)
while stack:
i = stack.pop()
answer[i] = size - (i + 1)
return answerSolution2 ( 시간복잡도 O(n2) )
문제의 조건에서 prices길이는 최대 10만개 이다. 따라서 n2으로 절~대 풀면 안된다 ( 10만 x 10만 => worst case 100초 )
def solution(prices):
size = len(prices)
answer = [0] * size
for i in range(size):
for j in range(i+1, size):
if prices[i] > prices[j]:
answer[i] = j - i
break
else:
answer[i] = size - (i + 1)
return answer2. 최솟값 만들기
문제 설명
길이가 같은 배열 A, B 두개가 있습니다. 각 배열은 자연수로 이루어져 있습니다. 배열 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱합니다. 이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱한 값을 누적하여 더합니다. 이때 최종적으로 누적된 값이 최소가 되도록 만드는 것이 목표입니다. (단, 각 배열에서 k번째 숫자를 뽑았다면 다음에 k번째 숫자는 다시 뽑을 수 없습니다.)
예를 들어 A = [1, 4, 2] , B = [5, 4, 4] 라면
- A에서 첫번째 숫자인 1, B에서 두번째 숫자인 5를 뽑아 곱하여 더합니다. (누적된 값 : 0 + 5(1x5) = 5)
- A에서 두번째 숫자인 4, B에서 세번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 5 + 16(4x4) = 21)
- A에서 세번째 숫자인 2, B에서 첫번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 21 + 8(2x4) = 29)
즉, 이 경우가 최소가 되므로 29를 return 합니다.
배열 A, B가 주어질 때 최종적으로 누적된 최솟값을 return 하는 solution 함수를 완성해 주세요.
제한사항
- 배열 A, B의 크기 : 1,000 이하의 자연수
- 배열 A, B의 원소의 크기 : 1,000 이하의 자연수
입출력 예
| A | B | answer |
|---|---|---|
| [1, 4, 2] | [5, 4, 4] | 29 |
| [1,2] | [3,4] | 10 |
입출력 예 설명
입출력 예 #1 문제의 예시와 같습니다.
입출력 예 #2 A에서 첫번째 숫자인 1, B에서 두번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 4) 다음, A에서 두번째 숫자인 2, B에서 첫번째 숫자인 3을 뽑아 곱하여 더합니다. (누적된 값 : 4 + 6 = 10) 이 경우가 최소이므로 10을 return 합니다.
Solution
def solution(A,B):
A.sort()
B.sort(reverse=True)
answer = 0
for i in range(len(A)):
answer += A[i] * B[i]
return answerN2 연산을 할 필요 없다!
3. 토마토
현수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림 과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.
창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향 에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토 가 혼자 저절로 익는 경우는 없다고 가정한다. 현수는 창고에 보관된 토마토들이 며칠이 지나 면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.
토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들 의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로 그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.
▣ 입력설명 첫 줄에는 상자의 크기를 나타내는 두 정수 M, N이 주어진다. M은 상자의 가로 칸의 수, N 은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M, N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄 에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토 의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.
▣ 출력설명 여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.
▣ 입력예제 1
6 4
0 0 -1 0 0 0
0 0 1 0 -1 0
0 0 -1 0 0 0
0 0 0 0 -1 1▣ 출력예제 1 4
Solution
import sys
from collections import deque
sys.stdin = open("input74.txt", "rt")
# 매 체크마다 board를 순회하며 0이 모두 1인지 체크하는건 n2 비효율 worst case > 0.1초
# 1이 하나도 없는 case, 0이 있지만 탐색 못하는 case, -1만 이루어진 case 등 생각
if __name__ == '__main__':
m, n = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
ch = [[0]*m for _ in range(n)]
res = 0
cnt = 0 # 바꿔야하는 감의 수
dQ = deque()
dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]
for y in range(n):
for x in range(m):
if board[y][x] == 0:
cnt += 1
elif board[y][x] == 1:
dQ.append((x,y))
if cnt == 0:
if len(dQ) == 0:
print(-1) # 모두 빈 공간
else:
print(0) # 애초에 모두 1
else:
while cnt > 0 and dQ:
for _ in range(len(dQ)):
x, y = dQ.popleft()
for i in range(4):
xx = x + dx[i]
yy = y + dy[i]
if 0 <= xx < m and 0 <= yy < n and ch[yy][xx] == 0 and board[yy][xx] == 0:
cnt -= 1
dQ.append((xx, yy))
ch[yy][xx] = 1
res += 1
if cnt > 0:
print(-1)
else:
print(res)Solution2
import sys
from collections import deque
sys.stdin = open("review_input.txt", "rt")
if __name__ == '__main__':
m, n = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
dis = [[0] * m for _ in range(n)]
dQ = deque()
dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]
cnt = 0
result = 0
for y in range(n):
for x in range(m):
if board[y][x] == 1:
dQ.append((x,y))
elif board[y][x] == 0:
cnt += 1
if cnt == 0:
if not dQ:
print(-1)
else:
print(0)
else:
while dQ:
tmp = dQ.popleft()
for k in range(4):
xx = tmp[0] + dx[k]
yy = tmp[1] + dy[k]
if 0 <= xx < m and 0 <= yy < n and board[yy][xx] == 0:
board[yy][xx] = 1
dis[yy][xx] = dis[tmp[1]][tmp[0]] + 1
dQ.append((xx, yy))
cnt -= 1
if cnt > 0:
print(-1)
else:
for y in range(n):
for x in range(m):
if dis[y][x] > result:
result = dis[y][x]
print(result)4. 소트인사이드
형변환 안쓰기
배열을 정렬하는 것은 쉽다. 수가 주어지면, 그 수의 각 자리수를 내림차순으로 정렬해보자.
- 입력
첫째 줄에 정렬하고자하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 정수이다.
- 출력
첫째 줄에 자리수를 내림차순으로 정렬한 수를 출력한다.
- 예제입력
2143- 예제출력
4321Solution
if __name__ == '__main__':
n = int(input())
if -2**31 > n or n > 2**31-1:
print(0)
else:
flag = False
if n < 0:
flag = True
n *= -1
tmp = list()
while n > 0:
tmp.append(n%10)
n //= 10
tmp.sort(reverse=True)
res = 0
for i in range(len(tmp)):
res = res * 10 + tmp[i]
if flag:
print(res*-1)
else:
print(res)5. 사다리 타기
현수와 친구들은 과자를 사먹기 위해 사다리 타기를 합니다. 사다리 표현은 2차원 평면은 0으 로 채워지고, 사다리는 1로 표현합니다. 현수는 특정도착지점으로 도착하기 위해서는 몇 번째 열에서 출발해야 하는지 알고싶습니다. 특정 도착지점은 2로 표기됩니다. 여러분이 도와주세 요. 사다리의 지도가 10*10이면
특정목적지인 2에 도착하려면 7번 열 출발지에서 출발하면 됩니다.
▣ 입력설명 10*10의 사다리 지도가 주어집니다.
▣ 출력설명 출발지 열 번호를 출력하세요.
▣ 입력예제 1
1 0 1 0 0 1 0 1 0 1
1 0 1 1 1 1 0 1 0 1
1 0 1 0 0 1 0 1 0 1
1 0 1 0 0 1 0 1 1 1
1 0 1 0 0 1 0 1 0 1
1 0 1 1 1 1 0 1 0 1
1 0 1 0 0 1 0 1 1 1
1 1 1 0 0 1 0 1 0 1
1 0 1 0 0 1 1 1 0 1
1 0 1 0 0 2 0 1 0 1▣ 출력예제 1
7
Solution
import sys
sys.stdin = open("input92.txt", "rt")
def DFS(x, y):
ch[y][x] = 1
if y == 0:
print(x)
else:
if x-1 >= 0 and board[y][x-1] == 1 and ch[y][x-1] == 0:
DFS(x-1, y)
elif x+1 < 10 and board[y][x+1] == 1 and ch[y][x+1] == 0:
DFS(x+1, y)
else:
DFS(x, y-1)
if __name__ == '__main__':
board = [list(map(int, input().split())) for _ in range(10)]
ch = [[0] * 10 for _ in range(10)]
for i in range(10):
if board[9][i] == 2:
DFS(i, 9)Solution2 ( 안좋은 방법)
import sys
sys.stdin = open("input92.txt", "rt")
def DFS(x, y):
if y == 9:
if board[y][x] == 2:
print(res)
sys.exit(0)
return
else:
flag = False
for k in [-1, 1]:
xx = x + k
if 0 <= xx < 10:
if board[y][xx] != 0 and ch[y][xx] == 0:
flag = True
ch[y][xx] = 1
DFS(xx, y)
ch[y][xx] = 0
if not flag:
if y < 9 and board[y+1][x] != 0:
ch[y+1][x] = 1
DFS(x, y+1)
ch[y+1][x] = 0
if __name__ == '__main__':
board = [list(map(int, input().split())) for _ in range(10)]
ch = [[0] * 10 for _ in range(10)]
res = 0
for i in range(10):
if board[0][i] == 1:
res = i
ch[1][i] = 1
DFS(i, 1) # 한칸 앞 부터
ch[1][i] = 0
![[HongDongUk]](/static/a60d793d17c3aad0361c9192a3b51381/a12fc/profile.png)