목록스택 (4)
beepbeep
문제 주어진 연결 리스트가 회문 구조인지 확인하는 문제이다. 살펴보기 문제를 보고 가장 먼저 생각난 방법은 리스트를 이용하는 방법이었다. 리스트를 만들어 노드값을 전부 저장한 후, 반복문을 이용해 리스트의 양끝에서부터 가운데로 순회하면서 양쪽의 값을 비교해 회문인지 확인하는 방법이다. 그래서 우선 리스트를 이용해 문제를 푼 다음, 206번 문제를 풀 때 배운대로 뒤집힌 연결 리스트를 만든 후 원본 연결 리스트랑 비교하는 방식으로 풀어보았다. 의도했던 대로 문제를 풀긴 했지만.. 더 좋은 풀이가 있는걸 알게 되어서 풀이를 참고해 한번 더 풀어보았다. 우선 두 개의 포인터를 이용해, 연결 리스트의 중간 지점을 찾아야 한다. 160번 문제에서 했던 것처럼 한 포인터(slow)는 한 번에 한칸씩만 이동하고, 다..
문제 주어진 이진 트리를 후위 순회하는 문제이다. 살펴보기 저번에 본 144번 문제와 마찬가지로 이진 트리를 막 배웠을 때 기본 개념을 복습하기 좋은 문제같다! 후위 순회는 1. 왼쪽 하위 트리를 먼저 순회하고 2. 오른쪽 하위 트리를 순회한 다음 3. 마지막으로 현재 노드를 방문하는 방식의 순회이다. 144번 문제와 비슷한 방식으로 풀되, 현재 노드의 값을 리스트에 저장하는 시점을 하위 트리 순회가 끝난 후로 미루었다. 풀어보기 public List postorderTraversal(TreeNode root) { List list = new ArrayList(); if(root!=null){ postorderTraversal(list, root); } return list; } public void p..
문제 주어진 이진 트리를 전위 순회하면서 노드 값을 리스트에 저장해 반환하는 문제이다. 살펴보기 전위 순회를 막 배운 시점에서 개념을 복습하기 좋은 문제같다! 전위 순회는 1. 현재 노드를 먼저 방문하고 2. 그 다음 왼쪽 자식 노드를 순회한 후 3. 마지막으로 오른쪽 자식 노드를 순회하는 방식이다. 풀어보기 노드값을 저장할 리스트를 선언한 후, 반환값이 void인 preorederTraversal 메서드를 호출해 리스트와 루트를 전달한다. 현재 노드가 null이면 return문을 통해 재귀 함수의 수행을 멈춘다. null이 아닌 경우 리스트에 현재 노드의 값을 추가한 후, 왼쪽 자식 노드가 있으면 preorederTraversal 메서드를 다시 호출해 리스트와 왼쪽 자식 노드를 전달해 순회한다. 왼쪽 ..
문제 살펴보기 주어진 문자열에서 숫자를 찾아 모두 더하되, 숫자가 아닌 "Z"를 만나면 이전에 더했던 값을 지워야 한다. 생각의 흐름 우선 주어진 문자열을 split() 메서드를 이용해 배열 형태로 바꾼다. 반복문을 이용해서 현재 문자열이 "Z"가 아니면 현재 인덱스에 해당하는 값을 누적하고, "Z"면 이전 인덱스에 해당하는 값을 뺐다. 처음 풀 때는 stack을 떠올리지 못해서, stack을 사용해서 다시 풀었다. stack을 사용할 경우, 현재 문자열이 "Z"이면 .pop() 메서드를 이용해 마지막에 쌓은 값을 제거해주면 된다. 풀어보기 Stack을 사용하지 않은 경우 String[] arr = s.split(" "); int answer = 0; for(int i=0; i