2-T 문제에 관한 질문
4
작성한 질문수 5
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
안녕하세요! 2-T문제 풀이에 관한 질문입니다.
제가 풀었을 때는 문제를 다른 방식으로 풀었어서요 .. 현재 채점사이트에서의 케이스들의 시간복잡도에 문제가 없어서 통과된 것인지, 크기가 100만처럼 엣지케이스로 가게 된다면 문제가 생기는 코드인지 궁금해서 질문 남깁니다.
현재 제 코드는
이러합니다.
시간복잡도를 줄이기 위해 전체를 모두 돌지 않고, 이전에 저장된 오큰수의 index를 보며 타고 타고 들어가는 방식으로 탐색을 했습니다.
스택은 생각도 못한지라.. 강의를 듣고 깨닫게 됐습니다..ㅜ_ㅜ
답변 1
0
안녕하세요, 인프런 AI 인턴입니다. pshpark12345님.
질문하신 부분에 대해 살펴보겠습니다. 현재 설명해 주신 코드에 대해 언급된 이미지 정보를 토대로 일반적인 ‘오큰수’ 문제와 비슷한 맥락을 가진 것으로 보입니다. 이 문제에 대해 자주 사용되는 접근 방식 중 하나는 스택을 사용하여 O(N) 시간복잡도로 해결하는 방법입니다. 스택을 사용하면 각 원소를 한 번만 처리하여 더욱 효율적으로 해결할 수 있죠.
코드 분석
말씀하신 대로 ret 벡터를 업데이트하는 방법으로 특정 비교를 통해 시간을 줄였다면, 그 방법이 특정 경우에서는 O(N^2)이 될 수 있습니다. 특히 배열의 크기가 매우 커진 경우, 즉 N = 100만에 도달할 때 문제가 생길 가능성이 높습니다.
기존에 작성한 방식이 이전 값의 인덱스를 추적하여 최적화를 시도했다면 이는 특정 케이스에서는 확실히 도움이 될 수 있으나, 문제 전체적으로는 최적화에 취약할 수 있습니다.
추천 해결 방법
스택 사용: 직접적으로 각 값에 대해 스택을 사용하여 오큰수를 찾는 방법을 사용하면 O(N)으로 안정된 시간 복잡도를 유지할 수 있습니다.
테스트 및 확인: 특별히 엣지 케이스(예: 배열의 값들이 모두 같은 경우 등)를 통해 예상한 시간 복잡도와 실제 동작 성능을 비교하여 코드를 개선할 수 있습니다.
참고자료: 다음 링크는 오큰수 문제를 스택으로 해결하는 방법에 대한 일반적인 설명입니다.
이는 C++ 코딩 테스트에서 시간 복잡도의 중요한 부분을 확실히 이해할 수 있게 도와줄 것입니다. 스택을 사용하여 적절히 문제 해결을 시도해 보시면 좋겠습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
코딩 살구 클럽 접속 및 사용방법 문의
0
23
2
안녕하세요~. 현재 코살코딩클럽 사이트가 접속이 안됩니다~
0
37
2
코딩살구클럽 로그인문제
0
42
3
코딩 살구 클럽 로그인 문제
0
59
2
2-J 채점관련 질문
0
48
3
코딩 살구 클럽 Python 지원 가능 여부
0
63
1
살구클럽 아이디 없음 문제
0
68
1
1-O 코딩살구클럽 채점관련 질문
0
51
2
히든 테스트 케이스가 사라졌습니다
0
47
1
채점서버 혹시 다른 언어 지원도 가능하게 해주실 수 있나요
1
64
2
살구 클럽 채점 관련 문의(테스트 케이스)
0
62
2
1-H 문제 채점하기 오류
0
53
3
코딩살구클럽 2주차 2-L 문제 채점하기 오류
0
49
2
살구 클럽 채점 관련 문의
0
57
2
코딩 살구 클럽 실전 세션
0
55
2
코딩살구클럽 채점 관련 질문
0
47
2
코딩살구클럽 컴파일에러
0
77
2
5-B
0
49
2
4 - A
0
55
2
코딩살구클럽 입장이 안됩니다
0
135
2
4-F 경우의 수 질문입니다.
0
56
2
코딩살구클럽 가입이 안됩니다.
0
124
2
살구 클럽에 대한 질문있습ㄴ디ㅏ
0
79
1
교안 158페이지 문의드립니다
0
54
2