코테 공부하기 1일차 (25.07.11)
ℹ️ 문제정보
- 문제 번호 : 1476
- 문제 이름 : 날짜 계산
- 난이도 : 실버 5
- 문제 링크 : https://www.acmicpc.net/problem/1476
📖 문제 요약
준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다.
지구를 나타내는 수를 E, 태양을 나타내는 수를 S, 달을 나타내는 수를 M이라고 했을 때, 이 세 수는 서로 다른 범위를 가진다. (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19)
우리가 알고있는 1년은 준규가 살고있는 나라에서는 1 1 1로 나타낼 수 있다. 1년이 지날 때마다, 세 수는 모두 1씩 증가한다. 만약, 어떤 수가 범위를 넘어가는 경우에는 1이 된다.
예를 들어, 15년은 15 15 15로 나타낼 수 있다. 하지만, 1년이 지나서 16년이 되면 16 16 16이 아니라 1 16 16이 된다. 이유는 1 ≤ E ≤ 15 라서 범위를 넘어가기 때문이다.
E, S, M이 주어졌고, 1년이 준규가 사는 나라에서 1 1 1일때, 준규가 사는 나라에서 E S M이 우리가 알고 있는 연도로 몇 년인지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 세 수 E, S, M이 주어진다. 문제에 나와있는 범위를 지키는 입력만 주어진다.
출력
첫째 줄에 E S M으로 표시되는 가장 빠른 연도를 출력한다. 1 1 1은 항상 1이기 때문에, 정답이 음수가 나오는 경우는 없다.
✨문제 분석 & 아이디어
1 ≤ E ≤ 15
1 ≤ S ≤ 28
1 ≤ M ≤ 19
E, S, M의 범위가 이와 같으므로
완전탐색을 이용할 경우 최대 15 * 28 * 19 = 7980번의 반복을 수행한다.
시간제한이 2초이기 때문에 완전탐색도 가능
📍풀이
입력이 E, S, M이라고 할 때, 다음 수식을 만족해야 한다.
15 * e + E = result
28 * s + S = result
19 * m + M = result
result - E는 15의 배수,
result - S는 28의 배수,
result - M은 19의 배수이므로 다음과 같은 조건식을 만들 수 있다.
if (result - E) % 15 == 0 and (result - S) % 28 == 0 and (result - M) % 19 == 0:
숫자 result를 1부터 위 조건을 만족할 때 까지 반복하면 정답을 찾을 수 있다.
import sys
input = sys.stdin.readline
E, S, M = map(int, input().split())
result = 1
while True:
if (result - E) % 15 == 0 and (result - S) % 28 == 0 and (result - M) % 19 == 0:
print(result)
break
result += 1ℹ️ 문제정보
- 문제 번호 : 2875
- 문제 이름 : 대회 or 인턴
- 난이도 : 브론즈 3
- 문제 링크 : https://www.acmicpc.net/problem/2875
📖 문제 요약
백준대학교에서는 대회에 나갈 때 2명의 여학생과 1명의 남학생이 팀을 결성해서 나가는 것이 원칙이다. (왜인지는 총장님께 여쭈어보는 것이 좋겠다.)
백준대학교는 뛰어난 인재들이 많아 올해에도 N명의 여학생과 M명의 남학생이 팀원을 찾고 있다. 대회에 참여하려는 학생들 중 K명은 반드시 인턴쉽 프로그램에 참여해야 한다. 인턴쉽에 참여하는 학생은 대회에 참여하지 못한다.
백준대학교에서는 뛰어난 인재들이 많기 때문에, 많은 팀을 만드는 것이 최선이다.
여러분은 여학생의 수 N, 남학생의 수 M, 인턴쉽에 참여해야하는 인원 K가 주어질 때 만들 수 있는 최대의 팀 수를 구하면 된다.
입력
첫째 줄에 N, M, K가 순서대로 주어진다. (0 ≤ M ≤ 100, 0 ≤ N ≤ 100, 0 ≤ K ≤ M+N),
출력
만들 수 있는 팀의 최대 개수을 출력하면 된다.
✨문제 분석 & 아이디어
2명의 여학생(N), 1명의 남학생(M)이 팀을 결성해 대회를 나가야 하고,
학생들 중 K명은 반드시 인턴십 프로그램에 참여해야 한다는 조건이 있다.
반복문을 이용해 해당 조건을 만족하지 않는다면 break하도록 코드를 작성한다.
우선 팀을 결성하고,
N -= 2
M -= 1
N 또는 M이 0보다 작거나, 남은 학생 수(N+M)이 K보다 작다면 break
그렇지 않다면 팀 수를 하나 증가시키는 방식으로 구현했다.
📍풀이
import sys
input = sys.stdin.readline
N, M, K = map(int, input().split())
team = 0
while True:
N -= 2
M -= 1
if N < 0 or M < 0 or N + M < K:
break
team += 1
ℹ️ 문제정보
- 문제 번호 : 10610
- 문제 이름 : 30
- 난이도 : 실버 4
- 문제 링크 : https://www.acmicpc.net/problem/10610
📖 문제 요약
어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다.
미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라.
입력
N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다.
출력
미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는다면, -1을 출력하라.
✨문제 분석 & 아이디어
30의 배수를 만들기 위해서는
3의 배수이면서 10의 배수라는 조건을 만족해야 한다.
1) 3의 배수의 조건
각 자리 숫자의 합이 3의 배수가 되어야 한다.
예를 들면,
80875542
이 숫자의 경우 각 자릿수의 합이 39이다.
8 + 0 + 8 + 7 + 5 + 5 + 4 + 2 = 39
39는 3의 배수이므로 80875542는 3의 배수 조건을 만족한다.
2) 10의 배수의 조건
맨 끝자리가 0이 되어야 한다.
즉, 주어진 숫자에 0이 1개 이상 포함되어 있어야 한다.
📍풀이
숫자 N을 입력받고,
자릿수별로 나눈 배열 N_list를 만들어주었다.
3의 배수인지 확인하기 위해 sum 함수를 이용해 각 자릿수의 합을 구해주고,
이를 3으로 나누어 3의 배수 조건을 만족하는지 확인한다.
또, 10의 배수인지 확인하기 위해 N_list에 0이 하나라도 포함되어 있는지 확인한다.
해당 조건을 만족하지 않으면 30의 배수를 만들 수 없으므로 -1을,
아니라면 N_list를 내림차순으로 정렬하고 붙여 만든 수를 출력한다.
import sys
input = sys.stdin.readline
N = input().rstrip()
N_list = list(map(int, N))
if sum(N_list) % 3 != 0 or not N_list.count(0):
print(-1)
else:
N_list.sort(reverse=True)
print("".join(map(str, N_list)))ℹ️ 문제정보
- 문제 번호 : 11650
- 문제 이름 : 좌표 정렬하기
- 난이도 : 실버 5
- 문제 링크 : https://www.acmicpc.net/problem/11650
📖 문제 요약
2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.
출력
첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.
✨문제 분석 & 아이디어
입력 개수가 최대 10⁵이고, 이 좌표를 정렬하는 문제이다.
시간 제한이 1초 이므로 최대 10⁸ 연산이 가능하기 때문에
가능한 알고리즘의 시간복잡도는 O(N) 또는 O(N log N)
파이썬의 기본 정렬은 Timsort 알고리즘을 이용하는데
최선은 O(N), 평균은 O(N log N), 최악은 O(N log N)의 시간복잡도를 가진다.
따라서 파이썬 기본 정렬을 사용해도 해당 문제를 풀 수 있다.
조건을 확인해보면
먼저 x좌표를 오름차순으로 정렬하고, x좌표가 같다면 y좌표를 오름차순으로 정렬하면 된다.
파이썬 정렬에서 정렬 조건을 설정하기 위해서는
lambda 함수를 이용할 수 있다.
📍풀이
points 배열에 (x, y) 좌표를 저장하고, lambda 함수를 이용해 정렬한다.
key = lambda x : (x[0], x[1])
응용)
내림차순 정렬을 위해서는 마이너스(-)를 활용하면 된다.
key = lambda x : (-x[0], -x[1])
import sys
input = sys.stdin.readline
N = int(input())
points = []
for i in range(N):
x, y = map(int, input().split())
points.append((x, y))
points.sort(key=lambda x: (x[0], x[1]))
for x, y in points:
print(x, y)
🔥응용 문제
ℹ️ 문제정보
- 문제 번호 : 11651
- 문제 이름 : 좌표 정렬하기 2
- 난이도 : 실버 5
- 문제 링크 : https://www.acmicpc.net/problem/11651
import sys
input = sys.stdin.readline
N = int(input())
points = []
for i in range(N):
x, y = map(int, input().split())
points.append((x, y))
points.sort(key=lambda x: (x[1], x[0]))
for x, y in points:
print(x, y)
ℹ️ 문제정보
- 문제 번호 : 10814
- 문제 이름 : 나이순 정렬
- 난이도 : 실버 5
- 문제 링크 : https://www.acmicpc.net/problem/10814
import sys
input = sys.stdin.readline
N = int(input())
users = []
for i in range(N):
age, name = input().rstrip().split()
users.append((int(age), name, i))
users.sort(key=lambda x: (x[0], x[2]))
for age, name, idx in users:
print(str(age) + " " + name)
ℹ️ 문제정보
- 문제 번호 : 10825
- 문제 이름 : 국영수
- 난이도 : 실버 4
- 문제 링크 : https://www.acmicpc.net/problem/10825
import sys
input = sys.stdin.readline
N = int(input())
students = []
for i in range(N):
name, korean, english, math = input().rstrip().split()
students.append((name, int(korean), int(english), int(math)))
students.sort(key=lambda x: (-x[1], x[2], -x[3], x[0]))
for student in students:
print(student[0])ℹ️ 문제정보
- 문제 번호 : 10989
- 문제 이름 : 수 정렬하기 3
- 난이도 : 브론즈 1
- 문제 링크 : https://www.acmicpc.net/problem/10989
📖 문제 요약
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
출력
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
✨문제 분석 & 아이디어
메모리 제한이 8MB로 작은 문제
처음에는 데이터를 배열에 입력받아서 파이썬 기본 정렬을 이용하는 방식으로 구현해 보았는데,
메모리 초과가 나왔다.
입력 숫자 범위가 10,000보다 작거나 같은 자연수이므로
1 ~ 10,000의 숫자가 주어진 횟수를 저장해두고, 출력한다.
즉, 카운팅 정렬을 이용하는 문제
카운팅정렬
- 입력되는 숫자의 최댓값(10,000)을 기준으로 각 숫자의 등장 횟수를 저장할 배열을 생성
- N개의 입력 숫자를 하나씩 읽으면서 해당 숫자에 해당하는 카운트 배열의 인덱스 값을 1씩 증가
- 정렬된 결과를 출력
이렇게 되면 10,000개의 정수를 저장하는 배열만 필요하므로 메모리 사용량이 적다.
📍풀이
import sys
input = sys.stdin.readline
N = int(input())
nums_count = [0] * 10001
for i in range(N):
num = int(input())
nums_count[num] += 1
for i in range(10001):
if nums_count[i] != 0:
for j in range(nums_count[i]):
print(i)