20200302 알고리즘
1. 문자열 내 마음대로 정렬하기
출처: 프로그래머스
문제 설명
문자열로 구성된 리스트 strings와, 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬하려 합니다. 예를 들어 strings가 [sun, bed, car]이고 n이 1이면 각 단어의 인덱스 1의 문자 u, e, a로 strings를 정렬합니다.
제한 조건
- strings는 길이 1 이상, 50이하인 배열입니다.
- strings의 원소는 소문자 알파벳으로 이루어져 있습니다.
- strings의 원소는 길이 1 이상, 100이하인 문자열입니다.
- 모든 strings의 원소의 길이는 n보다 큽니다.
- 인덱스 1의 문자가 같은 문자열이 여럿 일 경우, 사전순으로 앞선 문자열이 앞쪽에 위치합니다.
입출력 예
| strings | n | return |
|---|---|---|
| [sun, bed, car] | 1 | [car, bed, sun] |
| [abce, abcd, cdx] | 2 | [abcd, abce, cdx] |
입출력 예 설명
입출력 예 1 sun, bed, car의 1번째 인덱스 값은 각각 u, e, a 입니다. 이를 기준으로 strings를 정렬하면 [car, bed, sun] 입니다.
입출력 예 2 abce와 abcd, cdx의 2번째 인덱스 값은 c, c, x입니다. 따라서 정렬 후에는 cdx가 가장 뒤에 위치합니다. abce와 abcd는 사전순으로 정렬하면 abcd가 우선하므로, 답은 [abcd, abce, cdx] 입니다.
Solution1
def solution(strings, n):
def sortKey(x):
return x[n]
return sorted(sorted(strings), key=sortKey)Solution2
def solution(strings, n):
return sorted(sorted(strings), key=lambda x:x[n])sort() : 시간복잡도는 nlogn == 퀵소트 시간복잡도
2. 격자판 최대합
5*5 격자판에 아래롸 같이 숫자가 적혀있습니다.
N*N의 격자판이 주어지면 각 행의 합, 각 열의 합, 두 대각선의 합 중 가 장 큰 합을 출력합 니다.
▣ 입력설명 첫 줄에 자연수 N이 주어진다.(1<=N<=50) 두 번째 줄부터 N줄에 걸쳐 각 줄에 N개의 자연수가 주어진다. 각 자연수는 100을 넘지 않는 다.
▣ 출력설명 최대합을 출력합니다.
▣ 입력예제 1
5
10 13 10 12 15
12 39 30 23 11
11 25 50 53 15
19 27 29 37 27
19 13 30 13 19▣ 출력예제 1
155
Solution
import sys
sys.stdin = open("input16.txt", "rt")
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
max = -2147000000
for y in range(n):
tot1 = tot2 = 0
for x in range(n):
tot1 += a[y][x]
tot2 += a[x][y]
if tot1 > max:
max = tot1
if tot2 > max:
max = tot2
tot3 = tot4 = 0
for x in range(n):
tot3 += a[x][x]
tot4 += a[n-x-1][x]
if tot3 > max:
max = tot3
if tot4 > max:
max = tot4
print(max)3. 사과나무(다이아몬드)
현수의 농장은 N*N 격자판으로 이루어져 있으며, 각 격자안에는 한 그루의 사과나무가 심어저 있다. N의 크기는 항상 홀수이다. 가을이 되어 사과를 수확해야 하는데 현수는 격자판안의 사 과를 수확할 때 다이아몬드 모양의 격자판만 수확하고 나머지 격자안의 사과는 새들을 위해서 남겨놓는다.
만약 N이 5이면 아래 그림과 같이 진한 부분의 사과를 수확한다.
현수과 수확하는 사과의 총 개수를 출력하세요.
▣ 입력설명 첫 줄에 자연수 N(홀수)이 주어진다.(3<=N<=20) 두 번째 줄부터 N줄에 걸쳐 각 줄에 N개의 자연수가 주어진다. 이 자연수는 각 격자안에 있는 사과나무에 열린 사과의 개수이다. 각 격자안의 사과의 개수는 100을 넘지 않는다.
▣ 출력설명 수확한 사과의 총 개수를 출력합니다.
▣ 입력예제 1
5
10 13 10 12 15
12 39 30 23 11
11 25 50 53 15
19 27 29 37 27
19 13 30 13 19▣ 출력예제 1
379
Solution
import sys
sys.stdin = open("input17.txt", "rt")
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
s = e = n//2
tot = 0
for i in range(n):
for j in range(s, e+1):
tot += a[i][j]
if i < n//2:
s -= 1
e += 1
else:
s += 1
e -= 1
print(tot)4. 곳감(모래시계)
현수는 곳감을 만들기 위해 감을 깍아 마당에 말리고 있습니다. 현수의 마당은 N*N 격자판으 로 이루어져 있으며, 현수는 각 격자단위로 말리는 감의 수를 정합니다. 그런데 해의 위치에 따라 특정위치의 감은 잘 마르지 않습니다. 그래서 현수는 격자의 행을 기준으로 왼쪽, 또는 오른쪽으로 회전시켜 위치를 변경해 모든 감이 잘 마르게 합니다.
만약 회전명령 정보가 2 0 3이면 2번째 행을 왼쪽으로 3만큼 아래 그림처럼 회전시키는 명령 입니다.
첫 번째 수는 행번호, 두 번째 수는 방향인데 0이면 왼쪽, 1이면 오른쪽이고, 세 번째 수는 회 전하는 격자의 수입니다. M개의 회전명령을 실행하고 난 후 아래와 같이 마당의 모래시계 모양의 영역에는 감 이 총 몇 개가 있는지 출력하는 프로그램을 작성하세요.
▣ 입력설명 첫 줄에 자연수 N(3<=N<=20) 이 주어며, N은 홀수입니다. 두 번째 줄부터 N줄에 걸쳐 각 줄에 N개의 자연수가 주어진다. 이 자연수는 각 격자안에 있는 감의 개수이며, 각 격자안의 감의 개수는 100을 넘지 않는다. 그 다음 줄에 회전명령의 개수인 M(1<=M<=10)이 주어지고, 그 다음 줄부터 M개의 회전명령 정보가 M줄에 걸쳐 주어집니다.
▣ 출력설명 총 감의 개수를 출력합니다.
▣ 입력예제 1
5
10 13 10 12 15
12 39 30 23 11
11 25 50 53 15
19 27 29 37 27
19 13 30 13 19
3
2 0 3
5 1 2
3 1 4▣ 출력예제 1
362
Solution
import sys
sys.stdin = open("input18.txt", "rt")
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
t = int(input())
for _ in range(t):
num, direction, cnt = map(int, input().split())
if direction == 0:
for _ in range(cnt):
a[num-1].append(a[num-1].pop(0))
else:
for _ in range(cnt):
a[num-1].insert(0, a[num-1].pop())
s = 0
e = n-1
tot = 0
for i in range(n):
for j in range(s, e+1):
tot += a[i][j]
if i < n//2:
s += 1
e -= 1
else:
s -= 1
e += 1
print(tot)5. 봉우리
지도 정보가 N*N 격자판에 주어집니다. 각 격자에는 그 지역의 높이가 쓰여있습니다. 각 격자 판의 숫자 중 자신의 상하좌우 숫자보다 큰 숫자는 봉우리 지역입니다. 봉우리 지역이 몇 개 있는 지 알아내는 프로그램을 작성하세요. 격자의 가장자리는 0으로 초기화 되었다고 가정한다.
만약 N=5 이고, 격자판의 숫자가 다음과 같다면 봉우리의 개수는 10개입니다
▣ 입력설명 첫 줄에 자연수 N이 주어진다.(1<=N<=50) 두 번째 줄부터 N줄에 걸쳐 각 줄에 N개의 자연수가 주어진다. 각 자연수는 100을 넘지 않는 다.
▣ 출력설명 봉우리의 개수를 출력하세요.
▣ 입력예제 1
5
5 3 7 2 3
3 7 1 6 1
7 2 5 3 4
4 3 6 4 1
8 7 3 5 2▣ 출력예제 1
10
Solution
import sys
sys.stdin = open("input19.txt", "rt")
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
a.insert(0, [0]*n)
a.append([0]*n)
for t in a:
t.insert(0,0)
t.append(0)
cnt = 0
for i in range(1, n+1):
for j in range(1, n+1):
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
if all([a[i][j] > a[i+dx[k]][j+dy[k]] for k in range(4)]):
cnt += 1
print(cnt)
![[HongDongUk]](/static/a60d793d17c3aad0361c9192a3b51381/a12fc/profile.png)