문제 💁🏻♂️
문제 링크 - 백준 30969 진주로 가자! (Hard)
해결 과정
이 문제는 문제만 읽었을 때는 정말 쉬운 문제이다.
사고 과정 (1) ❗️
문제를 읽어보면 해결방법은 다음과 같다.
- 입력을 모두 받고, 교통 요금에 해당하는 값들만 리스트에 저장한다.
jinju라는 교통편을 찾았다면, 해당 요금을 변수에 따로 저장한다.- 모든 교통 요금을 저장한 리스트에서
jinju교통편의 교통 요금보다 높은 값들의 개수를 센다.
처음에는 위와 같은 방식으로 문제를 풀었다. 그러나, 메모리 초과 라는 결과를 얻었다. 그래서 문제의 조건을 살펴보니 메모리 제한이 16MB 이다. 즉, int 정수 하나가 4Byte를 차지하고, 대략적으로 16MB = 16,000KB = 16,000,000B 이므로 4,000,000 개의 정수를 저장할 수 있다. 하지만, 주어지는 교통편의 개수의 최댓값은 1 ≤ N ≤ 5,000,000 이기 때문에 메모리 초과가 나는 것이었다. 따라서 해결 방법을 다시 생각해야했다. 어떻게 저장을 덜 하고, 문제를 해결할 수 있을까? 언제 jinju 라는 교통편이 나올지 모르기 때문에 입력은 우선, 모두 받아서 저장은 해야한다. (그래야 비교를 할 수 있기 때문에) 20분 동안 생각해도 방법이 생각나지 않아, 블로그를 탐색했다.
사고 과정 (2) ‼️
중요한 사고 과정을 알 수 있었다. 문제에서 주어진 jinju 교통편의 요금은 최대 1,000이다. 다른 교통편의 교통요금으로 주어질 수 있는 최댓값은 10^15이다. 즉, jinju 교통편의 요금보다 크냐 작냐를 비교 하기 위해서는 1,000보다 작냐, 크냐만 따지면 되는 것이었다. 이 문제를 해결하기 위한 방법의 핵심은 마치 계수 정렬 아이디어와 같다.
- 우선, 1,002 개의 원소를 담을 수 있는 리스트를 선언한다.
- 1,000 미만인 요금들은 각 인덱스에 맞는 곳에 값을 1씩 증가하고, 1,000을 초과하는 값들은 그냥 1,001 인덱스를 가진 곳에 값을 1씩 증가시키면 된다.
- 모두 저장을 하고 나면,
jinju교통편의 교통 요금에 해당하는 값보다 뒤에 있는 값들을 모두 더한 값이 문제에서 요구하는 정답이 된다.
그저 5,000,000개의 값들을 어떻게 컨트롤할 수 있을까에 집중하고 있었지만, 문제를 해결할 수 있는 key는 교통 요금의 범위에 있었다. 이 문제를 통해서 계수 정렬의 아이디어를 다시 떠올릴 수 있었고, 그 아이디어를 응용해서 정렬이 아닌 다른 문제에 적용하여 풀 수 있다는 것에 큰 깨달음을 얻었다.
정답은 늘 짜릿하다!
코드
오답 코드 (메모리 초과)
from sys import stdin
input = stdin.readline
n = int(input().rstrip()) # n: 교통편의 개수
dic = {}
for _ in range(n):
d, c = input().split() # d: 도착지, c: 요금
dic[d] = int(c)
cnt = 0
for city, cost in sorted(dic.items(), key=lambda x: x[1]):
if city == "jinju":
cnt += 1
break
cnt += 1
print(dic["jinju"])
print(n - cnt)정답 코드
from sys import stdin
input = stdin.readline
LEN = 1_001
n = int(input().rstrip()) # n: 교통편의 개수
cost = None
lst = [0 for _ in range(LEN + 1)]
for _ in range(n):
d, c = input().split()
lst[min(1001, int(c))] += 1
if d == "jinju":
cost = int(c)
cnt = 0
for num in range(cost + 1, LEN + 1):
cnt += lst[num]
print(cost)
print(cnt)Reference
