1231. [S/W 문제해결 기본] 9일차 - 중위순회

하루입니다.

 

문제 링크

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

 

 

---

 

 

오늘 푼 문제는 나에게 큰 의미가 있다.

 

왜냐?

 

이론만 아는 게 아니라 실제로 사용해봐야 지식이 이어진다는 걸 다시 한 번 체감했기 때문이다. 자료구조 공부한 게 헛되지 않다는 걸 느끼기도 했고. 그래봤자 9일이긴 하지만 ^ㅁ^... 

 

오늘 푼 문제는 Swea의 1231번 문제이다 . 값을 입력받아서 이진 트리를 구현하고, 중위 순회한 결과를 출력하는 문제이다. 처음엔 트리를 대체 어떻게 구현해야 하는지, 값을 어떻게 입력받고 담을지도 감이 오지 않아서 한참 고민하다 구글링을 했다. 원래는 트리와 포인터(현재 노드를 가리킴)를 구현해야 한다. 하지만 완전 이진 트리가 주어지고, 이는 1차원 배열을 사용해서 효율적으로 풀 수 있다는 말에 그렇게 접근하기로 했다.

 

 

내가 생각한 프로세스

이 문제를 풀 때의 포인트는 1. 어떻게 주어진 값을 배열에 담을 것이지 2. 배열의 값을 어떻게 중위순회하며 꺼낼 것인지라고 생각한다.

 

 1. BufferedReader를 사용하여 한 줄을 통째로 읽은 뒤, StringTokenizer를 사용해 띄어쓰기 기준으로 앞의 두 원소(idx, 값)만 사용했다. 

 2. 재귀함수를 사용할 것이다. 이를 위해 static 변수를 선언하였다. 완전 이진 트리의 특징은 왼쪽 원소는 현재원소*2, 오른쪽 원소는 현재원소*2+1의 index(?)를 가진다는 것이다. 현재 원소의 왼쪽노드계산값이 전체 원소값보다 작거나 같은 경우 / 오른쪽노드계산값이 전체 원소값보다 작거나 같은 경우는 자식노드가 있다는 뜻이므로 재귀함수를 호출하는 식으로 진행할 것이다. 만약 위의 두 경우에 해당하지 않는다면 출력 대상이므로 출력할 것이다.

 

아래는 설명 겸 수도코드이다.

 

// BufferedReader와 StringTokenizer를 사용할 것이므로 미리 생성한다.

// 테스트 케이스가 10개이므로, 총 10번 반복한다. 

//

// inOrder(idx)라는 이름으로 재귀함수를 선언한다. (중위순회가 inOrder라고 함!)
//         만약 idx에 2를 곱한 값이 n와 같거나 작다면 왼쪽자식이 있다는 뜻임. inOrder에 2*idx를 넣어주자.

//         배열명[idx]를 출력한다.
//         만약 idx에 2를 곱하고 1을 더한 값이 n과 같거나 작다면 오른쪽 자식이 있다는 뜻임. inOrder에 2*idx+1을 넣어주자.

//
// 맨 위에 주어지는 수는 요소의 갯수이다. br.readLine()을 사용해 받는다. (int n)
// 1차원 배열을 사용하여 문제를 풀 것이고, 1부터 요소가 주어지므로 [요소 갯수 + 1] 의 int 배열을 만들 것이다.
// 배열의 인덱스마다 해당하는 요소를 넣어야 하기에 요소 갯수(n)만큼 반복문을 사용한다.
//         한 줄을 통째로 받고, stringTokenizer를 사용해서 띄어쓰기 기준으로 자른다.
//         배열의 인덱스(nextToken) = 요소값(nextToken)이다. 뒤에 오는 건 무시한다.
//         값이 들어간 배열 완성!
// 반복문이 끝났다면 inOrder(1)을 실행한다.

 

코드 보기

https://github.com/mjkim856/Algorithm/blob/main/SWEA/D4/1231.%E2%80%85%EF%BC%BBS%EF%BC%8FW%E2%80%85%EB%AC%B8%EC%A0%9C%ED%95%B4%EA%B2%B0%E2%80%85%EA%B8%B0%EB%B3%B8%EF%BC%BD%E2%80%859%EC%9D%BC%EC%B0%A8%E2%80%85%EF%BC%8D%E2%80%85%EC%A4%91%EC%9C%84%EC%88%9C%ED%9A%8C/%EF%BC%BBS%EF%BC%8FW%E2%80%85%EB%AC%B8%EC%A0%9C%ED%95%B4%EA%B2%B0%E2%80%85%EA%B8%B0%EB%B3%B8%EF%BC%BD%E2%80%859%EC%9D%BC%EC%B0%A8%E2%80%85%EF%BC%8D%E2%80%85%EC%A4%91%EC%9C%84%EC%88%9C%ED%9A%8C.java

 

---

 

느낀 점

재귀함수 돌아가는 거 100%는 이해 못함. 당연함 정의해서 사용해 본 게 처음이니까 ... 그럼에도 불구하고 이래서 스택을 배웠고, 이래서 array를 배웠고, 지금 문제에서 필요한 건 뭐니까 이 자료구조를 사용해야겠다! 라는 생각이 아주 조금씩은 들고 있다는 점이다. 

 

추가로 이번 문제는 무려 D4 (...) 레벨이었다. 혼자였다면 풀 생각도 안 했겠지만, 함께 스터디 하는 분이 같이 풀어봐요! 라고 하셔서 도전할 수 있었다. 게다가 풀었음 어쨌든 푼 거임. 앞으로도 스터디 열심히 하면서 여기저기 부딪혀 봐야겠다.

 

...

 

파이텡!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!