1713. 후보 추천하기
문제
월드초등학교 학생회장 후보는 일정 기간 동안 전체 학생의 추천에 의하여 정해진 수만큼 선정된다. 그래서 학교 홈페이지에 추천받은 학생의 사진을 게시할 수 있는 사진틀을 후보의 수만큼 만들었다. 추천받은 학생의 사진을 사진틀에 게시하고 추천받은 횟수를 표시하는 규칙은 다음과 같다.
학생들이 추천을 시작하기 전에 모든 사진틀은 비어있다.
어떤 학생이 특정 학생을 추천하면, 추천받은 학생의 사진이 반드시 사진틀에 게시되어야 한다.
비어있는 사진틀이 없는 경우에는 현재까지 추천 받은 횟수가 가장 적은 학생의 사진을 삭제하고, 그 자리에 새롭게 추천받은 학생의 사진을 게시한다. 이때, 현재까지 추천 받은 횟수가 가장 적은 학생이 두 명 이상일 경우에는 그러한 학생들 중 게시된 지 가장 오래된 사진을 삭제한다.
현재 사진이 게시된 학생이 다른 학생의 추천을 받은 경우에는 추천받은 횟수만 증가시킨다.
사진틀에 게시된 사진이 삭제되는 경우에는 해당 학생이 추천받은 횟수는 0으로 바뀐다.
후보의 수 즉, 사진틀의 개수와 전체 학생의 추천 결과가 추천받은 순서대로 주어졌을 때, 최종 후보가 누구인지 결정하는 프로그램을 작성하시오.
입력
첫째 줄에는 사진틀의 개수 N이 주어진다. (1 ≤ N ≤ 20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대로 주어진다. 총 추천 횟수는 1,000번 이하이며 학생을 나타내는 번호는 1부터 100까지의 자연수이다.
출력
사진틀에 사진이 게재된 최종 후보의 학생 번호를 증가하는 순서대로 출력한다.
예제 입력 1
3\
9\
2 1 4 3 5 6 2 7 2
예제 출력 1
2 6 7
알고리즘 분류
- 구현
- 시뮬레이션
풀이
- 3개 이상일 때
- 순서체크 -> 큐 사용 (선입선출)
- 인덱싱체크
[예시]
- 214
- 314
- 354
- 356
- 256
- 276
코드
N = int(input())
M = int(input())
student = list(map(int, input().split()))
photo = dict()
for i in range(M):
if student[i] in photo: # 딕셔너리에 이미 사진이 있을 때
photo[student[i]][0] += 1 # 해당 후보의 추천수에 1을 카운팅 해준다.
else: # 딕셔너리에 사진이 없을 때
if len(photo) < N: # 딕셔너리에 N개 사진이 다 차있지 않으면
photo[student[i]] = [1, i] # [추천수, 들어온 순서]
else:
# 추천수대로 오름차순 정렬하고, 들어온 순서대로 오름차순 정렬한다.
del_list = sorted(photo.items(), key= lambda x : (x[1][0], x[1][1]))
del_key = del_list[0][0] # 가장 작은 값 삭제
del(photo[del_key])
photo[student[i]] = [1, i] # 새 값 할당
ans_list = list(sorted(photo.keys())) # key 값 기준으로 오름차순 정렬
answer = str(ans_list[0]) # 키값만 변환하여 저장
for i in ans_list[1: ] :
answer += " " + str(i)
print(answer)1669. 멍멍이 쓰다듬기
문제
동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다 오늘도 어김없이 그의 영원한 라이벌 멍멍이를 만나게 되었다. 원숭이는 멍멍이를 쓰다듬고 싶었다. 하지만 원숭이는 멍멍이보다 키가 작기 때문에 멍멍이를 쓰다듬어줄 수 없다. 원숭이가 멍멍이를 쓰다듬으려면 둘의 키가 같아야 하기 때문이다.
그래서 원숭이는 그 날부터 자신의 키를 조절하기로 마음먹었다. 원숭이는 초능력자이기 때문에 마음대로 키를 늘릴 수 있다. 하지만 안타깝게도 사람이 아니라 동물이기 때문에 하루에 늘릴 수 있는 키의 양을 1cm밖에 조절할 수 없다. 예를 들어 오늘 키를 5cm 만큼 늘렸다면, 내일은 키를 4cm, 5cm, 6cm 중 하나만큼 키를 늘릴 수 있다는 뜻이다. 늘릴 수 있는 키의 양은 음수가 될 수 없다. 그리고 첫째 날과 마지막 날에는 무조건 1cm 만큼 늘릴 수 있다.
현재 원숭이와 멍멍이의 키가 주어졌을 때, 원숭이가 매일 키를 늘려서 멍멍이와 키가 같아지는 최소의 일수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 원숭이의 키 X와 멍멍이의 키 Y가 주어진다. X, Y는 0 ≤ X ≤ Y < 231을 만족하는 정수이다.
출력
첫째 줄에 원숭이가 멍멍이의 키와 같아지게 되는 최소의 일수를 출력한다.
예제 입력 1
45 49
예제 출력 1
3
예제 입력 2
45 50
예제 출력 2
4
알고리즘 분류
- 수학
- 늘릴 수 있는 키의 범위: -1, 0, +1
- 키가 같아지는 최소일수
- 처음과 끝은 무조건 +1 -> 대칭
- 계단식 모양의 조건: 제곱수 -> 최소 일 수: 2 x N - 1
[예시]
- 1 1 1
- 1 2 1
- 1 2 1 1
- 1 2 2 1
- 1 2 2 1 1
- 1 2 2 2 1
- 1 2 3 2 1
- 1 2 3 2 1 1
코드
X, Y = map(int, input().split())
if X == Y: # 키가 같을 때 0 출력
print(0)
else:
n = int((Y - X) ** 0.5)
if n ** 2 == Y - X: # n 이 제곱수일 때
print(2 * n - 1)
else: # n 이 제곱수가 아닐때
z = (Y - X) - n ** 2 # 원숭이와 강아지 키 차이에서 제곱수 만큼 뺀값
if z <= n: # 남는 수가 키차이보다 작다면
print(2 * n)
else: # 남는 수가 키차이보다 크다면
print(2 * n + 1)
14002. 가장 긴 증가하는 부분 수열 4
문제
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)
출력
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다. 그러한 수열이 여러가지인 경우 아무거나 출력한다.
예제 입력 1
6\
10 20 10 30 20 50
예제 출력 1
4\
10 20 30 50
알고리즘 분류
- 다이나믹 프로그래밍
코드
N = int(input())
num = list(map(int, input().split()))
dp = [1]*N
for i in range(1, N): # 리스트 만큼 순환
for j in range(i): # 키값과 비교할 값 j
if num[i]>num[j]: # 선행값이 후행값보다 클 때
dp[i] = max(dp[i], dp[j]+1) # 조건이 만족하면 dp에 1씩 카운팅한다.
print(max(dp)) # 가장 긴 부분수열의 길이 출력
order = max(dp)
arr = []
for i in range(N-1, -1, -1): # 리스트를 반대로 순환
if dp[i]==order: # 해당 부분수열일 때
arr.append(num[i]) # arr에 값 저장
order-=1 # order 값을 하나씩 줄여 순차 탐색
arr.reverse()
for i in arr:
print(i, end=' ')