강의
https://www.youtube.com/watch?v=mBeyFsHqzHg&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=4
문제
https://github.com/encrypted-def/basic-algo-lecture/blob/master/workbook/0x03.md
10808 알파벳 개수
알파벳은 연속되어 있음. 배열에 일대일 대응 가능.
알파벳의 빈도수를 저장할 freq['z' - 'a' + 1] 배열을 만들어 사용
2577 숫자의 개수
숫자도 연속되어 있음. 배열에 일대일 대응 가능.
1475 방 번호
자릿수에 대응하는 배열을 만들어줌.
대신 6과 9는 둘이 같이 사용할 수 있으니 / 2를 해줘야 함
이 때 나머지가 있는 경우 ++을 해줄 수도 있지만, 그냥 (x + 1) / 2 를 하면 알아서 나머지가 있는 경우는 1만큼 더해지고 아닌 경우는 그냥 몫을 사용할 수 있음
3273 두 수의 합
어려웠다..ㅠㅠ
원래 내 방식은
for(int i = 0; i < n - 1; ++i) {
for (int j = 1; j < n; ++j) {
}
}로 O(N^2)이 될 수 밖에 없는 구조였음.
하지만 수가 나타났는지 아닌지를 배열로 관리하게 되면
if ((x - arr[i]) && occur[x - arr[i]])이렇게 O(N)으로 확인할 수 있게 됨.
연속된 수는 배열로 관리해서 시간을 줄일 수 있다는 사실을 명심하기!
10807 개수 세기
이것도 배열로 관리하면 빠름
13300 방 배정
처음 내가 한 코드에선 M[6], W[6] 으로 남 여 배열을 따로 만들었는데
남자 여자 배열을 이차원 배열로 한 번에 관리할 수 있었음. student[2][6];
이렇게 하면 입력받은 성별을 가지고 배열에 바로 저장하면 됨 ++student[s][y];
11328 Strfy
이것도 알파벳을 배열로 관리해서 처음 str에 나온 알파벳은 freq 배열에서 ++해주고, 두 번째 str에 나온 알파벳은 freq 배열에서 --해준 다음
freq 배열을 돌며 0이 아닌 값이 있을 때 false를 반환하게 해주는 식으로 구현.
1919 애너그램 만들기
이것도 freq 배열로 문자열 두 개 ++, -- 해주고
freq 배열 돌면서 절대값을 res에 더해주는 식으로 구현
배운 점
배열 할당을 꼭 알맞은 사이즈로 할 필요는 없다. (넘치게 선언해두고 사용해도 됨)
시간초과 문제가 생긴다면 공간복잡도를 늘려서 시간을 줄일 수 있는 방법이 있나 생각해보기
연속되는 특징을 가진 값들은 배열을 사용하도록 연습!
어떻게 하면 일대일 대응을 시킬 수 있을지 잘 생각해보기
