TIL 23-04-25 백준 알고리즘 - 수 정렬하기 3

1. 백준 알고리즘 - 설탕 배달

 문제점

문제
상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 
상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 
설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 
봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 
예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 
5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 
봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)

출력
상근이가 배달하는 봉지의 최소 개수를 출력한다. 
만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.

# 설탕은 3 or 5

# 정확하게 맞춰서 배달할 때 최소한의 갯수 구하기

# 불가능하면 -1

 시도해 본 것들

수식으로 작성 시도 

three = 0
five = 0
kg = 11
if kg % 5 % 3 == 0:
    five = kg//5
    three = kg % 5//3
    print(three+five)
elif kg % 3 % 5 == 0:
    three = kg//3
    five = kg % 3//5
    print(three+five)
else:
    print(-1)

5로 먼저 나눴을 때 5로 나눌 수 있는 모든 수를 나눠버려서 5로 나누고 6 이상 남아야 맞아떨어지는 경우 계산 불가

 

반복문 시도 

five_num = 0
a = int(input())
min_answer = -1
for _ in range(a):
    kg = a
    kg -= 5*five_num
    if kg < 0:
        break
    three = kg // 3
    if kg > 2 and kg % 3 == 0:
        current_answer = five_num+three
        if min_answer < 0:
            min_answer = current_answer
        elif min_answer > 0 and min_answer > current_answer:
            min_answer = current_answer
    five_num += 1
print(min_answer)

min_answer의 기본값을 -1로 설정, KG수 만큼 range를 돌리면서 5kg을 차감했을 때 -값으로 진입하면 break 

제출 시 오답 

 

코드 수정

if kg > 2 and (kg % 3 == 0 or kg % 5 == 0):

기존 코드는 5로만 나눴을 때 딱 맞아떨어지는 경우를 조건에 포함하지 못했음

 해결 방법

five_num = 0
a = int(input())
min_answer = -1
for _ in range(a):
    kg = a
    kg -= 5*five_num
    if kg < 0:
        break
    three = kg // 3
    if kg > 2 and kg % 3 == 0:
        current_answer = five_num+three
        if min_answer < 0:
            min_answer = current_answer
        elif min_answer > 0 and min_answer > current_answer:
            min_answer = current_answer
    five_num += 1
print(min_answer)

수식으로 해결하고 싶었는데 방법이 안 떠오른다.

 

리팩토링 while문과 3을 조작하는 방식의 풀이 

three_num = 0
kg = int(input())
min_answer = -1
while kg >= 0:
    if kg % 5 == 0:
        min_answer = kg//5+three_num
        break
    kg -= 3
    three_num += 1
print(min_answer)

이렇게 3의 숫자를 늘려가면 처음 나오는 값이 5를 최대한 넣고 0으로 나눠 떨어지는 경우가 제일 먼저 나오기 때문에 최솟값인지 체크하는 조건문이 필요가 없다. 

 알게 된 점

제대로 활용하지는 못 했지만 입력받은 값을 조정하며 답을 찾는 방법을 반복문으로 시도할 때 바로 하면서 알고리즘에 익숙해지는 게 실감 난다.

 

 

1. 백준 알고리즘 - 수 정렬하기 3

 문제점

문제
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 
둘째 줄부터 N개의 줄에는 수가 주어진다. 
이 수는 10,000보다 작거나 같은 자연수이다.

출력
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

# 입력 N

# N개의 수

# 출력 N개의 수를 오름차순으로 return

메모리제한

 시도해 본 것들

for문과 append 시도

N = int(input())
n_list = []
for _ in range(N):
    n_list.append(int(input()))
n_list.sort()
for n in n_list:
    print(n)

결과는 맞게 나오지만, 제출 시 제한조건인 메모리를 만족하지 못했다.

 

print개선

print(*n_list, sep='\n')

for문을 통해 print 한 것을 바꿨지만 어림도 없다.

 

입력 방식 개선

for _ in range(N):
    n_list.append(int(sys.stdin.readline()))

입력을 input() 대신  sys.stdin.readline()으로 대체했지만 append를 해결하지 못하면 통과가 불가능하다.

 

for문, append제거 시도 

import sys
N = int(input())
n_list = int(sys.stdin.readlines().rstrip())
n_list.sort()
print(*n_list, sep='\n')

어림도 없다.

 

append대신 리스트를 미리 만들어두기 

n_list = [0] * 10001

방법을 찾아보던 중 리스트를 미리 선언하고 그 값을 바꾸면 메모리를 아낄 수 있음을 알았다.

n_list가 10001개인 이유는 10000까지의 숫자를 표현하기 위해서는 0부터 시작하는 인덱스가 10001개가 필요하다.

 

리스트에 값 넣기

for n in range(N):
    n_list[int(sys.stdin.readline())] += 1

sys.stdin.readline()으로 값을 추가할 index를 지정해서 n번 째 인덱스가 몇 번 나왔는지 카운팅

 

리스트를 바탕으로 print 하기

for n in range(10001):
    for i in range(n_list[n]):
        print(n)

첫 번째 for문은 0~10000까지의 숫자를 뜻한다.

두 번째 for문은 0~10000까지의 index에서 카운팅 된 횟수만큼 print문을 실행한다.

 해결 방법

import sys
N = int(input())
n_list = [0] * 10001
for n in range(N):
    n_list[int(sys.stdin.readline())] += 1
for n in range(10001):
    for i in range(n_list[n]):
        print(n)

 알게 된 점

이제 알고리즘에서 input() 대신 sys.stdin.readline()의 사용을 습관화해야겠다. 몇 번 사용은 해봤지만 아직도 사용하려면 찾아보고 사용하게 된다. 

시간제한이나, 메모리 제한이 생기면 처음 생각했던 코드와 전혀 다른 방법으로 풀게 된다.