남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 차가 최소가 되게 하려 한다.
통나무 건너뛰기의 난이도는 인접한 두 통나무 간의 높이의 차의 최댓값으로 결정된다. 높이가 {2, 4, 5, 7, 9}인 통나무들을 세우려 한다고 가정하자. 이를 [2, 9, 7, 4, 5]의 순서로 세웠다면, 가장 첫 통나무와 가장 마지막 통나무 역시 인접해 있다. 즉, 높이가 2인 것과 높이가 5인 것도 서로 인접해 있다. 배열 [2, 9, 7, 4, 5]의 난이도는 |2-9| = 7이다. 우리는 더 나은 배열 [2, 5, 9, 7, 4]를 만들 수 있으며 이 배열의 난이도는 |5-9| = 4이다. 이 배열보다 난이도가 낮은 배열은 만들 수 없으므로 이 배열이 남규가 찾는 답이 된다.
입력
입력은 T개의 테스트 케이스로 이루어져 있다. 첫 줄에 T가 주어진다.
이어지는 각 줄마다 첫 줄에 통나무의 개수를 나타내는 정수 N(5 ≤ N ≤ 10,000), 둘째 줄에 각 통나무의 높이를 나타내는 정수 Li가 주어진다. (1 ≤ Li ≤ 100,000)
문자열로 구성된 리스트 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”] 입니다.
연세대학교 수강신청이 얼마 전부터 바뀌어, 마일리지 제도로 바뀌었다. 이 제도는 각각의 학생들에게 마일리지를 주어 듣고 싶은 과목에 마일리지를 과목당 1~36을 분배한다. 그리고 모두 분배가 끝이 나면 과목에 대해서 마일리지를 많이 투자한 순으로 그 과목의 수강인원만큼 신청되는 방식이다.
성준이는 연세대학교 재학 중인 학생이다. 성준이는 저번 수강신청에서 실패하여 휴학을 했기 때문에 이번 수강신청만은 필사적으로 성공하려고 한다. 그래서 성준이는 학교 홈페이지를 뚫어버렸다.
그 덕분에 다른 사람들이 신청한 마일리지를 볼 수 있게 되었다. 성준이는 주어진 마일리지로 최대한 많은 과목을 신청하고 싶어 한다. (내가 마일리지를 넣고 이후에 과목을 신청하는 사람은 없다) 마일리지는 한 과목에 1에서 36까지 넣을 수 있다.
입력
첫째 줄에는 과목 수 n (1 ≤ n ≤ 100)과 주어진 마일리지 m (1 ≤ m ≤ 100)이 주어진다. 각 과목마다 2줄의 입력이 주어지는데 첫째 줄에는 각 과목에 신청한 사람 수 Pi과 과목의 수강인원 Li이 주어지고 그 다음 줄에는 각 사람이 마일리지를 얼마나 넣었는지 주어진다. (1 ≤ Pi ≤100, 1 ≤ Li ≤ 100)
N, M = map(int, input().split()) answer = 0 sugang = []
for _ inrange(N): P, L = map(int, input().split()) mileages = list(map(int, input().split())) heapq.heapify(mileages)
available = L - P if available > 0: heapq.heappush(sugang, 1) else: for i inrange(abs(available)): heapq.heappop(mileages) heapq.heappush(sugang, heapq.heappop(mileages))
count = 0 while sugang: sugang_mileage = heapq.heappop(sugang) if M - sugang_mileage >= 0: M -= sugang_mileage count += 1 else: break print(count)
M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다. 행성의 크기를 알고 있을때, 균등한 우주의 쌍이 몇 개인지 구해보려고 한다. 구성이 같은데 순서만 다른 우주의 쌍은 한 번만 센다.
두 우주 A와 B가 있고, 우주 A에 있는 행성의 크기는 A1, A2, …, AN, 우주 B에 있는 행성의 크기는 B1, B2, …, BN라고 하자. 두 우주의 행성 크기가 모든 1 ≤ i, j ≤ N에 대해서 아래와 같은 조건을 만족한다면, 두 우주를 균등하다고 한다.
Ai < Aj → Bi < Bj
Ai = Aj → Bi = Bj
Ai > Aj → Bi > Bj
입력
첫째 줄에 우주의 개수 M과 각 우주에 있는 행성의 개수 N이 주어진다. 둘째 줄부터 M개의 줄에 공백으로 구분된 행성의 크기가 한 줄에 하나씩 1번 우주부터 차례대로 주어진다.
space_list = [list(map(int, input().split())) for _ inrange(M)]
new_space_list = [[] for _ inrange(M)] dictionary = {} for i inrange(M): new_list = sorted(list(set(space_list[i]))) for j inrange(len(new_list)): dictionary[new_list[j]] = j for x in (space_list[i]): new_space_list[i].append(dictionary[x])
new_space_list.sort() cnt, ans = 1, 0 for i inrange(1, M): if new_space_list[i] == new_space_list[i - 1]: cnt += 1 else: ans += cnt * (cnt - 1) // 2 cnt = 1
M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다. 행성의 크기를 알고 있을때, 균등한 우주의 쌍이 몇 개인지 구해보려고 한다. 구성이 같은데 순서만 다른 우주의 쌍은 한 번만 센다.
두 우주 A와 B가 있고, 우주 A에 있는 행성의 크기는 A1, A2, …, AN, 우주 B에 있는 행성의 크기는 B1, B2, …, BN라고 하자. 두 우주의 행성 크기가 모든 1 ≤ i, j ≤ N에 대해서 아래와 같은 조건을 만족한다면, 두 우주를 균등하다고 한다.
Ai < Aj → Bi < Bj
Ai = Aj → Bi = Bj
Ai > Aj → Bi > Bj
입력
첫째 줄에 우주의 개수 M과 각 우주에 있는 행성의 개수 N이 주어진다. 둘째 줄부터 M개의 줄에 공백으로 구분된 행성의 크기가 한 줄에 하나씩 1번 우주부터 차례대로 주어진다.
space_list = [list(map(int, input().split())) for _ inrange(M)]
new_space_list = [[] for _ inrange(M)] dictionary = {} for i inrange(M): new_list = sorted(list(set(space_list[i]))) for j inrange(len(new_list)): dictionary[new_list[j]] = j for x in (space_list[i]): new_space_list[i].append(dictionary[x])
count = 0 for i inrange(M - 1): for j inrange(i + 1, M): if new_space_list[i] == new_space_list[j]: count += 1
![[백준] 1449번 수리공 항승](/images/posts/thumb/baekjoon.png)
![[프로그래머스] 문자열 내 마음대로 정렬하기](/images/posts/thumb/programmers.png)