PQ1 BOJ G2 1655 가운데를 말해요 JAVA 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 문제 읽기 맨 처음에 문제를 읽자마자 트리 형태가 먼저 생각났다. 하나씩 숫자를 넣으면서 중간 값을 찾아낼 수 있지 않을까 하는 생각. 하지만 자료구조를 본 게 시간이 좀 지나서 어떤 식으로 구현해야 할 지는 감이 잘 잡히지 않았다. 그 다음 생각난 접근은 정렬이다. 하나씩 값이 들어오고, 값이 몇 개 들어왔는지 알 수 있고.. 그렇다면 삽입 정렬을 하면 되지 않을까 싶었다. 하지만 삽입 정렬의 시간복잡도는 최악의 경우 N^2이기 때문에(문제에서.. 2024. 1. 11. 이전 1 다음
