백준 BaaaaaaaaaaarkingDog님이 제작하신 문제집을 사용합니다
링크 : https://www.acmicpc.net/workbook/view/7308
문제집: 0x04강 - 연결 리스트 (BaaaaaaaaaaarkingDog)
www.acmicpc.net
무너져버린 코테 기초를 다시 쌓기 위해 유형별로 문제를 쭉쭉 밀기로 했다.
모든 문제를 풀고 필요할 경우 코멘트를 작성한다.
이 문제집의 3문제를 풀기 위해서는 C++ STL의 list 컨테이너를 이해하는 게 좋다. list의 구조는 대충 다음과 같다.
list에서 수행할 수 있는 기본 연산인 원소 이동, 값 참조, insert, erase에 대해 대충 알아보자.
>> 원소(그림에서 동그라미) 이동은 반복자 (그림에서 빨간 삼각형) 에 대한 ++, -- 연산을 통해 한 칸씩만 할 수 있다. +- 1 도 안 된다.
>> * 연산자를 통해 각 반복자의 값을 참조하면 바로 오른쪽의 원소를 가리킨다. L.end()는 오른쪽에 원소가 없으므로 오류가 발생한다.
>> insert(iter, value)는 현재 반복자 iter 자리에 value 원소를 추가한다. 또한 insert 수행 후 반복자 iter는 원래 가리키던 원소를 계속 가리키는 반면 insert는 새로 추가한 원소를 가리키는 반복자를 반환한다.
아래 그림은 2번 원소를 가리키는 반복자 iter에 대해 L.insert(iter, 10)을 수행한 결과이다.
따라서 iter가 원래 있던 '위치'(여기서는 '2번째')를 가리키게 하려면 iter = insert(iter, 값) 처럼 반환값을 사용하고,
원래 가리키던 '원소' (여기서는 원소 2)를 가리키게 하려면 insert(iter, 값) 처럼 반환값을 무시하면 된다.
>> erase(iter)는 현재 반복자가 가리키는 원소를 삭제한다. 또한 erase 수행 후 iter는 insert와 마찬가지로 원래 가리키던 원소를 가리켜야 하는데, 이 원소가 사라졌으므로 iter가 이상한 값을 갖게 된다. 반면 erase의 반환값은 삭제된 원소 다음 원소의 반복자가 된다.
아래 그림은 2번 원소를 가리키는 반복자 iter에 대해 L.erase(iter)를 수행한 결과이다.
따라서 iter를 그냥 사용하면 다음 iter 사용 시 오류가 발생하고, iter = erase(iter)로 반환값을 사용해 iter가 제대로 된 위치를 가리키도록 해야한다.
1406번 : 에디터 → 커서가 반복자라고 생각하면 간단해진다.
명령어 L은 --, D는 ++로 구현할 수 있다. B와 P는 커서 '왼쪽'에 대해 작업하므로, B는 -- 후 erase, P는 -- 후 insert하면 된다. 옮겼을 때 begin()과 end()를 넘어가지 않게 주의하고, insert와 erase 후 iter의 위치를 잘 고려해야 한다.
5397번 : 키로거 → 위의 에디터 문제와 동일하게 구현하면 된다.
1158번 : 요세푸스 문제 → 원래는 큐를 사용해서 푸는데 연결 리스트로도 풀 수 있다.
반복자를 K번 이동한 뒤 해당 원소를 출력하고 erase하면 되는데, iter = erase(iter)는 iter를 미리 한 번 이동시킨 것과 같으므로 매 반복문마다 반복자를 K-1번만 이동해야 한다.
푼 문제 : 3/3
총 소요 시간 : 40분
'백준 > 문제집(유기)' 카테고리의 다른 글
| 백준 문제집 풀이 6 - 덱 (1) | 2023.10.06 |
|---|---|
| 백준 문제집 풀이 5 - 큐 (1) | 2023.10.06 |
| 백준 문제집 풀이 4 - 스택 (0) | 2023.09.28 |
| 백준 문제집 풀이 2 - 배열 (0) | 2023.09.26 |
| 백준 문제집 풀이 1 - 기초 코드 작성 요령 II (0) | 2023.09.26 |