• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

Map 을 사용하신 이유가 궁금합니다.

20.03.12 22:59 작성 조회수 255

6

안녕하세요. 강의 잘 보고 있습니다.

Map 을 사용하신 이유가 혹시 이중 for 문을 피하기 위해서 인가요?

이중 for 문을 사용하면 문제가 쉽게 풀리는데 Map 을 사용하니까 난이도가 올라가네요...

이런 식의 사고를 할 수 있으려면 어떤 연습이 필요할까요? 

답변 2

·

답변을 작성해보세요.

8

아 그리고 twoSum문제 유형은 너무 많이 응용되고 있습니다. 

twoSum은,  Array+Map(고유키를 저장 했다가 Array를 for문 돌려서 나오면 후려쳐서 값 얻기) 대표문제죠 ^^;

이런 문제 엄청 많이 나오죠 , 주로 온라인 코딩테스트 기본문제로다가

6

안녕하세요~~

질문 감사합니다.

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단계를 잘 적용하면 ..다 풀수 있다고 확신합니다.

초반엔 막막하지만, 유사한 문제가 보이기 시작하면서 ..점점 고수가 되겠죠??

화이팅하세요~~