[백준(BOJ)] 2075번 N번째 큰수 C++

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

2075번: N번째 큰 수

어떤 문제인가?

문제는 특별히 어렵지 않았다.

N x N 표에 있는 숫자들 중 N번째로 큰 수를 출력하면 끝이다.

 

접근 방법

처음에는 문제의 메모리 제한과 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 조건 때문에 표의 일부분만 뽑은 그룹에서 N번째 큰 수를 찾으려고 했다. 그렇게 벡터를 사용해서 구현을 했고 테스트케이스는 통과해서 제출했지만 오답이었다.

 

 

 

int n;
cin >> n;
int arr[n*n];

for(int i=0;i<n*n;i++){
    cin >> arr[i];
}

다시 천천히 생각해보다가 그냥 입력 받은 모든 수를 정렬해볼까? 라는 생각에 1차원 배열에 모든 입력받은 수를 넣었다.

 

sort(arr, arr+n*n,greater<>());

그 다음 오름차순으로 배열을 정렬했다.

 

 

cout << arr[n-1];

당연히 값은 잘 나왔고 제출했다. 그랬더니 시간초과가 떴다.

 

ios_base::sync_with_stdio(false);
cin.tie(NULL);

ios_base::sync_with_stdio(false), cin.tie(null)구문을 추가해 제출해보니 통과할 수 있었다.

 

무엇이 어려웠나?

원래 알고 있던 지식 선에서도 해결 가능해서 어렵다고 느껴지진 않았다.

 

배운 점

문제를 풀기전에 시간제한과 메모리 제한을 보고 대충 어떤식으로 풀이를 해야할지 생각해야겠다는 것을 배웠다.

내가 생각한 풀이의 시간과 메모리에 대해 생각해보기!

 

+ ios_base::sync_with_stdio(false), cin.tie(null)구문은 항상 붙이도록 노력하기!

 

시간 복잡도

입력 n에 대해 n*n번 숫자를 입력받아야 한다.

따라서 시간 복잡도는 O(N^2)이 된다.

 

 

https://github.com/farmJun/Algorithm_BOJ_PS/blob/main/%EC%8D%B8%EB%A8%B8%EC%BD%94%EB%94%A9/2075.cpp

GitHub - farmJun/Algorithm_BOJ_PS: 백준 알고리즘 문제풀이 기록 레포짓입니다.