https://www.acmicpc.net/problem/5676
5676번: 음주 코딩
각 테스트 케이스마다 곱셈 명령의 결과를 한 줄에 모두 출력하면 된다. 출력하는 i번째 문자는 i번째 곱셈 명령의 결과이다. 양수인 경우에는 +, 음수인 경우에는 -, 영인 경우에는 0을 출력한다.
www.acmicpc.net
세그먼트트리 문제다.
풀이
단순히 구간 곱 구하기 문제처럼 구하게 된다면 100¹⁰⁰⁰⁰⁰의 수를 담아야 하기에 오버플로우가 발생한다. 즉 해당 문제는 음수, 양수, 0인지 구하면 되는 문제이기에 입력되는 수를 1,0,-1 만으로 트리를 구성하여 결과를 출력하면 된다. 처음 문제를 읽었을 때 입력되는 수를 100 * 10⁵으로 판단하여 일반적인 구간 곱 형태의 트리로 접근하였다가 오답판정을 받았다.
정답 코드
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import Foundation | |
| var ans = [String]() | |
| while let line = readLine(){ | |
| var res = "" | |
| let NK = line.split(separator: " ").map{Int($0)!} | |
| let N = NK[0] | |
| let K = NK[1] | |
| var arr = readLine()!.split(separator: " ").map{Int($0)!} | |
| var tree = Array(repeating: 1, count: N*4) | |
| func make_tree(from:Int, to:Int, idx:Int)->Int{ | |
| if from == to{ | |
| arr[from] = arr[from]<0 ? -1: arr[from]>0 ? 1:0 | |
| tree[idx] = arr[from] | |
| return tree[idx] | |
| } | |
| let mid = (from+to)/2 | |
| let left = make_tree(from: from, to: mid, idx: idx*2) | |
| let right = make_tree(from: mid+1, to: to, idx: idx*2+1) | |
| tree[idx] = left*right | |
| return tree[idx] | |
| } | |
| func update_tree(from:Int, to:Int, node_idx:Int, target_idx:Int, value:Int) -> Int{ | |
| if target_idx < from || to < target_idx{ | |
| return tree[node_idx] | |
| } | |
| if from == to{ | |
| arr[target_idx] = value | |
| tree[node_idx] = value | |
| return tree[node_idx] | |
| } | |
| let mid = (from+to)/2 | |
| let left = update_tree(from: from, to: mid, node_idx: node_idx*2, target_idx: target_idx, value: value) | |
| let right = update_tree(from: mid+1, to: to, node_idx: node_idx*2+1, target_idx: target_idx, value: value) | |
| tree[node_idx] = left*right | |
| return tree[node_idx] | |
| } | |
| func read_tree(from:Int, to:Int, idx:Int, min:Int, max:Int) -> Int{ | |
| if to < min || max < from{ | |
| return 1 | |
| } | |
| if min <= from && to <= max{ | |
| return tree[idx] | |
| } | |
| let mid = (from+to)/2 | |
| let left = read_tree(from: from, to: mid, idx: idx*2, min: min, max: max) | |
| let right = read_tree(from: mid+1, to: to, idx: idx*2+1, min: min, max: max) | |
| return left*right | |
| } | |
| make_tree(from: 0, to: N-1, idx: 1) | |
| for _ in 0..<K{ | |
| let line = readLine()!.split(separator: " ").map{String($0)} | |
| let cmd = line[0] | |
| if cmd == "C"{ | |
| let i = Int(line[1])!-1 | |
| var v = Int(line[2])! | |
| update_tree(from: 0, to: N-1, node_idx: 1, target_idx: i, value: v<0 ? -1:v>0 ? 1:0) | |
| }else{ | |
| let i = Int(line[1])!-1 | |
| let j = Int(line[2])!-1 | |
| let tmp = read_tree(from: 0, to: N-1, idx: 1, min: i, max: j) | |
| if tmp < 0{ | |
| res+="-" | |
| }else if tmp == 0{ | |
| res+="0" | |
| }else{ | |
| res+="+" | |
| } | |
| } | |
| } | |
| ans.append(res) | |
| } | |
| print(ans.joined(separator: "\n")) |
'Problem Solving > BOJ' 카테고리의 다른 글
| [3745] 오름세 (0) | 2023.02.26 |
|---|---|
| [12837] 가계부 (Hard) (0) | 2023.02.23 |
| [18436] 수열과 쿼리 37 (0) | 2023.02.21 |
| [14438] 수열과 쿼리 17 (0) | 2023.02.20 |
| [1306] 달려라 홍준 (0) | 2023.02.18 |