인프런 커뮤니티 질문&답변
작성한 질문수
공주 구하기 문제 풀이 시간 복잡도 질문
작성
·
148
0
안녕하세요
제가 푼 코드와 강의의 풀이가 차이가 있어서 질문 드립니다.
저는 아래와 같이 문제를 풀어 봤는데요.
강의와 제 풀이의 시간 복잡도가 어떻게 되는건지 궁금합니다.
제 풀이는 while문이 하나 있으니 O(n)으로 표시하면 되는 것일까요?
강의 풀이는 while문 안에 for문이 있는데 그럼 O(n^2) 인건가요? 아니면 K를 상수로 보고 O(n) 이라고 생각하면 되는 걸까요..
public int solution(int n, int k) {
int answer = 0;
Queue<Integer> queue = new LinkedList<>();
for (int i = 1; i <= n; i++) {
queue.add(i);
}
int cnt = 1;
while (queue.size() > 0) {
if (cnt == k) {
answer = queue.poll();
cnt = 1;
} else {
queue.add(queue.poll());
cnt++;
}
}
return answer;
}
두 코드 중 어떤 것이 더 효율적인 코드인지 궁금합니다.
실행 시간을 비교해서 더 짧게 나오는 것이 효율적인 코드라고 봐도 되는 걸까요?
답변 1
0
안녕하세요, 인프런 AI 인턴입니다.
현지원님의 질문에 대해 답변 드리겠습니다.
O(n)과 O(n^2)은 서로 다른 시간 복잡도를 나타냅니다. 제시해주신 코드는 Queue를 사용하여 각각의 요소를 한 번씩만 따져보게 하므로 O(n)에 해당합니다.
반복문 안에 또 다른 반복문이 있어 복잡해 보이지만, k가 상수라면 내부 반복문은 k번 반복하므로 결국 O(n)이 됩니다.
두 코드의 효율성 비교는 시간 복잡도 이외에도 다른 요소를 고려해야 합니다. 실행 시간은 컴퓨터의 상태나 입력 값의 크기에 따라 달라질 수 있으므로, 시간 복잡도 분석이나 공간 복잡도 등을 종합적으로 고려하여 판단하는 것이 좋습니다.
질문에 대한 답변이 되었길 바랍니다. 좀 더 자세한 답변을 원하시면 인프런 FAQ를 참조하시거나 강의 페이지 내에 있는 ‘수강 전 문의 게시판’을 통해 강사님께 질문해 보시는 것도 추천드립니다.
감사합니다.