-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
Map 을 사용하신 이유가 궁금합니다.
20.03.12 22:59 작성 조회수 255
6
안녕하세요. 강의 잘 보고 있습니다.
Map 을 사용하신 이유가 혹시 이중 for 문을 피하기 위해서 인가요?
이중 for 문을 사용하면 문제가 쉽게 풀리는데 Map 을 사용하니까 난이도가 올라가네요...
이런 식의 사고를 할 수 있으려면 어떤 연습이 필요할까요?
답변을 작성해보세요.
8
푸샵맨 코딩스터디
지식공유자2020.03.12
아 그리고 twoSum문제 유형은 너무 많이 응용되고 있습니다.
twoSum은, Array+Map(고유키를 저장 했다가 Array를 for문 돌려서 나오면 후려쳐서 값 얻기) 대표문제죠 ^^;
이런 문제 엄청 많이 나오죠 , 주로 온라인 코딩테스트 기본문제로다가
6
푸샵맨 코딩스터디
지식공유자2020.03.12
안녕하세요~~
질문 감사합니다.
1. 질문 주신 내용 보면
"이중 for 문을 사용하면 문제가 쉽게 풀리는데 Map 을 사용하니까 굉장히 어려워지더라고요."
=>네 이중for문을 돌리면 쉽죠, 답은 그렇게 구할 수도 있습니다. 하지만 time Complexity(n의제곱)이 되죠
문제처럼 갯수가 4개면 상관없지만 극단적으로 100만개~1000만개를 돌린다고하면 시스템에 무리가 가죠
그래서 데이타에 한번 접근해서 구하기 위해서 Map을 이용한겁니다.
2. " 이런 식의 사고를 할 수 있으려면 어떤 연습이 필요할까요? "
아래 유형을 빨리 캐치해야죠. 그리고 수업중에 말한 문제 적용에 단계가 있습니다.
3단계(한국어로 문제완전이해+ 데이타 그릇만들기+ for문돌리기+ 알고리즘적용하기) 를 적용해야하면서..
1. Array 문제라고 판단되면
Array(sort이용하는거), Array+Map(키이용), Array+Map+Set(중복없이 고유키), Map+Map(고유키가 양쪽포진)
-> 거의 이걸로 다 해결됩니다.
2. Stack & Queue 문제판단
3. dfs/bfs 판단해서 파고들기
4. 백트랭킹, dp문제
5. 그래프, tree. 우선순위, 그리디, 최단거리, 등등
쓰다보니 유형이 많네요ㅜㅜ..하지만 3단계를 잘 적용하면 ..다 풀수 있다고 확신합니다.
초반엔 막막하지만, 유사한 문제가 보이기 시작하면서 ..점점 고수가 되겠죠??
화이팅하세요~~
답변 2