GitHub ID : soohyun-dev
윤수현의 개발 공간
GitHub ID : soohyun-dev
전체 방문자
오늘
어제
  • 분류 전체보기 (918)
    • 성장기록 (49)
      • 성장기록 (3)
      • 우아한테크코스 (16)
      • 프로젝트 (15)
      • TIL (14)
      • 테오의 스프린트 (1)
    • 프로그래밍언어 (88)
      • C언어 (14)
      • HTML\CSS (12)
      • JavaScript (7)
      • React (23)
      • Python (11)
      • JAVA (14)
      • TypeScript (6)
    • 알고리즘 공부 (736)
      • 코드업 - 파이썬 (108)
      • 백준 - 파이썬 (468)
      • 백준 - 자바스크립트 (125)
      • 프로그래머스 - 파이썬 (1)
      • 프로그래머스 - 자바스크립트 (34)
    • 책 리뷰 (9)
      • 프로그래밍 (3)
      • 독서 (6)
    • 전자기기 (1)
    • 일상, 일기 (18)
    • 기술 세미나 (2)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 코드업파이썬
  • 백준파이썬
  • 코딩테스트
  • PYTHON
  • 프로그래머스
  • 자바스크립트
  • 프로그래머스자바스크립트
  • 프론트엔드
  • 독해
  • 영어독해
  • 프로그래머스풀이
  • 영어
  • 파이썬
  • 코테
  • 백준풀이
  • javascript
  • 코드업
  • 백준
  • 코딩
  • 프로그래밍언어

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
GitHub ID : soohyun-dev

윤수현의 개발 공간

백준/ Silver 2 문제 , 백준 파이썬 2075 , N번째 큰 수
알고리즘 공부/백준 - 파이썬

백준/ Silver 2 문제 , 백준 파이썬 2075 , N번째 큰 수

2022. 6. 24. 15:11

백준/ Silver 2 문제 , 백준 파이썬 2075 , N번째 큰 수

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
heap을 이용하여 입력을 받을때마다 정렬 후 마지막 첫번째 원소를 출력

 

<문제 출처>

 

https://www.acmicpc.net/problem/2075

 

2075번: N번째 큰 수

첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다.

www.acmicpc.net

 

 

 

------------------------------------------------------------------------------------------------------------------------------

 

 

N x N 행렬 형태중에서 N 번째로 큰 숫자를 찾는 문제이다.

 

N개의 heap 을 가지고 1행 부터 N행까지 쭉 확인해가며 숫자들을 계속 초기화 시켜준다.

 

마지막 행의 원소를 지나면 N 개의 heap 만 남아있을텐데,

 

오름 차순으로 정렬되어있고, 그 heap의 0번째 인덱스가 전체에서 N번째로 큰 수 이다.

 

추가로, -1 번째 인덱스는 당연히 입력받은 숫자들에서 가장 큰 수 이다.

 

 

 

 

입력을 한번에 받아 저장한 뒤 처리하려면 메모리 초과가 발생한다.

 

그러니, 1행씩 입력을 받자마자 처리한다.

 

 

 

 

 

------------------------------------------------------------------------------------------------------------------------------

정답

 

 

 

import heapq
import sys
input=sys.stdin.readline

N=int(input())
heap=[]
heapq.heapify(heap)

for _ in range(N):
    tmp=list(map(int,input().split()))
    for i in range(N):
        heapq.heappush(heap, tmp[i])
        if len(heap)>N:
            heapq.heappop(heap)
            
print(heap[0])

 

 

반응형

'알고리즘 공부 > 백준 - 파이썬' 카테고리의 다른 글

백준/ Silver 5 문제 , 백준 파이썬 1251 , 단어 나누기 , 정렬  (0) 2022.06.24
백준/ Bronze 1 문제 , 백준 파이썬 2309 , 일곱 난쟁이 , 정렬  (0) 2022.06.24
백준/ Silver 4 문제 , 백준 파이썬 13305 , 주유소  (0) 2022.06.23
백준/ Bronze 3 문제 , 백준 파이썬 17174 , 전체 계산 횟수  (0) 2022.06.22
백준/ Bronze 2 문제 , 백준 파이썬 15829 , Hashing  (0) 2022.06.21
    '알고리즘 공부/백준 - 파이썬' 카테고리의 다른 글
    • 백준/ Silver 5 문제 , 백준 파이썬 1251 , 단어 나누기 , 정렬
    • 백준/ Bronze 1 문제 , 백준 파이썬 2309 , 일곱 난쟁이 , 정렬
    • 백준/ Silver 4 문제 , 백준 파이썬 13305 , 주유소
    • 백준/ Bronze 3 문제 , 백준 파이썬 17174 , 전체 계산 횟수
    GitHub ID : soohyun-dev
    GitHub ID : soohyun-dev
    환영합니다!😊 이곳은 저의 개발에 관한 내용들을 정리하는 공간입니다. 알고리즘 풀이에도 관심이 많아요. 좋은 하루 되세요~! github : soohyun_dev

    티스토리툴바