백준 BaaaaaaaaaaarkingDog님이 제작하신 문제집을 사용합니다
링크 : https://www.acmicpc.net/workbook/view/7311
무너져버린 코테 기초를 다시 쌓기 위해 유형별로 문제를 쭉쭉 밀기로 했다.
모든 문제를 풀고 필요할 경우 코멘트를 작성한다.
10866번 : 덱 → deque STL을 이용한다. map<string, int>로 명령을 매핑하면 코드가 간결해진다.
1021번 : 회전하는 큐 → 문제에서 '뽑아낸다'라는 표현은 1번 연산의 '첫 번째 원소를 뽑아낸다', 즉 D.front() 에 해당한다.
즉 덱을 적당히 회전시켜, 두 번째 줄에 있는 각 위치의 원소를 D.front()에 보내면 된다. 원소의 위치라고 해서 복잡하게 생각하지 말고 1부터 N까지 값을 덱에 집어넣고 이를 위치라고 생각하자.
다음 값 next을 front에 보내기 위해 할 수 있는 선택지는 계속 왼쪽/오른쪽으로 돌리기 2가지 밖에 없다. 따라서 최소 이동 횟수를 구하기 위해 next의 현재 위치에서 D.front() 즉 0번 인덱스까지 왼쪽으로 이동했을 때와 오른쪽으로 이동했을 때 거리 중 더 짧은 쪽을 선택하면 된다.
5430번 : AC → R의 홀짝 여부에 따라 pop_back, pop_front를 호출하고, 연산이 모두 끝나고 R이 홀수 번 등장했을 경우 문자열을 뒤집는다. 문자열 파싱이 더 까다로웠던 문제로, erase같은 string 메소드 대신 그냥 정직하게 문자열을 스캔하면서 파싱하는 편을 추천한다.
11003번 : 최솟값 찾기 → 일단 덱에는 값 자체 대신 인덱스를 저장해야 하고, 덱 내부에서 인덱스에 해당하는 배열의 값을 항상 오름차순으로 관리해야 한다. 매번 새로 읽어들이는 원소 new가 덱의 맨 끝에 위치하게, 즉 최댓값이 되게 하면 된다.
풀이
덱의 끝에서부터 new보다 큰 값을 모두 제거(pop_back)하고 new를 삽입(push_back)한다. 덱을 오름차순으로 관리하므로 front에는 항상 최솟값이 존재한다. 단 new의 인덱스 i에 대해 최솟값을 구하는 구간이 (i-L+1) ~ i이므로, 최솟값을 갖는 front의 인덱스가 해당 구간 밖에 위치한다면 모두 삭제(pop_front)한다.
예제 입력의 일부 구간에 대해 알고리즘 수행 과정을 확인해보자.

푼 문제 : 4/4
총 소요 시간 : 1시간 20분
'백준 > 문제집(유기)' 카테고리의 다른 글
백준 문제집 풀이 8 - BFS (0) | 2023.10.06 |
---|---|
백준 문제집 풀이 7 - 스택의 활용 (1) | 2023.10.06 |
백준 문제집 풀이 5 - 큐 (1) | 2023.10.06 |
백준 문제집 풀이 4 - 스택 (0) | 2023.09.28 |
백준 문제집 풀이 3 - 연결 리스트 (0) | 2023.09.28 |