beepbeep

문제 주어진 연결 리스트가 회문 구조인지 확인하는 문제이다. 살펴보기 문제를 보고 가장 먼저 생각난 방법은 리스트를 이용하는 방법이었다. 리스트를 만들어 노드값을 전부 저장한 후, 반복문을 이용해 리스트의 양끝에서부터 가운데로 순회하면서 양쪽의 값을 비교해 회문인지 확인하는 방법이다. 그래서 우선 리스트를 이용해 문제를 푼 다음, 206번 문제를 풀 때 배운대로 뒤집힌 연결 리스트를 만든 후 원본 연결 리스트랑 비교하는 방식으로 풀어보았다. 의도했던 대로 문제를 풀긴 했지만.. 더 좋은 풀이가 있는걸 알게 되어서 풀이를 참고해 한번 더 풀어보았다. 우선 두 개의 포인터를 이용해, 연결 리스트의 중간 지점을 찾아야 한다. 160번 문제에서 했던 것처럼 한 포인터(slow)는 한 번에 한칸씩만 이동하고, 다..

문제 주어진 두 연결 리스트가 교차하고 있는지 확인해서 교차점이 있으면 해당 교차점의 노드를, 없으면 null을 반환하는 문제이다. 살펴보기 두 가지 방법을 이용해서 풀어보았다. 첫 번째 방법은 두 연결 리스트의 현재 노드부터 교차점까지의 거리를 일치시킨 후, 두 연결 리스트를 동시에 순회하면서 노드의 주소값을 비교하는 방법이다. 예를 들어 주어진 두 연결리스트가 아래와 같은 모습을 띈다면 빨간색 네모를 친 2칸만큼 파랑색 연결 리스트가 더 길다. 만약 두 연결 리스트를 동시에 순회할 경우, 노랑색 연결 리스트가 파랑색 연결 리스트보다 2칸 앞서가게 돼서, 두 노드의 교차점을 찾을 수 없다.. 그래서 두 연결 리스트의 길이 차이인 2만큼 파랑색 연결 리스트를 이동한 후 두 연결 리스트를 동시에 순회하면 ..

문제 주어진 연결 리스트가 순환하고 있는지 확인하는 문제이다. 살펴보기 문제를 푸는 방법은 여러 가지가 있다고 하는데 2개의 포인터를 이용하는 방법(투 포인터 알고리즘)이 가장 자주 쓰이는 것 같고, 컬렉션을 이용하는 방법도 많이 쓰이는 것 같다. 먼저 포인터를 이용하는 방법은 head와 연결된 두 노드를 활용한다. 한 노드는 한 칸씩(.next), 다른 노드는 한번에 두 칸씩(.next.next) 이동시킨다. 리스트가 순환하고 있다면, 두 노드가 순회하다가 만나게 된다! 그러나 순환하고 있지 않다면 null을 만나서 순회가 끝나게 된다. 컬렉션을 이용하는 방법은 간단하다. 컬렉션을 하나 만들고, 컬렉션에 방문한 노드의 주소값을 저장해둔다. 그리고 노드를 방문할 때마다 컬렉션에 해당 노드의 주소값과 동일..

문제 살펴보기 일명 Happy Number를 찾는 문제이다. Happy Number를 찾는 방법은 다음과 같다. 1. 주어진 숫자에서 모든 자릿수의 제곱의 합을 구한다. 2. 제곱의 합이 1이 나올때까지 반복 수행한다. 3. 제곱의 합이 1이 나오면 Happy Number이다. 4. 제곱의 1이 나오지 않으면 1번이 무한히 반복된다. 예시) 주어진 숫자가 23인 경우 2^2 + 3^2 = 13 1^2 + 3^2 = 10 1^2 + 0^2 = 1 23은 Happy Number 생각해보기 숫자가 Happy Number가 아니라면, Happy Number를 찾는 연산이 무한히 반복된다고 한다. 즉, 연산 과정에서 특정한 숫자가 반복해서 얻어지게 된다. 예를 들어, 주어진 숫자가 4인 경우 4^2 = 16 1^..