오랜만에 알고리즘 문제를 풀어보기로 결심했다. 예전에는 BOJ 사이트에서 문제를 주로 풀었었는데 알고리즘 분류 카테고리를 통해 문제가 어떤 유형인지 미리 알고 풀었었다. 이 방법은 기업 코딩 테스트를 대비한다면 절대 지양해야한다. 기업 코테에서는 문제 유형을 알려주지 않는다. 즉, 이 수능 비문학 문제들이 연상되는 지문들을 읽고 어떤 알고리즘 기법으로 문제를 해결해야할지조차 스스로 해석해야한다는 것이다.
이 글을 기점으로 BOJ 인기 문제집과 프로그래머스 문제 풀이를 꾸준히 업로드해볼 계획이다.
문제 설명
솔직하게 뭔 소린지 이해하는데 10분 정도 걸린 것 같다.
문제의 골자는 이러함.
- 입력되는 숫자들 중에서 매번 가운데 숫자를 출력
- 홀수 일 때는 가운데 숫자, 짝수일 때는 가운데 두 개의 수 중 더 작은 숫자를 출력
그러니까 위 입력 예시에서는 입력 횟수인 7이 먼저 입력되고 그 뒤로 숫자들이 차례대로 입력이 된다. 이때 매번 이 숫자들을 순서대로 정렬 했을 때 가운데 숫자를 출력하라는 것이다.
말로 설명하기 힘들어서 끄적인거 올림.
입력된 숫자를 배열에 저장해서 정렬했을 때 숫자 개수가 홀수 일 땐 그냥 가운데 숫자를 출력하면 되고 짝수일 때는 가운데 수가 2개가 되니, 그 중 작은 수를 출력하면 된다.
문제 풀이
우선 입력을 어떻게 받을지 정해야한다. 맨 처음 입력될 숫자 N개에 대한 정보가 주어지니, 반복문을 이용해 N번 입력을 받아보자.
1
2
3
4
let N = Int(readLine()!)!
for _ in (1...N) {
Int(readLine()!)!
}
그 다음 생각해야할 부분은 입력되는 숫자가 계속 누적되어야 한다는 점이다. 숫자를 저장할 배열을 하나 만들고 숫자를 저장해보자.
1
2
3
4
5
let N = Int(readLine()!)!
var numbers: [Int] = []
for _ in (1...N) {
numbers.append(Int(readLine()!)!)
}
매 주기마다 저장된 숫자를 정렬해서 가운데 수를 찾아야한다. 가운데 수를 찾을 공식을 생각해보자.
- 짝수일 때는 가운데 두 수 중 더 작은 수
- 홀수일 때는 가운데 수 정렬된 상태에서 짝수일 때 가운데 두 수 중 더 작은 수는 항상 왼쪽 숫자가 된다.
예를 들어 [1, 2, 5, 10] 에서 가운데 두 수는 2, 5지만 더 작은 수는 항상 왼쪽 숫자인 2임. 정렬된 상태니까.
그래서 가운데 숫자의 index를 구하는 공식을 아래처럼 생각해봤다.
1
let index = numbers.count % 2 == 0 ? numbers.count/2 - 1 : number.count/2
삼항 연산자를 사용해서 조금 가독성이 떨어지지만, 풀이해보자면
- 배열 개수가 짝수라면 배열 개수를 2로 나눈 값의 - 1 이 가운데 수
- 배열 개수가 홀수라면 배열 개수를 2로 나누면 가운데 수
[1, 2, 5, 10] 을 예시로 들어보자. 배열 개수는 4인데 2로 나누면 2가 된다. 이때의 값은 짝수일 때 가운데 두 수 중 항상 오른쪽 수의 index가 된다. 즉 여기서 - 1만 해주면 정렬된 상태에서는 더 작은 수의 index임을 보장할 수 있다.
[-99, 1, 2, 5, 10] 일 때는 배열 개수가 5이다. 여기서 2로 나누면 딱 나눠떨어지지 않지만 / 연산자는 몫을 구하는 연산자기 때문에 2가 된다. 홀수일 때는 절반으로 나누기만 해도 가운데 숫자의 index를 구할 수 있다.
1
2
3
4
5
6
7
8
let N = Int(readLine()!)!
var numbers: [Int] = []
for _ in (1...N) {
numbers.append(Int(readLine()!)!)
let index = numbers.count % 2 == 0 ? numbers.count/2 - 1 : numbers.count/2
print(numbers.sorted()[index])
}
위와 같이 작성해서 테스트해보니 입출력 값은 예제와 똑같이 동작한다. 그러나 한가지 문제가 발생한다.
바로 시간 초과. 찾아보니 이 문제는 최대 힙과 최소 힙을 활용해서 풀어야하는 문제라고 한다. 최대 힙과 최소 힙에 대해 배운 뒤 다시 도전해보자.