당니의 개발자 스토리
1-I 본문
내 풀이(http://boj.kr/31521d5017de4cd492333c0fd0c15a7a) - 틀림
공유 소스 보기
www.acmicpc.net
1-I
1-I 1620 나는야 포켓몬마스터 이다솜 문제를 풀어보도록 할게요.
이 문제는 어떤 문제죠? String을 Int로 바꿔야 되구요. Int를 String으로 바꿔야 하는 문제입니다.
일단 이 문제는 이따가 자료구조를 이용해서 할텐데, String과 Int 두 개가 동시에 오잖아요.
두 개가 동시에 왔을 때 이걸 Int형인지, String인지 분간을 해서 String이 들어오면 Int로, 반대로 Int가 들어오면 String으로 이렇게 해야 되잖아요.
잠깐 교안을 보도록 하죠.
드디어 atoi를 쓸 때가 왔습니다. 문자열을 int로 바꿔 줘야 할 상황이 있어요.
예를 들어서 "amumu" 또는 0 이렇게 온다고 해 봅시다. 그러면 이게 문자열인지 숫자인지를 확인할 때 어떻게 하냐?
바로 이런 식으로 하시면 됩니다. atoi(s.c_str())이렇게 하면, atoi는 문자열을 숫자로 바꿔주는 거거든요.
그래서 1 이라면 그냥 1로 변환이 돼요. 예를 들어서 "amumu" 같은 경우는 숫자가 아니죠. 이렇게 숫자가 아니면 0을 반환합니다. 따라서 atoi를 할 경우에는 0은 체크를 못하겠죠.
그래서 만약에 문제에서 입력에 0이 들어온다면 거기에 대한 처리를 따로 해줘야 합니다.
그런데 이 문제 같은 경우는 1부터 범위가 시작이 되기 때문에 0에 대한 처리를 고민할 필요는 없습니다.
그리고 이 문제는 자료구조를 이용해야하는데,
이런 식으로 담아야할 거 아니예요. 그럼 어떤 자료구조를 통해서 담아야 할까요?
대표적으로 Array나 Map같은 것을 생각할 수 있겠죠. 자료구조를 두 개를 사용해야 되거든요.
그 이유를 설명해 드릴게요.
"amumu"를 찾는 로직이 있다고 합시다. "amumu" 라는 걸 찾아서 얘가 몇 번째라는 포켓몬인지를 찾는 것을 구현한다고 칩시다.
이거를 만약에 배열에다가 담아요.
그럼 배열에는 이런 식으로 여러가지 String을 담았겠죠. 그러면 찾는 게 맨 앞에 있으면 운 좋게 바로 찾겠지만, 이게 중앙에 있을 거란 말이죠.
그러니까 좀 멀리 있을 수도 있죠. 그럼 얘를 만약에 찾는다. 배열에서 만약에 find 함수로 찾는다고 하면,
이거 시간 복잡도가 얼마예요? 배열 같은 경우에는 O(n) 이죠.
저희가 find 라는 함수로 했을 때 시간 복잡도가 O(N) 보다 더 낮은 경우가 뭐가 있죠?
바로 O(logN)인 Map이 있죠.
string에다가 int를 맵핑을 해놔야 되잖아요. 이럴 때는 Map을 사용해야 된다. 왜?
그냥 Array에다가도 담을 수는 있겠죠? 그런데 Array 같은 경우는 시간 복잡도가 O(N)이고, Map은 O(logN)이잖아요. 훨씬 더 작죠? 그래서 string에다가 int를 맵핑 할 때는 Map을 써야합니다.
그럼 Int와 String을 맵핑할 때는 뭐를 써야할까요?
물론 결론적으로 둘 다 되는데, Array 같은 경우는 어느 정도 걸려요? O(1)이죠. 상수시간의 시간 복잡도를 가집니다. 반면, Map은 O(logN)이기 때문에 Array를 쓰는 게 훨씬 더 좋긴 하지만, 사실 logN과 1은 엄청나게 큰 차이는 나지 않기 때문에 Map을 2개 써도 됩니다.
그래서 일단은 String-Int, Int-String 이런 식으로 2개의 자료구조를 사용해야죠.
왜냐하면 이 문제를 푸는데 하나의 자료구조만 가지고는 불가능해요.
그냥 String-Int를 Map에 담았다고 합시다.
그러면 String 이라는 Key를 기반으로 Int를 찾는 것은 쉽지만, 이것을 Key가 아니라 Value를 기반으로 찾는다고 하면 또 O(N)이 걸려요.
그렇기 때문에 자료구조는 두 개가 필요하고, String-Int 같은 경우는 Map, 그리고 Int-String 같은 경우는 Array 또는 Map 두 가지가 된다고 설명을 드렸습니다.
자 코드를 보면서 설명을 하도록 할게요.
자 이런 식으로 2개의 자료구조를 사용했어요. 그리고 인덱스를 기반으로 값을 담습니다. array도 된다는 걸 보여주기 위해 String 배열도 만들었어요.
물론, 출력값을 이렇게 해도 둘 다 시간초과가 나지 않습니다.
그리고 이 문제 같은 경우는 시간초과가 좀 빡세기 때문에, 동기화를 해제하는 것도 주의해 주시고요.
여러분들이 처음에는 문제를 풀 때 하나의 자료구조만 생각했을 수도 있어요. 근데 하나의 자료구조만 쓰면, 만약에 String-Int를 하나의 자료구조에 넣는다고 하면 Value를 기반으로 find를 하기 때문에 O(N)이 걸려서 시간초과가 나와버려요. Key를 기반으로 하면 find를 써도 O(logN)이고, 심지어 find를 안 써도 참조하면 되는 거죠.
그래서 자료구조는 두 개를 사용해야 되고 String-Int 같은 경우는 Map이 더 효율적이다. Int-String 같은 경우는 Array와 Map, 두 가지가 있고 둘 다 쓸 수가 있다는 것을 알아봤습니다.
