https://www.acmicpc.net/problem/3653
3653번: 영화 수집
각 테스트 케이스에 대해서 한 줄에 m개의 정수를 출력해야 한다. i번째 출력하는 수는 i번째로 영화를 볼 때 그 영화의 위에 있었던 DVD의 개수이다. 상근이는 매번 영화를 볼 때마다 본 영화 DVD
www.acmicpc.net
세그먼트 트리 문제다. 접근방법이 떠오르지 않아 다른 분의 풀이를 보고 나서 풀었다.
풀이
n개의 DVD 중 임의의 DVD를 m번 선택한 뒤 시청한 뒤 가장 위에 놓는다는 얘기는 세그먼트 트리의 입장에서 n개의 DVD앞에 m개의 빈 공간이 필요하다는 얘기가 된다. 리프노드 m+n개를 표현할 수 있는 구간 합 세그먼트트리를 생성한다. 끝에서 n개 구간(m ~ m+n)에 하나씩 추가하여 처음 상태의 DVD 위치를 지정한다.
X번 DVD가 선택되면 [0 ~ X-1] 구간의 구간합을 반환하고 해당 DVD를 m-0번 구간으로 이동, 다음 선택된 DVD는 m-1번 구간으로 이동하면서 반복하면 된다. 예제를 기준으로 다음과 같이 그래프 상태를 그려볼 수 있다.
초기상태의 트리와 배열의 모습이다. 배열에는 1번부터 3번 DVD가 트리의 어느 구간에 있는지 나타낸다.
가장 먼저 3번 DVD의 경우 5번에 위치. 즉 0~4번까지의 구간합을 출력한다.
이후 자신의 위치를 DVD 진열의 최상단인 2번 인덱스로 이동. 이후 3번 DVD의 위치를 갱신해 준다.
다음으로 1번 DVD의 위치는 3번이니 0~2번 구간합을 출력한다.
이후 해당 DVD는 다음 최상단 인덱스인 1번으로 이동.
1번 DVD를 확인. 이번에는 0~0 구간의 구간합을 출력하면 된다.
마지막 위치인 0번으로 위치 갱신.
정답 코드
| import Foundation | |
| let T = Int(readLine()!)! | |
| var ans = [String]() | |
| for _ in 0..<T{ | |
| let nm = readLine()!.split(separator: " ").map{Int($0)!} | |
| let cmd = readLine()!.split(separator: " ").map{Int($0)!-1} | |
| var result = [String]() | |
| let n = nm[0] | |
| let m = nm[1] | |
| var arr = Array(repeating: 0, count: n) | |
| var tree = Array(repeating: 0, count: (n+m)*4) | |
| func update_tree(start:Int, end:Int, node:Int, idx:Int, value:Int){ | |
| if idx < start || end < idx{ | |
| return | |
| } | |
| tree[node] += value | |
| if start == end{ return } | |
| let mid = (start+end)/2 | |
| update_tree(start: start, end: mid, node: node*2, idx: idx, value: value) | |
| update_tree(start: mid+1, end: end, node: node*2+1, idx: idx, value: value) | |
| } | |
| func read_tree(start:Int, end:Int, node:Int, from:Int, to:Int) -> Int{ | |
| if end < from || to < start{ | |
| return 0 | |
| } | |
| if from <= start && end <= to{ | |
| return tree[node] | |
| } | |
| let mid = (start+end)/2 | |
| let left = read_tree(start: start, end: mid, node: node*2, from: from, to: to) | |
| let right = read_tree(start: mid+1, end: end , node: node*2+1, from: from, to: to) | |
| return left + right | |
| } | |
| for i in 0..<n{ | |
| update_tree(start: 0, end: n+m-1, node: 1, idx: i+m, value: 1) | |
| arr[i] = i+m | |
| } | |
| var newNumber = m-1 | |
| for i in 0..<m{ | |
| let number = cmd[i] | |
| let idx = arr[number] | |
| result.append("\(read_tree(start: 0, end: n+m-1, node: 1, from: 0, to: idx-1))") | |
| update_tree(start: 0, end: n+m-1, node: 1, idx: idx, value: -1) | |
| update_tree(start: 0, end: n+m-1, node: 1, idx: newNumber, value: 1) | |
| arr[number] = newNumber | |
| newNumber -= 1 | |
| } | |
| ans.append(result.joined(separator: " ")) | |
| } | |
| print(ans.joined(separator: "\n")) |
'Problem Solving > BOJ' 카테고리의 다른 글
| [3895] 그리고 하나가 남았다 (0) | 2023.03.24 |
|---|---|
| [3770] 대한민국 (0) | 2023.03.14 |
| [7578] 공장 (0) | 2023.03.11 |
| [1280] 나무 심기 (1) | 2023.03.09 |
| [1725] 히스토그램 (0) | 2023.03.07 |