백준/ class3 문제 , 백준 파이썬 1620 , 나는야 포켓몬 마스터 이다솜

백준/ class3 문제 , 백준 파이썬 1620 , 나는야 포켓몬 마스터 이다솜

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>

문제가 좀 더러워보였지만 얻어가는게 있는 문제이다.
여태까지 dict 를 사용해서 푸는 문제들은 인덱스를 처음 부터 끝까지 흝어 O(n) 의 시간복잡도로 풀었는데
이 문제에서는 주어지는 숫자가 너무 많다. 그래서 시간 초과가 발생하는데.

그래서 애초에 값을 입력받을때 dict 에 문자랑 숫자를 한꺼번에 저장을 하는 것이다.
이 후 값들을 한번에 출력하지말고 입력받자마자 바로바로 꺼내서 출력시켜버리면된다.

 

 

 

<문제 출처>

https://www.acmicpc.net/problem/1620

1620번: 나는야 포켓몬 마스터 이다솜

------------------------------------------------------------------------------------------------------------------------------

 

 

 

 

 

 

 

시간 초과가 난 내 코드이다. 딱봐도 불필요한 연산들이 보인다.

 

 

 

 

 

 

 

이 코드가 문제의 핵심이다. 이 코드를 사용하면 불필요하게 리스트를 만들필요가 없다.

 

 

 

 

 

https://gudwns1243.tistory.com/63

[백준][파이썬]1620번: 나는야 포켓몬 마스터 이다솜

 

 

이 블로그님의 풀이를 보고 핵심 아이디어를 얻었다.

 

 

 

 

이 문제를 푸는데 관건은 

 

 

 

 

 

------------------------------------------------------------------------------------------------------------------------------

 

정답