i can do ik!

CodeUp 1451 데이터 정렬(small)

문제

데이터 정렬은 프로그래밍 문제를 푸는데 많이 사용된다.

N개의 데이터가 입력되면, 오름차순된 결과를 출력하는 프로그램을 작성하시오.

시간 제한 : 1 초
메모리 제한 : 128 MB

입력

첫째줄에 N이 입력된다. (1<=N<=10,000)

다음 줄부터 N개의 데이터가 한 줄에 한 개씩 입력된다.

출력

오름차순 정렬한 결과를 한 줄에 하나씩 순서대로 출력한다.

입력 예시

5
7
3
10
2
1

출력 예시

1
2
3
7
10

풀이

import sys

input = sys.stdin.readline
n = int(input())
nums = []

for _ in range(0, n):
    number = int(input())
    nums.append(number)
    
nums.sort()

print(*nums)

CodeUp 1420 3등 찾기

문제

 민준이는 뒤늦게 정보 과목의 중요성을 깨닫고 학습실에서 공부를 하고 있다.

기본 공부가 너무 안 되어 있어 아주 쉬운 문제부터 어려움을 겪은 민준이는 친구에게 물어보려고 한다.

가장 잘 하는 친구에게 물어보기는 질문의 내용이 너무 부끄러워 n명의 친구들 중 정보 성적이 3번째로 높은 친구에게 묻고자 한다.

친구들의 성적은 모두 다르다.

n명의 친구들의 이름과 정보 성적이 주어졌을 때 성적이 세 번째로 높은 학생의 이름을 출력하시오.

시간 제한 : 1 초
메모리 제한 : 128 MB

입력

첫째 줄에 n이 입력된다. ( 3 <= n <= 50 )

둘째 줄 부터 n+1행까지 친구의 이름과 점수가 공백으로 분리되어 입력된다. 이름은 영문

출력

세 번째로 높은 학생의 이름을 출력한다.

입력 예시

5
minsu 78
gunho 64
sumin 84
jiwon 96
woosung 55

출력 예시

minsu

풀이

n = int(input())
record = {}

for _ in range(0, n):
    name, score = input().split()
    record[name] = int(score)

data = sorted(record.items(), key=lambda x: x[1], reverse=True)

print(data[2][0])

CodeUp 1172 세 수 정렬하기

문제

세 수를 오름차순으로 정렬하려고 한다. (낮은 숫자 -> 높은 숫자)

예)
5 8 2   ====> 2 5 8    로 출력

시간 제한 : 1 초
메모리 제한 : 128 MB

입력

세 정수가 입력된다.

출력

낮은 숫자 부터 출력한다.

입력 예시

8 7 6

출력 예시

6 7 8

도움말

숫자가 같을 때도 생각하세요~

풀이

import sys

input = sys.stdin.readline
nums = list(map(int, input().split()))
nums.sort()

print(*nums, end=' ')

BOJ 2212 센서

문제

한국도로공사는 고속도로의 유비쿼터스화를 위해 고속도로 위에 N개의 센서를 설치하였다.

문제는 이 센서들이 수집한 자료들을 모으고 분석할 몇 개의 집중국을 세우는 일인데, 

예산상의 문제로, 고속도로 위에 최대 K개의 집중국을 세울 수 있다고 한다.

각 집중국은 센서의 수신 가능 영역을 조절할 수 있다.

집중국의 수신 가능 영역은 고속도로 상에서 연결된 구간으로 나타나게 된다.

N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 하며, 

집중국의 유지비 문제로 인해 각 집중국의 수신 가능 영역의 길이의 합을 최소화해야 한다.

편의를 위해 고속도로는 평면상의 직선이라고 가정하고, 

센서들은 이 직선 위의 한 기점인 원점으로부터의 정수 거리의 위치에 놓여 있다고 하자. 

따라서, 각 센서의 좌표는 정수 하나로 표현된다. 

이 상황에서 각 집중국의 수신 가능영역의 거리의 합의 최솟값을 구하는 프로그램을 작성하시오. 

단, 집중국의 수신 가능영역의 길이는 0 이상이며 모든 센서의 좌표가 다를 필요는 없다.

시간 제한 : 2 초
메모리 제한 : 128 MB

입력

첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 

셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 

각 좌표 사이에는 빈 칸이 하나 있으며, 좌표의 절댓값은 1,000,000 이하이다.

출력

첫째 줄에 문제에서 설명한 최대 K개의 집중국의 수신 가능 영역의 길이의 합의 최솟값을 출력한다.

예제 입력 1

6
2
1 6 9 3 6 7

예제 출력 1

5

예제 입력 2

10
5
20 3 14 6 7 8 18 10 12 15

예제 출력 2

7

풀이

import sys

input = sys.stdin.readline
n = int(input())
k = int(input())
sensor = list(map(int, input().split()))
sensor.sort()
arr = []

for i in range(0, n-1):
    arr.append(sensor[i+1] - sensor[i])

arr.sort()
print(sum(arr[:n-k]))

BOJ 2437 저울

문제

하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다.

이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다.

또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다.

무게가 양의 정수인 N개의 저울추가 주어질 때, 

이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오.

예를 들어, 무게가 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 주어졌을 때,

이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다.

시간 제한 : 1 초
메모리 제한 : 128 MB

입력

첫 째 줄에는 저울추의 개수를 나타내는 양의 정수 N이 주어진다.

N은 1 이상 1,000 이하이다. 

둘째 줄에는 저울추의 무게를 나타내는 N개의 양의 정수가 빈칸을 사이에 두고 주어진다. 

각 추의 무게는 1이상 1,000,000 이하이다.

출력

첫째 줄에 주어진 추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 출력한다.

예제 입력 1

7
3 1 6 2 7 30 1

예제 출력 1

21

풀이

n=int(input())
weight=list(map(int, input().split()))
weight.sort()
res=1

for i in weight:
    if res < i:
        break
    res += i
print(res)

BOJ 1015 수열 정렬

문제

P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 

수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 

적용하는 방법은 B[P[i]] = A[i]이다.

배열 A가 주어졌을 때, 수열 P를 적용한 결과가 비내림차순이 되는 수열을 찾는 프로그램을 작성하시오. 

비내림차순이란, 각각의 원소가 바로 앞에 있는 원소보다 크거나 같을 경우를 말한다. 

만약 그러한 수열이 여러개라면 사전순으로 앞서는 것을 출력한다.

시간 제한 : 2 초
메모리 제한 : 128 MB

입력

첫째 줄에 배열 A의 크기 N이 주어진다.

둘째 줄에는 배열 A의 원소가 0번부터 차례대로 주어진다.

N은 50보다 작거나 같은 자연수이고, 배열의 원소는 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 비내림차순으로 만드는 수열 P를 출력한다.

예제 입력 1

3
2 3 1

예제 출력 1

1 2 0

예제 입력 2

4
2 1 3 1

예제 출력 2

2 0 3 1

예제 입력 3

8
4 1 6 1 3 6 1 4

예제 출력 3

4 0 6 1 3 7 2 5

풀이

n = int(input())
arr = list(map(int, input().split()))
sort_arr = sorted(arr)

res = []
for i in range(n):
    t = sort_arr.index(arr[i])
    res.append(t)
    sort_arr[t] = -1

print(*res)

BOJ 2161 카드1

문제

N장의 카드가 있다.

각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에,

N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 

우선, 제일 위에 있는 카드를 바닥에 버린다.

그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 

1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 

3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 

마지막으로 2를 버리고 나면, 버린 카드들은 순서대로 1 3 2가 되고, 남는 카드는 4가 된다.

N이 주어졌을 때, 버린 카드들을 순서대로 출력하고, 마지막에 남게 되는 카드를 출력하는 프로그램을 작성하시오.

시간 제한 : 2 초
메모리 제한 : 128 MB

입력

첫째 줄에 정수 N(1 ≤ N ≤ 1,000)이 주어진다.

출력

첫째 줄에 버리는 카드들을 순서대로 출력한다.

제일 마지막에는 남게 되는 카드의 번호를 출력한다.

예제 입력 1

7

예제 출력 1

1 3 5 7 4 2 6

풀이

from collections import deque
import sys

input = sys.stdin.readline
n = int(input())
queue = deque([i for i in range(1, n+1)])

while len(queue) > 1:
    print(queue.popleft())
    queue.append(queue.popleft())
print(queue.popleft())

BOJ 2164 카드2

문제

N장의 카드가 있다. 
각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, 

N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 

우선, 제일 위에 있는 카드를 바닥에 버린다. 

그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 

1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 

3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 

마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.

N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

시간 제한 : 2 초
메모리 제한 : 128 MB

입력

첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다.

출력

첫째 줄에 남게 되는 카드의 번호를 출력한다.

예제 입력 1

6

예제 출력 1

4

풀이

from collections import deque
import sys

input = sys.stdin.readline
n = int(input())
queue = deque([n-i for i in range(n)])

while len(queue) > 1:
    queue.pop()
    queue.appendleft(queue.pop())

print(queue.pop())