알고리즘/자료구조(2)
-
백준 2346번: 풍선 터뜨리기 (C++)
https://www.acmicpc.net/problem/2346 2346번: 풍선 터뜨리기 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선 www.acmicpc.net 풀이 직접 구상하진 않고 친구에게 들은 방식으로 구현했다. 덱 자료구조를 사용해서 원형 큐 처럼 구현하면 된다고 들었다. 우선, 가장 앞에 있는 풍선의 값만큼 이동한다. 그 값이 양수라면, 앞에 있는 것들을 뒤로 붙여주고 음수라면 뒤에있는 것들을 앞에 붙인다. 즉, 양수일 때 -> push_back(front()) -> pop_front() 음수일 때 -> push_front(b..
2023.01.21 -
백준 1764번: 듣보잡 (C++)
https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 풀이 set 컨테이너를 활용하면 간단하게 풀 수 있다. 사전순 출력이기 때문에 번거롭게 정렬하지 않아도 된다. (set은 원소 자동 오름차순 정렬) 우선, 듣도 못한 사람을 s1에 저장한다. 그리고 보도 못한 사람을 입력 받을 때, s1에 있는 요소랑 같다면 s2에 저장한다. 그 후 s2 사이즈와 s2의 요소들을 출력한다. + 다른 사람 풀이를 보니 map으로 구현한 방법이 더 빠른 듯 하여 m..
2023.01.16