문제
연결 리스트는 다음 노드를 가리키는 노드에 값을 저장하므로 앞쪽에서 추가하거나 삭제하는 비용이 적습니다. 빈 상태에서 시작하는 리스트를 흉내 내세요.
연산을 순서대로 처리합니다:
push_front x: x를 맨 앞에 추가합니다.push_back x: x를 맨 뒤에 추가합니다.pop_front: 첫 번째 값을 삭제합니다(리스트가 비어 있으면 무시).remove x: 값이 x인 첫 번째 노드가 있으면 삭제합니다.reverse: 노드 순서를 뒤집습니다.
linked_list_operations(operations)를 구현하세요.
입력
operations: 연산 목록.
출력
리스트의 값을 앞에서 뒤 순서로 반환합니다.
제약 조건
0 ≤ 연산 수 ≤ 10,000
−10^9 ≤ x ≤ 10^9
예시
예시 1
입력:
operations = ["push_back 2", "push_front 1", "push_back 3", "reverse"]
예상 출력:
expected = [3, 2, 1]입력:
std::vector<std::string> operations = {"push_back 2", "push_front 1", "push_back 3", "reverse"};
예상 출력:
std::vector<long long> expected = {3, 2, 1};입력:
string[] operations = new string[] {"push_back 2", "push_front 1", "push_back 3", "reverse"};
예상 출력:
long[] expected = new long[] {3, 2, 1};설명
리스트는 1 → 2 → 3이 되고, 뒤집으면 [3, 2, 1]입니다.
예시 2
입력:
operations = ["push_back 5", "push_back 7", "push_back 5", "remove 5", "pop_front"]
예상 출력:
expected = [5]입력:
std::vector<std::string> operations = {"push_back 5", "push_back 7", "push_back 5", "remove 5", "pop_front"};
예상 출력:
std::vector<long long> expected = {5};입력:
string[] operations = new string[] {"push_back 5", "push_back 7", "push_back 5", "remove 5", "pop_front"};
예상 출력:
long[] expected = new long[] {5};설명
remove는 첫 번째 5만 지워 7 → 5가 남고, pop_front가 7을 지웁니다: [5].
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
앞뒤 삽입이 빠른 리스트 타입(std::list, LinkedList<T>, deque)이 대부분의 일을 해 줍니다.
힌트 2
remove는 처음 일치하는 것만 지우고, 빈 리스트의 pop_front는 아무 일도 하지 않습니다.
힌트 3
뒤집으면 이후 push와 pop에서 앞쪽이 되는 끝이 바뀝니다.
예상 복잡도
시간 O(n²), 추가 공간 O(n)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.