문제 풀기 (38) 썸네일형 리스트형 [코딩인터뷰 완전정복] 2.4 분할 Q : 값 x가 주어졌을 때 x보다 작은 노드들을 x보다 크거나 같은 노드들보다 앞에 오도록 하는 코드를 작성하라. 만약 x가 리스트에 있다면 x는 '오른쪽 그룹' 어딘가에만 존재하면 된다. 왼쪽과 오른쪽 그룹 사이에 있을 필요는 없다. ...더보기 // LinkedList.h #include struct node { int data; node *next; }; class linked_list { private: node *head, *tail; public: linked_list() { head = NULL; tail = NULL; } node* add_node(int n) { node *temp = new node; temp->data = n; temp->next = NULL; if (head == .. [코딩인터뷰 완전정복] 2.3 중간 노드 삭제 Q : 단방향 연결리스트가 주어졌을 때 중간에 있는 노드하나를 삭제하는 알고리즘을 작성하라. 단 삭제할 노드에만 접근 할 수 있다. ...더보기 // LinkedList.h #include struct node { int data; node *next; }; class linked_list { private: node *head, *tail; public: linked_list() { head = NULL; tail = NULL; } node* add_node(int n) { node *temp = new node; temp->data = n; temp->next = NULL; if (head == NULL) { head = temp; tail = temp; } else { tail->next = tem.. [코딩인터뷰 완전정복] 2.2 뒤에서 K번째 원소 구하기 Q : 단방향 연결 리스트가 주어졌을 때 뒤에서 k번째 원소를 찾는 알고리즘을 구현하라. ...더보기 // linked_list.h #include struct node { int data; node *next; }; class linked_list { private: node *head, *tail; public: linked_list() { head = NULL; tail = NULL; } void add_node(int n) { node *temp = new node; temp->data = n; temp->next = NULL; if (head == NULL) { head = temp; tail = temp; } else { tail->next = temp; tail = tail->next; } .. [코딩인터뷰 완전정복] 2.1 중복 없애기 Q : 정렬되어 있지 않은 연결리스트가 주어졌을 때 이 리스트에서 중복되는 원소를 제거하는 코드를 작성하라. + 임시 버퍼를 사용할 수 없다면 어떻게 풀 수 있을까? 우선 연결리스트를 준비한다. ...더보기 #include struct node { int data; node *next; }; class linked_list { private : node *head, *tail; public: linked_list() { head = NULL; tail = NULL; } void add_node(int n) { node *temp = new node; temp->data = n; temp->next = NULL; if (head == NULL) { head = temp; tail = temp; } else.. [코딩인터뷰 완전정복] 1.9 문자열 회전 Q : 한단어가 다른 문자열에 포함되어 있는지 판별하는 isSubstring 이라는 메서드가 있다고 하자. s1과 s2의 두 문자열이 주어졌을때 s1이 s2의 회전인지 판별하고자 한다. isSubstring을 1번만 호출해서 판별할 수 있는 코드를 작성하라. 회전 : abcde → cdeab s1을 문자열 xy로 나눴을때 yx는 s1의 회전이다. 단순하게 생각해보면 y가 s2의 처음에 나오는지 확인하고 그 뒤가 x와 일치하는지 확인하면 되지만 이 방법은 isSubstring을 1번만 호출하라는 지시에 맞지 않다. bool isRotate(string s1, string s2){ return isSubstring(s1+s1, s2); } 조금 더 생각을 해보자. s1 = xy , s2 = yx 라고 한다면.. [코딩인터뷰 완전정복] 1.8 O행렬 Q : M * N 행렬의 한 원소가 0일 경우, 해당 원소가 속한 행과 열의 모든 원소를 0으로 설정하는 알고리즘을 작성하라. #include int** OMatrix(int** input, int m, int n) { bool* horizen0; bool* vertical0; horizen0 = new bool[m]; vertical0 = new bool[n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (input[i][j] == 0) { horizen0[i] = 1; vertical0[j] = 1; } } } for (int i = 0; i < m; i++) { if (horizen0[i] == 1) { for (int j = 0.. [코딩인터뷰 완전정복] 1.7 행렬 회전 Q : 이미지를 표현하는 N*N 행렬이 있다. 이미지의 각 픽셀은 4바이트로 표현된다. 이때, 이미지를 90도 회전시키는 메서드를 작성하라. 행렬을 추가로 사용하지 않고서도 할 수 있겠는가? #include int** RotateMatrix(int* matrix[], int n) { int temp; for (int i = 0; i [코딩인터뷰 완전정복] 1.6 문자열 압축 Q : 반복되는 문자의 개수를 세는 방식의 기본적인 문자열 압축 메서드를 작성하라. 만약 압축된 문자열의 길이가 기존문자열보다 길다면 기존 문자열을 반환한다. A : 1. 하나의 문자를 읽어와서 저장한다. 카운트를 1로 한다. 2. 다음 문자를 읽어와서 저장된 문자와 같다면 카운트를 1올린다. 3. 다른 문자가 나올때까지 2를 반복. 4. 다른 문자가 나올경우 압축 문자열에 저장된문자와 카운트를 추가한다. 5. 압축문자열이 기존문자열보다 길어지거나 문자열이 끝날때까지 1부터 반복. 6. 압축문자열이 기존문자열보다 길다면 기존문자열을 반환. 아닐경우 압축 문자열을 반환 이전 1 2 3 4 5 다음