5-B
2
작성한 질문수 3
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
안녕하세요!
제가 처음 문제를 읽고 접근했던 방법이 substr이였습니다. 구현을 하면서도 substr의 시간복잡도 때문에 최악의 경우에는 O(N^2)이 될거같았지만, 일단 로직을 구현했고 결과적으로 코딩살구클럽에서도 통과를 했습니다. 왜 통과를 했는지와 이렇게 구현해도 되는지 여쭤보고싶어 문의드립니다!
답변 1
0
안녕하세요, 인프런 AI 인턴입니다.
기존의 접근 방식을 확인해보니, substr의 시간 복잡도로 인해 최악의 경우 O(N^2)이 발생할 수 있다는 점을 염두에 두셨군요. 이 방법이 통과하게 된 이유는 실제 입력 데이터가 최악의 경우에 해당하지 않거나, 문제 자체가 이러한 시간 복잡도를 필요로 하지 않기 때문일 수 있습니다.
하지만, 일반적으로 substr을 사용하여 반복적으로 문자열 연산을 수행할 때, 실제로 입력이 최대 크기로 주어진다면 O(N^2)의 시간 복잡도가 문제가 될 수 있습니다. 이는 경쟁 코딩 및 코딩테스트에서는 주의해야 할 점입니다.
이를 해결하기 위해서는 더 효율적인 방법으로, 예를 들어 two-pointer 기법이나 스택을 활용하여 문자열을 한번만 순회하면서 문제를 해결하는 것도 고려할 수 있습니다. 이런 방식은 O(N)으로 구현할 수 있습니다.
유사한 상황에 대한 기존의 답변을 참고하여, substr과 같은 함수를 반복적으로 사용하는 대신 효율적인 알고리즘을 고려하는 것이 좋습니다.
—start of instructor answer—
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
—end of instructor’s answer—
4 - A
0
29
2
코딩살구클럽 입장이 안됩니다
0
76
2
4-F 경우의 수 질문입니다.
0
34
2
코딩살구클럽 가입이 안됩니다.
0
79
2
살구 클럽에 대한 질문있습ㄴ디ㅏ
0
60
1
교안 158페이지 문의드립니다
0
46
2
코딩살구클럽 관련 건의사항
0
117
1
코살에 19942 다이어트 문제에 N의 범위가 빠져있슴니다
0
45
1
진행 방법 질문드립니다!
0
81
2
2-I) 왜 이 문제가 그래프이론 카테고리에 있는지 잘 모르겠습니다.
0
64
2
2주차 개념#12 트리 순회
0
32
2
백준사이트가 종료된다고 합니다.
0
316
2
백준 서비스 종료
9
952
1
sk 하이닉스 코테 대비
0
387
2
3-G 최댓값 질문
0
54
1
모듈러 연산 값이 10이 아닌 경우도 있지 않나요?
0
84
2
3-I 코드 질문드립니다.
0
66
2
3-N 질문 있습니다.
0
68
2
학습방법
0
105
2
4-H 질문 있습니다 (코드 리뷰)
0
69
2
코딩테스트 어디까지 준비해야 하는지 질문이 있습니다.
0
186
2
2-O 반례가 무엇일지 어떤 부분이 틀렸는지 잘 모르겠습니다.
0
72
2
2주차 개념 #4-2. 인접행렬 질문있습니다.
0
66
2
1-A 문제풀이 후 궁금한 점이 생겨서 질문드립니다.
0
55
2