기로에 서다

문제 www.acmicpc.net/problem/16402 16402번: 제국 배성일력 73년, 대륙을 주름잡던 성일 제국은 무리한 정복 전쟁 끝에 멸망하게 되었다. 기회를 노리던 반란군들은 혼란을 틈타 제각각 왕국을 선포했고, 왕국들은 제국의 자리를 차지하기 위해 � www.acmicpc.net 문제 풀이 1. 유니온파인드로 집합을 관리하기 위해 각 국의 이름을 입력받은 후 파싱하여 map에 순으로 저장한다. 2. 위와 마찬가지로 각 국의 이름과 관계도 적절히 파싱한 후에 이기는 국가가 앞쪽으로 오도록 두 집합을 합쳐준다. 3. 합칠 때는 아래의 세가지 경우가 존재하고, 맨 위 두가지 경우는 같다고봐도 무방하다. (∵ 종주국 v의 부모는 pv) 종주국(u)이 종주국(v)을 이길 때 : u가 v의 속국으..

문제 www.acmicpc.net/problem/19591 19591번: 독특한 계산기 숫자, '+', '*', '-', '/'로만 이루어진 길이가 106 이하인 수식이 주어진다. 계산 과정 중의 모든 수는 −263 이상 263 미만이며, 0으로 나누는 경우는 없다. 숫자 앞에 불필요한 0이 있을 수 있다. www.acmicpc.net 문제 풀이 1. 파싱 : 문자열을 숫자와 연산자로 파싱하는 과정이 까다롭지만 연산자가 나왔을 때, 연산자는 연산자대로 저장하고 그동안의 숫자들을 하나의 숫자로 묶어서 저장하면 쉽게 파싱할 수 있습니다. (첫 수가 음수일때 예외처리) 2. 자료구조 : 연산할 때 맨 앞과 뒤에 접근하므로 덱을 사용하여 숫자, 문자들을 관리할 수 있습니다. 3. 주어진 조건대로 연산자의 우선순..