Algorithm/연결리스트

[알고리즘] 리트코드 19. 리스트 끝에서 N번째 노드 제거 c++ // 노드탐색

https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/* 내풀이size를 찾고prev값이 없길래 저장하고,제거대상인 노드인경우, prev->next = cur->next로 바꿔줬다.ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ결과 :맨앞의 노드를 제거하는경우 오답이났음.이경우는 head = head -> next를 리턴하면 됬다./** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next..

리트코드 2. 두개의숫자추가 c++ // stoi 주의점, 노드 begin 저장방법, 두 링크드리스트 덧셈방법

https://leetcode.com/problems/add-two-numbers/description/ * stoi 주의점21억( 2,147,483,647 )== 문자열로 10자리만 벗어나도 out of range 가뜸-> stoll을 사용할것 ( 9,223,372,036,854,775,807)-한계 : 20자리이상은 불가능함.-> 숫자계산으로 구현해야함. 문자열꼼수 안통해 * 기존코드숫자를 문자열로 바꾸면서 덧셈하고해당 숫자를 다시 노드로 바꿈- 문제 : stoi 에서 stoll로 해도 ll의 범위도 벗어나버림/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * List..

프로그래머스 표편집 c++ // 연결리스트 직접구현 하는방법, 삽입삭제 되돌리기는 연결리스트(직접구현)!

https://school.programmers.co.kr/learn/courses/30/lessons/81303 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 고찰 stl의 list를 쓰면 풀수없는듯 하다. 이유 : prev,next 가 없음.. - 삽입삭제, 되돌리기는 연결리스트(직접구현)! - 삭제된 노드도 prev,next가 남아있기때문에 복원이 ez하다! 2.전체코드 #include using namespace std; struct Node{ int n; Node* prev; Node* next; Node(int n, Node* prev, ..

백준 1158 cpp // 연결리스트 풀이, int_to_string(int), List.erase() 주의사항

https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net *의사코드 1. [1, 2, 3,4,5,6,7] List에 push 2. 2회(k-1)회 만큼 커서++ 3. 단, end이면 시작점으로 돌리기 *문제 : 밑에줄에 now=L.erase()가 문제였다. erase는 다음원소 idx를 반환 -> 끝숫자가 지워지면 now가 end포인터가됨 /* * 문제 : 에서 * 7이 지워지면 * now가 end가 됨. * 해결 : end이면 시작점으로 바꿔주기 */ if (now == L.end()) { now = L.begin(); } * 문제 2 : 문..

백준 5397 cpp// 연결리스트 메모장

https://www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net * 주의 L.insert에서는 cursor갱신 필요없다. 이유 : 에서 커서 이동을 처리하므로. #include using namespace std; int tc; list L; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> tc; while (tc--) { string s; cin >> s; auto ..

백준 1406 cpp // 연결리스트 사용법

https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net * 연결리스트 장점 : 삽입이 O(1) 이다. 단점 : 조회가 O(N)이다. 사용처 : 메모장 구현 등 삽입,삭제가 빈번할 때 코테키워드 : 메모장, 커서 *메소드 L.insert(idx,값) // 삽입한놈 idx 반환 L.erase(idx) // 삭제한 다음놈 idx 반환 L.end() // 마지막원소 다음 idx 반환 #include using namespace std; string s; int..