코드 구현력 기르기
K번째수
N개의 숫자로 이루어진 숫자열이 주어지면 해당 숫자열중에서 s번째부터 e번째 까지의 수를 오름 차순 정렬했을 때 k번째로 나타나는 숫자를 출력하는 프로그램을 작성하세요.
-
입력 설명
1.1 첫 번째 줄에 테스트 케이스 T(1<=T<=10)이 주어집니다.각 케이스별
1.2 첫 번쨰 줄은 자연수 N(5<=N<=500), s, e, k가 차례로 주어진다.
1.3 두 번쨰 줄에 N개의 숫자가 차례로 주어진다. -
출력 설명
2.1 각 케이스별 k번째 수를 아래 출력예제와 같이 출력하세요. -
입력 예제(k번째.txt)
2
6 2 5 3
5 2 7 3 8 9
15 3 10 3
4 15 8 16 6 6 17 3 10 11 18 7 14 7 15 -
출력 예제
# 1 7
# 2 6입력예제1 해설: 2 7 3 8의 숫자 중 3번째로 작은 수는 7이다.
"""
import sys
sys.stdin=open("k번째.txt", 'rt')
T = int(input()) # T의 값에 2?
print('T:',T)
for t in range(T):
n, s, e, k = map(int, input().split())
print(f"n, s, e, k: {n}, {s}, {e}, {k}")
a = list(map(int, input().split())) # 여기서 나온
print(f"a: {a}")
a = a[s-1:e]
print(f"a 리스트의 s번째부터 e까지: {a}")
a.sort()
print(f"sorting된 a 리스트: {a}" )
print("#%d %d" %(t+1, a[k-1]))느낀점 :
- 정작 문제는 별것 없지만 입력예제가 의미하는 바를 정확히 catch하지 못해서 버벅거렸음...
K번째 큰 수
현수는 1부터 100사이의 자연수가 적힌 N장의 카드를 가지고 있습니다.
같은 숫자의 카드가 여러장 있을 수 있습니다.
현수는 이 중 3장을 뽑아 각 카드에 적힌 수를 합한 값을 기록하려고 합니다.
3장을 뽑을 수 있는 모든 경우를 기록합니다.
기록한 값 중 K번째로 큰 수를 출력하는 프로그램을 작성하세요.
-
입력 설명
첫 줄에 자연수 N(3<=N<=100), K(1<=K<=50)가 입력되며 그 다음 줄에 N개의 카드 값이 입력된다. -
출력 설명
첫 줄에 K번째 수를 출력합니다. K번째 수는 반드시 존재합니다. -
입력예제 1
10 3
13 15 34 23 45 65 33 11 26 42 -
출력예제 1
143
for a in range(n):
for b in range(a+1, n): # a가 9가되면 b가 10이 될수 있는줄 알았는데 거기 아님
for c in range(b+1, n): 어찌보면 위에서 오해한것이 IndexError: index out of range가 발생할 거라고 착각을 했다.
for a in range(10):
for b in range(a+1, n):
for c in range(b+1, n): 위 형태에서 a+1은 10이 되겠지만 하지만 변수 b에 절대로 10이 할당되지는 못한다.
예를 들면 이렇다.
for i in range(10, 1): print(i) # 절대로 프린트가 찍히지 않느다. for i in []: print(i) # 마치 empty list가 절대로 변수 i에 어떠한 값도 할당하지 않는것 처럼 말이다.해답 코드
solution = set()
n, k = map(int, input().split())
if not (3<=n<=100) or not (1<=k<=50):
print(f"Scope of N and K Should be (3<=N<=100) and (1<=K<=50)")
def big_k(n, k):
import random
# random_numbers = [random.randint(1, 101) for _ in range(n)]
random_numbers = 13, 15, 34, 23, 45, 65, 33, 11, 26, 42
print(random_numbers)
for a in range(n):
for b in range(a+1, n):
for c in range(b+1, n):
print(random_numbers[a]+random_numbers[b]+random_numbers[c], ':', random_numbers[a], random_numbers[b], random_numbers[c])
solution.add(random_numbers[a]+random_numbers[b]+random_numbers[c])
# 내림차순 정렬
result = sorted(solution, reverse=True)
print(result)
# k번째로 큰 수
return result[k-1]
print(big_k(n, k))
느낀점 :
- 이 분제는 조합의 개념을 모르면 풀기 매우 어려운 문제다. 나같은 수포자에게 너무나 가혹한 문제이다. 하지만 다시 개념 단디 붙잡고 차근차근 짚어가면서 해야 겠다는 생각을 가졌다.
- 핵심은 한 번 뽑은 카드는 다시 뽑지 않도록 하는게 중요하다는것! 그렇게 하려면 인덱스를 돌면서 start_point를 그것도 다음 루프의!!! 그놈을 +1해줘야한다는고.
최솟값 구하기
arr = [5, 3, 7, 9, 2, 5, 2, 6]
arrMin = float('inf') # 파이썬에서 가장 큰 값으로 초기화함
for i in range(len(arr)): # arr의 길이 만큼 loop를 돌립니다. i는 0~7로 할당이 됨
print(arr[i])5
3
7
9
2
5
2
6출력된 결과 값이 결국 arrMin과 arr[i] 비교하여 작을경우 arr[i]을 arrMin에 할당하여 값을 바꾸어준다.
if arr[i] < arrMin:
arrMin = arr[i]정리
- index로 구하기
arr = [5, 3, 7, 9, 2, 5, 2, 6]
arrMin = float('inf') # 파이썬에서 가장 큰 값으로 초기화함
for i in range(len(arr)):
if arr[i] < arrMin:
arrMin = arr[i]
print(arrMin)- 리스트의 값으로 for문 돌리기
arr = [5, 3, 7, 9, 2, 5, 2, 6]
arrMin = float('inf')
for value in arr:
if value < arrMin:
arrMin = value
print(arrMin)느낀점
float('inf')를 사용하면 파이썬에서 가장 큰 값을 구할 수 있네!
대표값
대표값 N명의 학생의 수학점수가 주어집니다. N명의 학생들의 평균(소수 첫째자리 반올림)을 구하고, N명의 학생 중 평균에 가장 가까운 학생은 몇 번째 학생인지 출력하는 프로그램을 작성하세요.
평균과 가장 가까운 점수가 여러 개일 경우 먼저 점수가 높은 학생의 번호를 답으로 하고, 높은 점수를 가진 학생이 또 여러명인 경우 그 중 학생번호가 빠른 학생의 번호를 답으로 합니다.
-
입력 설명
첫 줄에 자연수 N(5<=<=100)이 주어지고, 두 번째 줄에는 각 학생의 수학점수인 N개의 자연수가 주어집니다. 학생의 번호는 앞에서부터 1로 시작해서 N까지이다. -
출력 설명
첫 줄에 평균과 평균에 가장 가까운 학생의 번호를 출력한다. 평균은 소수 첫째자리에서 반올림합니다. -
입력 예제
10
45 73 66 87 92 67 75 79 75 80 -
출력 예제
74 7
예제설명) 평균이 74점으로 평균과 가장 가까운 점수는 73(2번), 75(9번)입니다. 여기서 점수가 높은 75(7번), 75(9번)이 답이 될 수 있고, 75점이 두명이므로 학생번호가 빠른 7번이 답이 됩니다.
# n명의 학생수
n = int(input())
# 학생들의 점수를 리스트형식으로 가져온다.
scores = list(map(int, input().split()))
# round() 소수 첫 째자리에서 반올림
average=round(sum(scores)/n)
# 최솟값으로 설정할 변수와 큰 값을 초기화값으로 입력한다.
min = float('inf')
# idx: 학생번호
for idx, score in enumerate(scores):
# 편차 구하기
deviation = abs(score-average)
if deviation < min :
min = deviation
# 편차가 같은 점수가 나올경우 더큰 점수로 해야함. 즉 비교를 위한 변수가 필요함
tmp_score=score
# # 평균과 가까운(편차가 가장 작은) 학생의 인덱스 번호
res = idx+1
# 이전 값(min)과 deviation이 같다면, value(현재값) > tmp_socre(이전값)이라면, value를 tmp_score로 할당하고, idx번호를 변경한다.
elif deviation == min and score > tmp_score:
tmp_score = score
res = idx+1
print(average, res)정다면체
2개의 정 N면체와 정 M면체의 두 개의 주사위를 던져서 나올 수 있는 눈의 합 중 가장 확률이 높은 숫자를 출력하는 프로그램을 작성하세요.
정답이 여러 개일 경우 오름차순으로 출력합니다.
-
입력설명
첫 번째 줄에는 자연수 N과 M이 주어집니다. N과 M은 4, 6, 8, 12, 20 중의 하나입니다. -
출력설명
첫 번째 줄에 답을 출력합니다. -
입력예제 1
4, 6 -
출력예제 1
5, 6, 7 -
참고:
정?면체는: 정(사, 육, 팔, 십이, 이십)면체가 대표적임
from collections import defaultdict
n,m=4,6
result = defaultdict(int)
max = 0
for i in range(1, n+1):
for j in range(1, m+1):
result[i+j]+= result[i+j]+1
# 루프를 돌면서 사전 정의된 최대값과 비교하여 최대값을 할당해줌
for i in range(n+m+1):
if result[i] > max:
max=result[i]
for i in range(n+m+1):
if result[i] == max:
print(i, end=' ')
자릿수의 합
N개의 자연수가 입력되면 각 자연수의 자릿수의 합을 구하고, 그 합이 최대인 자연수를 출력하는 프로그램을 작성하세요. 각 자연수의 자릿수의 합을 구하는 함수를 def digit_sum(x)를 꼭 작성해서 프로그래밍 하세요.
-
입력 설명
첫 줄에 자연수의 개수 N(3<=N<=100)이 주어지고, 그 다음 줄에 N개의 자연수가 주어진다.
각 자연수의 크기는 10,000,000를 넘지 않는다. -
출력 설명
자릿수의 합이 최대인 자연수를 출력한다. 자릿수의 합이 같을 경우 입력순으로 먼저인 숫자를 출력합니다. -
입력예제 1
3
125 15232 97 -
출력예제 1
97
아래는 for문이 3번 돌게됨.
n = 3
inputs = '125 15232 97'.split()
result = {}
import time
from datetime import timedelta
start = time.time()
def digit_sum(inputs):
max = res = 0
for index, value in enumerate(inputs):
result[inputs[index]] = sum([int(i) for i in value])
for key, value in result.items():
if value > max:
max = value
res=key
if value == max:
res=key
return res
print(timedelta(seconds=time.time()-start))
print(digit_sum(inputs))code from tutor
n = 3
a = [125, 15232, 97]
import time
start = time.time()
from datetime import timedelta
def digit_sum(x):
sum = 0
while x > 0:
# x를 10으로 나눈 나머지
sum += x % 10
# x를 10으로 나눈 몫
x = x // 10
return sum
max = -2147000000
for x in a:
tot = digit_sum(x)
if (tot > max):
max = tot
res = x
print(timedelta(seconds=time.time()-start))
print(res)
소수(에라토스테네스 체)
자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요.
만약 20이 입력되면 1부터 20까지의 소수는 2, 3, 5, 7, 11, 13, 17, 19로 총 8개입니다.
제한시간은 1초입니다.
-
입력 설명
첫 줄에 자연수의 개수 N(2<=N<=200,000)이 주어집니다. -
출력 설명
첫 줄에 소수의 개수를 출력합니다. -
입력 예제 1
20 -
출력 예제 1
8
# 예) 1~100
import math
m,n = map(int,input().split(" "))
l = [True for _ in range(n + 1)] # 처음엔 모든 수가 소수(True)인 것으로 초기화
# 2부터 n의 제곱근까지이며 그리고 +1을 range 함수 두번째 매개변수에 붙인 이유는 n=100일경우 int(math.sqrt(n)) -> 10 이 되서 range(2, 10)이 되면 실제 범위는 9까지 되기 때문에 뒤에 +1을 해준것!
# 눈여겨 볼 부분이 math.sqrt(n) 이부분이라는 점! 범위를 해당 수의 배수는 모두 지울수 있게 하는 핵심 역할
for i in range(2, int(math.sqrt(n)) + 1):
if l[i] == True: # i가 소수인 경우 (남은 수인 경우)
# i를 제외한 i의 모든 배수를 False로 변경
# j값은 2*2, 2*3, 2*4, .... 다시 loop를 돌때 3*2 ... 이런식으로 while문을 돌며 해당 배수의 결과값. 즉, 리스트변수 l의 첨자(i*j)를 통해서 인덱싱하며 할당을 통한 소수가 아닌 값을 제외하게함
j = 2
while i * j <= n:
l[i * j] = False
j += 1
# 모든 소수 출력
for i in range(m, n + 1):
if l[i]:
if i != 1:
print(i)뒤집은 소수
시간 복잡도 O(n)
공간 복잡도 O(n)
설명
뒤집은 소수 N개의 자연수가 입력되면 각 자연수를 뒤집은 후 그 뒤집은 수가 소수이면 그 수를 출력하는 프로그램을 작성하세요.
예를 들어 32를 뒤집으면 23이고, 23은 소수이다. 그러면 23을 출력 한다.
단 910를 뒤집으면 19로 숫자화 해야 한다.
첫 자리부터의 연속된 0은 무시한다.
뒤집는 함수인 def reverse(x) 와 소수인지를 확인하는 함수 def isPrime(x)를 반드시 작성하 여 프로그래밍 한다.
▣ 입력설명
첫 줄에 자연수의 개수 N(3<=N<=100)이 주어지고, 그 다음 줄에 N개의 자연수가 주어진다. 각 자연수의 크기는 100,000를 넘지 않는다.
▣ 출력설명
첫 줄에 뒤집은 소수를 출력합니다. 출력순서는 입력된 순서대로 출력합니다.
▣ 입력예제
5
32 55 62 3700 250
▣ 출력예제
23 73
import math
from random import randint
def is_prime(num):
end = int(math.sqrt(num))+1
for i in range(2, end):
if num % i == 0:
return False # 2부터 ~ 0으로 나누어 떨어지면 소수가 아님
return True
def rever(x):
result = str(x)[::-1]
return int(result)
n = int(input())
str_arr = [randint(1,100000) for _ in range(n)]
#str_arr = '32 55 62 3700 250'.split()
for str_value in str_arr:
reversed_num = rever(str_value)
if is_prime(reversed_num):
print(rever(str_value), end=' ')
주사위 게임
시간 복잡도 : O(n) for문 1번 사용
공간 복잡도 : O(1)
설명
주사위 게임 1에서부터 6까지의 눈을 가진 3개의 주사위를 던져서 다음과 같은 규칙에 따라 상금을 받는 게임이 있다.
규칙(1) 같은 눈이 3개가 나오면 10,000원+(같은 눈)1,000원의 상금을 받게 된다.
규칙(2) 같은 눈이 2개만 나오는 경우에는 1,000원+(같은 눈)100원의 상금을 받게 된다.
규칙(3) 모두 다른 눈이 나오는 경우에는 (그 중 가장 큰 눈)*100원의 상금을 받게 된다.
예를 들어, 3개의 눈 3, 3, 6이 주어지면 상금은 1,000+3100으로 계산되어 1,300원을 받게 된 다. 또 3개의 눈이 2, 2, 2로 주어지면 10,000+21,000 으로 계산되어 12,000원을 받게 된다. 3개의 눈이 6, 2, 5로 주어지면 그 중 가장 큰 값이 6이므로 6*100으로 계산되어 600원을 상금 으로 받게 된다.
N 명이 주사위 게임에 참여하였을 때, 가장 많은 상금을 받은 사람의 상금을 출력하는 프로그램 을 작성하시오
▣ 입력설명
첫째 줄에는 참여하는 사람 수 N(2<=N<=1,000)이 주어지고 그 다음 줄부터 N개의 줄에 사람 들이 주사위를 던진 3개의 눈이 빈칸을 사이에 두고 각각 주어진다.
▣ 출력설명
첫째 줄에 가장 많은 상금을 받은 사람의 상금을 출력한다.
▣ 입력예제
3
3 3 6
2 2 2
6 2 5
▣ 출력예제
reward = 0
for i in range(n):
_input = input().split()
_input.sort()
print(_input)
a, b, c = map(int, _input)
if a == b and b == c:
print(a, b, c)
money = 10000 + (1000*a)
elif a == b or a == c:
money = 1000 + (100*a)
pass
elif b == c:
money = 10000 + (100*a)
elif a != b and b != c and a!= c:
money = 100*c
if money > reward:
print('---')
print('reward=money:', reward, money)
reward = money
print(reward)
점수 계산
시간복잡도 : O(n) for문 1회
공간 복잡도 : O(1)
설명
OX 문제는 맞거나 틀린 두 경우의 답을 가지는 문제를 말한다.
여러 개의 OX 문제로 만들어진 시험에서 연속적으로 답을 맞히는 경우에는 가산점을 주기 위해서 다음과 같이 점수 계산을 하기로 하였다.
1번 문제가 맞는 경우에는 1점으로 계산한다. 앞의 문제에 대해서는 답을 틀리다가 답이 맞는 처음 문제는 1점으로 계산한다.
또한, 연속으로 문제의 답이 맞는 경우에서 두 번째 문제는 2점, 세 번째 문제는 3점, ..., K번째 문제는 K점으로 계산한다. 틀린 문제는 0점으로 계산한다.
예를 들어, 아래와 같이 10 개의 OX 문제에서 답이 맞은 문제의 경우에는 1로 표시하고, 틀린 경우에는 0으로 표시하였을 때, 점수 계산은 아래 표와 같이 계산되어, 총 점수는 1+1+2+3+1+2=10 점이다
1 0 1 1 1 0 0 1 1 0
채점 1 0 1 1 1 0 0 1 1 0
점수 1 0 1 2 3 0 0 1 2 0
시험문제의 채점 결과가 주어졌을 때, 총 점수를 계산하는 프로그램을 작성하시오.
▣ 입력설명
첫째 줄에 문제의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에는 N개 문제의 채점 결과를 나 타내는 0 혹은 1이 빈 칸을 사이에 두고 주어진다. 0은 문제의 답이 틀린 경우이고, 1은 문제의 답이 맞는 경우이다.
▣ 출력설명
첫째 줄에 입력에서 주어진 채점 결과에 대하여 가산점을 고려한 총 점수를 출력한다.
▣ 입력예제
10
1 0 1 1 1 0 0 1 1 0
▣ 출력예제
10
n = 10
result = 0
# _input = list(map(int, input().split()))
_input = list(map(int, '1 0 1 1 1 0 0 1 1 0'.split()))
count = 0
for value in _input:
# 점수를 맞춘 경우
if value:
# 연속한 경우
count += 1
if count:
result += count
# 연속하지 못한 경우
elif not count:
result += 1
else :
count = 0
print(result)key point
- 값이 1인 경우 : count변수를 어떻게 처리 할 것인가
- 변수 초기화 위치
- 연속해서 1인 경우 count 변수를 증가 시키는 위치
- 연속하지 못한 경우 - 값이 0인 경우
- 변수 초기화 위치
