1-B counting star

내 풀이(http://boj.kr/a9207910b585417b8bd3018e458a9848) - 맞음

공유 소스 보기

---

1-B counting star

백준 10808 알파벳 개수 문제를 풀어보도록 할게요.

이 문제는 주어진 문자열을 분해를 해서, 이 문자열 안에 있는 문자들을 하나하나 분해 해가지고, 예를 들어서 a가 있으면, a가 두개 들어있어요 라고 출력하는 문제죠.

여러분 자 제발 따라해주세요. Counting star는 map 또는 배열, 무조건 이 두 개가 생각이 나야 됩니다.

일단 Map이라는 자료구조는 뭐죠? Key와 Value 형태로 이루어져 있죠.

나는 a라는 게 몇 개 들어가 있는지를 체크하고 싶죠.

그럼 a라는 key를 놓고, 이 key에 대한 value가 처음엔 0이겠죠?

근데 a가 1개 들어가면 map을 ++ 해서 value가 1이 되고, 2개가 들어가면 ++ 해서 value가 2, 이렇게 나오겠죠?

 

그래서 Counting을 한다고 했을 때는 이렇게 Map을 생각하거나, 그리고 오늘 문제를 풀 때 사용될 Array, 배열을 떠올리셔야 합니다.

배열 같은 경우는 Integer를 기반으로 할 수가 있죠.

보통 Counting을 한다고 했을 때는 cnt라는 이름의 배열을 정의하고,

예를 들어서 첫번째 1이라는 값이 2번 나왔다고 그러면 ++ 해가지고 cnt[1] = 2. 이런식으로 만들 수가 있습니다.

 

다시 정리하자면, Counting star는 Map 또는 배열, 이 두가지를 꼭 생각하셔야 됩니다.

'근데 선생님! Map 또는 배열 중에서 어떨 때는 Map, 어떨 때는 Array를 써야 될까요?' 카운트를 할 때 맵과 배열이 있다라고 했어요.

Map은 보통은 string을 기반으로 할 때는 Map을 쓰세요.

반면, Array는 Integer을 기반으로 하는 게 좋습니다.

그러니까 예를 들어서 "큰돌"이라는 string이 몇 개야? 라는 문제이면 맵을 쓰는 게 좋아요. 근데 예를 들어서 1이 몇 개야?, 2가 몇 개 나왔어? 라고 했을 때는 Integer, Array를 쓰는 게 좋아요.

다만 여기서 반례가 하나 있는데,

Integer라도 문제에서 주어지는 숫자가 10만, 100만, 1000만 이렇게 주어지는 경우가 있어요.

일단 densely가 뭐냐면,

주어지는 요소 자체가 이렇게 꽉 차게 1000만이 들어오지 않고 10만, 100만, 1000만 이렇게 띄엄띄엄 들어오는 경우가 있어요. 이걸 sparse하다 라고 하는데, sparse 하게 들어오는 경우는 배열을 쓰면 안되고 Map을 써야돼요.

일단은 문제마다 좀 다르긴 한데, 보통은 배열 1000만 정도를 정의할 수가 없어요. 정의하게 되면 공간 복잡도가 초과돼서 공간 할당이 잘 안되거든요. 보통 배열은 1000만 정도면 공간 할당이 안돼요.

그래서 이렇게 sparse 하게 1000만, 100만 10만 이렇게 약간 포인트처럼 오는 경우는 얘가 Integer임에도 불구하고 Map을 써야 돼요.

근데 이런 경우 제외하고는 그냥 string 하면 Map, Integer로 하면 Array, 이런 식으로 하는 게 좋습니다.

---

자 그러면 이 문제는 string 이니까 Map을 써야 될까요? 아닙니다.

이 문제는 문자열을 기반으로 해서 문자를 counting 하는 거죠.

예를 들어서 이 문제는 소문자 a부터 z까지 나오니까 {a, b, c, a} 이렇게 쭉 나오면, a, b, c, a 각각의 문자를 기준으로 카운팅을 하는 거죠.

자 이 문자는 ASCII 코드를 기반으로 숫자(Integer)로 나타낼 수가 있습니다. 그래서 이 문제는 배열을 사용해야 되는데, ASCII 코드를 잠깐 보자면,

교안에도 설명을 드렸어요.

개념은 사실 외우실 필요는 없고, 문자와 숫자가 맵핑되어 있다라고 보시면 됩니다.

대문자 A는 65에 맵핑이 되어 있고, 그리고 소문자 a는 97에 맵핑이 되어 있습니다.

 

자, 이 ASCII 코드를 전부 다 외워할까요? 그렇진 않습니다. ASCII 코드는 딱 두 개만 외워주세요.

대문자 A는 65, 소문자 a는 97만 외워두세요.

그리고 알파벳이 26개이니까, + 25를 하면 Z가 나온다는 거를 알아두시면 됩니다.

---

그럼 'a'가 97에 맵핑되어 있다고 했죠. 확인해봅시다.

97이 출력됩니다.

'선생님 그러면 만약에 cnt[a]를 하게 되면 어떻게 될까요?'

그럼 얘는 cnt[97]이 되는 겁니다.

원래는 (int)를 해가지고 형변환을 해줘야 되지만, C++에서는 약간 유연하게 그냥 int로 변환을 해줍니다.

---

자 그럼 정답 코드를 볼게요.

'근데 선생님, 그냥 cnt[a]++ 이렇게 해도되지 않나요?'

여러분 이 문제는 소문자 a부터 소문자 z까지 나오는 문제죠.

그럼 97부터 122까지죠. 근데 만약에 이거를 이제 배열로 나타낸다면,

배열의 크기를 한 123 정도로 정의해야 이 문자 요소들을 나타낼 수가 있겠죠. a[122]가 참조 가능해야되니까요.

근데 생각해보면 97 이전의 값들은 사용되지가 않죠.

그럼 이거를 땡겨서 0에서 25까지로 나타낼 수가 있겠죠.

이런 걸 평행이동, 좌표이동이라고 하는데, 좌표이동을 해서 이렇게 표현할 수가 있습니다. 그러면 배열의 크기는 123이 아니라, 26만으로도 정의를 할 수가 있는 거죠.

그게 아니라, cnt[a]++로 하면, 123으로 정의를 해야 되고 필요 없는 공간이 소모가 되기 때문에 그렇게 좋지는 않은 코드가 되는 겁니다.

 

근데 만약에 문제에서 대문자까지 사용한다고 했으면 거기에 대한 것도 고려를 해야 되지만, 지금 문제에서 소문자 a부터 z까지 라고 했기 때문에 배열 크기를 26으로 정의를 하고, 여기서 좌표 이동을 하면 됩니다.

처음 cnt[a - 'a']++; 하면 1이 됩니다. 전역변수로 선언하게 되면 컴파일러가 무조건 0으로 초기화가 된다고 말씀을 드렸어요.

그런데 지역변수로 하게 되면, 초기화를 따로 안 시키면 쓰레기 값이 들어가기 때문에 코딩 테스트를 할 때는 보통 전역변수로 하는게 좋다 라고도 말씀드렸습니다.

++을 할 수록 자동적으로 counting 되는 로직이 만들어집니다.

 

다시 Counting star는 Map 또는 배열 이렇게 생각을 하시면 됩니다.