Q1.스택을 표현한 메서드이다. 시간복잡도를 모두 찾아라!

class Stack {

  private ArrayList<Integer> listStack = new ArrayList<Integer>();

  public void push(Integer data) {
    listStack.add(data);
  }

  public Integer pop() {
    return listStack.remove(listStack.size() - 1);
  }

  public boolean contains(Integer data) {
    return listStack.contains(data);
  }
}

Stack stack = new Stack();

우선 이 문제에 대한 답은 이렇다.

stack에서 찾을 수 있는 시간 복잡도는

• 스택에 새로운 요소를 넣거나 뺄 때 발생하는 O(1)이 있습니다. (넣을 때와 뺄 때 가장 마지막 요소를 넣거나 뺍니다.)
• 스택을 탐색하는 O(n)이 있습니다. (스택 한 번 순회)

---

나의 질문내용❓

💡 내가 이해되지 않던 부분은 이 코드였다.
이것은 내가 한 질문의 내용이다.

public boolean contains(Integer data) {
    return listStack.contains(data);
  }

스택을 표현한 코드중 일부인데 이 코드를 시간복잡도로 표기하면 O(n)이라고 하는데 왜 O(n)이 나올 수 있는지 이해가 잘 안갑니다!

integer 타입의 데이터를 인자로 받아서 boolean타입으로 리턴을 해주는 메서드이고 listStack인스턴스로 contains(data); 메서드를 재귀하는 메서드로 이해를 했는데 이렇게하면 무한루프가 돌지 않나요 ? 참/거짓으로 리턴이 될 수 있는지도 잘 모르겠어요!

---

질문해결💡

class Stack {

  private ArrayList<Integer> listStack = new ArrayList<Integer>();

  public void push(Integer data) {
    listStack.add(data);
  }

  public Integer pop() {
    return listStack.remove(listStack.size() - 1);
  }

  public boolean contains(Integer data) {
    return listStack.contains(data);
  }
}

Stack stack = new Stack();

이 코드의 구조를 먼저 보면

• Stack클래스 안에
  • listStack이 ArrayList타입으로 인스턴스화 되어 있다.
  • push(){}
  • pop() {}
  • contains(Integer data){
    return listStack.contains(data);
• Stack클래스 밖에
  • Stack타입의 stack이 생성되어 있다.

내가 이해하지 못한 이유는 contains(Integer data){}와 listStack.contains(data);의 메서드명이 같아서 당연히 재귀함수일거라고 생각했기 때문이다.(재귀를 배우고 있었음)

contains(Integer data){...} 는 Stack클래스의 메서드이고 listStack.contains(data); 는 ArrayList클래스의 contains메서드였다. 따라서 재귀함수가 아니다.

class Stack {

private ArrayList<Integer> listStack = new ArrayList<Integer>();
...(생략)

	// 문제의 contains메서드...ㅜㅜ

		public boolean contains(Integer data) { 
	    //Integer 타입의 data를 인자로 받아 아래의 코드를 실행한 후 boolean타입으로 반환해라

	  	return listStack.contains(data);
		// ArrayList클래스 내 contains()메소드를 실행시킨다.
		// listStack에 data가 있으면 true, 없으면 false;
     	// (contains()는 ListArray가 선언된 객체의 equals()로 확인한다.) 
	}
}

Stack stack = new Stack();

오늘의 교훈 : 코드를 해석할 땐 구조부터 파악하자! 메서드 명이 같다고 다 오버로드,오버라이드, 재귀가 아니다! 다음부턴 좀 더 꼼꼼하게 코드를 봐야겠다. 이 코드 하나로 피같은 몇시간을 혼자 끙끙댔다.