2075번 하나로 4시간 순삭_ 후기
처음 문제 봤을 땐 그냥 정렬 문제인 줄 알았다.
"N×N의 수 중 N번째로 큰 수를 출력하세요"
오잉? 그럼 그냥 2차원 배열을 한 줄로 펴서 정렬하고 [-N] 출력하면 되는 거 아냐?
근데 막상 그렇게 풀자니 시간 초과가 날 거 같고…
예제 출력은 맞는데 이상하게 찝찝하다. 그래서 결국 찾아보니 heapq를 쓰는 문제란다.
🧠 그때부터 뇌가 바쁘게 돌아가기 시작했다.
1. heapq? 뭐더라?
“힙큐…? 큐는 알겠는데 힙큐는 뭐였지…?”
“그냥 정렬해주는 큐인가? 왜 쓰지?”
“우선순위 큐래… 근데 정렬은 안 하고도 우선순위를 유지해준다고?”
그래서 개념부터 다시 정리함:
파이썬의 heapq는 기본이 최소 힙
heappop() 하면 가장 작은 수가 먼저 나온다
최대 힙은 따로 없다 → 그래서 -x로 음수 트릭을 써서 구현함
2. ??? 그럼 왜 큰 수를 찾는데 작은 수 힙을 써?
“작은 수가 먼저 나간다며? 그럼 어떻게 큰 수를 찾는 거야???”
★★★여기서 배운 포인트:
❗ 힙에 음수로 넣으면, 큰 수일수록 더 작은 수처럼 취급됨
그래서 -x로 넣고, 꺼낼 때 다시 -heappop()으로 복원하면
👉 “실제로는 가장 큰 수부터 꺼내는 효과”를 만들 수 있음
이걸 최대 힙 흉내내기라고 함.
3. list(map(int, input().split())) ← 이건 뭐야 또
진짜 제일 당황한 구문…
“list(map)이 뭔데? map만 치면 이상한 object만 나오는데?”
“왜 변수도 없고 for문도 없는데 x가 생겨?”
“왜 갑자기 정수로 다 바뀌어 있음???”
💡 깨달은 순간:
map(int, input().split())
→ input으로 받은 문자열 리스트에 int 함수를 각각 적용해주는 기계
list()로 감싸야 우리가 보기 좋은 리스트가 됨
map()은 그냥 자동 변환 공장
python
list(map(int, ["1", "2", "3"])) → [1, 2, 3]
그래서 이 구문은 입력 한 줄을 정수 리스트로 바꾸는 단골 패턴이었다.
4. 리스트 전체에 - 붙이면 안 돼?
나는 진짜로 -nums 같은 거 되는 줄 알았음
“그럼 그냥 heap = -nums 이렇게 하면 되잖아?”
❌ 에러 터짐. 왜냐면 리스트는 숫자 아니니까 - 연산이 안 됨
💡 해결: 리스트 컴프리헨션 써야 함
===========================
python
[-x for x in nums]
요소 하나하나에만 -가 붙게 만드는 방법!
5. len(heap) > N 이 왜 필요해?
이건 문제 핵심이었음.
“왜 > N이지? 딱 N개면 되는 거 아냐?”
“== N일 때 자르면 되는 거 아냐?”
“근데 왜 자꾸 6번째 들어오면 pop()해?”
✔️ 힙에 항상 N개의 큰 수만 유지하기 위한 전략
즉, 6번째가 들어올 때 가장 작은 수(= 음수로 넣은 값 중 절댓값 가장 작은 거)를 제거해서, 큰 수만 남기려고 그런 것.
6. while문 + heappop → 이게 정렬처럼 되네?
“근데 이건 그냥 정렬 아니잖아?”
“왜 결과는 정렬처럼 나와?”
결론: heappop()이 최소 힙이라서
가장 작은 값부터 차례로 나가기 때문
즉, 여러 번 꺼내면 결과적으로 정렬된 순서가 나온다
→ 이걸 정렬처럼 쓰는 경우도 많음
7. 출력이 왜 세로로 돼?
마지막까지 혼란 온 부분…
“왜 리스트는 가로로 출력되는데 이건 왜 세로야?”
알고 보니 while문으로 print() 여러 번 돌릴 때
print()는 기본적으로 줄바꿈 포함이라
하나씩 줄줄이 세로로 찍히는 거였다.
원하면 print(x, end=" ")로 가로 출력도 가능.
✅ 이 문제 하나로 얻은 개념 총정리
heapq의 기본은 최소 힙
최대 힙 구현 → 음수로 넣고, 꺼낼 때 다시 음수로 복원
map()은 반복 변환 기계. list()로 감싸야 실제 리스트로 보인다
리스트 전체에 - 붙이면 안 된다. 컴프리헨션 써야 한다
힙의 길이를 N개로 유지하면 N번째 큰 수가 남는다
heappop()을 반복하면 정렬처럼 꺼낼 수 있다
기본 출력은 세로고, end=" "로 가로 출력 가능
★★★느낀점★★★
이렇게 4시간 들여서 공부해도 개념을 완전 응용못한다.ㅠ
혼자 2075번 다시 풀어보고
같은 구문이 쓰인 문제 1개 더 풀어봐야할 듯...?
하지만 지금 할 일이 밀렸는데 또 4시간이 걸릴까봐 두렵다.. 그래도 해야겠지
2075번 하나로 4시간 순삭_ 후기
처음 문제 봤을 땐 그냥 정렬 문제인 줄 알았다.
"N×N의 수 중 N번째로 큰 수를 출력하세요"
오잉? 그럼 그냥 2차원 배열을 한 줄로 펴서 정렬하고 [-N] 출력하면 되는 거 아냐?
근데 막상 그렇게 풀자니 시간 초과가 날 거 같고…
예제 출력은 맞는데 이상하게 찝찝하다. 그래서 결국 찾아보니 heapq를 쓰는 문제란다.
🧠 그때부터 뇌가 바쁘게 돌아가기 시작했다.
1. heapq? 뭐더라?
“힙큐…? 큐는 알겠는데 힙큐는 뭐였지…?”
“그냥 정렬해주는 큐인가? 왜 쓰지?”
“우선순위 큐래… 근데 정렬은 안 하고도 우선순위를 유지해준다고?”
그래서 개념부터 다시 정리함:
파이썬의 heapq는 기본이 최소 힙
heappop() 하면 가장 작은 수가 먼저 나온다
최대 힙은 따로 없다 → 그래서 -x로 음수 트릭을 써서 구현함
2. ??? 그럼 왜 큰 수를 찾는데 작은 수 힙을 써?
“작은 수가 먼저 나간다며? 그럼 어떻게 큰 수를 찾는 거야???”
★★★여기서 배운 포인트:
❗ 힙에 음수로 넣으면, 큰 수일수록 더 작은 수처럼 취급됨
그래서 -x로 넣고, 꺼낼 때 다시 -heappop()으로 복원하면
👉 “실제로는 가장 큰 수부터 꺼내는 효과”를 만들 수 있음
이걸 최대 힙 흉내내기라고 함.
3. list(map(int, input().split())) ← 이건 뭐야 또
진짜 제일 당황한 구문…
“list(map)이 뭔데? map만 치면 이상한 object만 나오는데?”
“왜 변수도 없고 for문도 없는데 x가 생겨?”
“왜 갑자기 정수로 다 바뀌어 있음???”
💡 깨달은 순간:
map(int, input().split())
→ input으로 받은 문자열 리스트에 int 함수를 각각 적용해주는 기계
list()로 감싸야 우리가 보기 좋은 리스트가 됨
map()은 그냥 자동 변환 공장
python
list(map(int, ["1", "2", "3"])) → [1, 2, 3]
그래서 이 구문은 입력 한 줄을 정수 리스트로 바꾸는 단골 패턴이었다.
4. 리스트 전체에 - 붙이면 안 돼?
나는 진짜로 -nums 같은 거 되는 줄 알았음
“그럼 그냥 heap = -nums 이렇게 하면 되잖아?”
❌ 에러 터짐. 왜냐면 리스트는 숫자 아니니까 - 연산이 안 됨
💡 해결: 리스트 컴프리헨션 써야 함
===========================
python
[-x for x in nums]
요소 하나하나에만 -가 붙게 만드는 방법!
5. len(heap) > N 이 왜 필요해?
이건 문제 핵심이었음.
“왜 > N이지? 딱 N개면 되는 거 아냐?”
“== N일 때 자르면 되는 거 아냐?”
“근데 왜 자꾸 6번째 들어오면 pop()해?”
✔️ 힙에 항상 N개의 큰 수만 유지하기 위한 전략
즉, 6번째가 들어올 때 가장 작은 수(= 음수로 넣은 값 중 절댓값 가장 작은 거)를 제거해서, 큰 수만 남기려고 그런 것.
6. while문 + heappop → 이게 정렬처럼 되네?
“근데 이건 그냥 정렬 아니잖아?”
“왜 결과는 정렬처럼 나와?”
결론: heappop()이 최소 힙이라서
가장 작은 값부터 차례로 나가기 때문
즉, 여러 번 꺼내면 결과적으로 정렬된 순서가 나온다
→ 이걸 정렬처럼 쓰는 경우도 많음
7. 출력이 왜 세로로 돼?
마지막까지 혼란 온 부분…
“왜 리스트는 가로로 출력되는데 이건 왜 세로야?”
알고 보니 while문으로 print() 여러 번 돌릴 때
print()는 기본적으로 줄바꿈 포함이라
하나씩 줄줄이 세로로 찍히는 거였다.
원하면 print(x, end=" ")로 가로 출력도 가능.
✅ 이 문제 하나로 얻은 개념 총정리
heapq의 기본은 최소 힙
최대 힙 구현 → 음수로 넣고, 꺼낼 때 다시 음수로 복원
map()은 반복 변환 기계. list()로 감싸야 실제 리스트로 보인다
리스트 전체에 - 붙이면 안 된다. 컴프리헨션 써야 한다
힙의 길이를 N개로 유지하면 N번째 큰 수가 남는다
heappop()을 반복하면 정렬처럼 꺼낼 수 있다
기본 출력은 세로고, end=" "로 가로 출력 가능
★★★느낀점★★★
이렇게 4시간 들여서 공부해도 개념을 완전 응용못한다.ㅠ
혼자 2075번 다시 풀어보고
같은 구문이 쓰인 문제 1개 더 풀어봐야할 듯...?
하지만 지금 할 일이 밀렸는데 또 4시간이 걸릴까봐 두렵다.. 그래도 해야겠지