benjykim

1.8 0 행렬 M x N 행렬의 한 원소가 0일 경우, 해당 원소가 속한 행과 열의 모든 원소를 0으로 설정하는 알고리즘을 작성하라. M x N 행렬에 한 원소만이 0일 경우로 해석하여 푼 경우 - 공간복잡도 O(MN) #include #include #define M 3 #define N 4 using namespace std; pair get_pos(int array[][N]) { for (int i = 0; i < M; i++) for (int j = 0; j < N; j++) if (array[i][j] == 0) return make_pair(i, j); } void set_zero(int array[][N], pair pos) { // horizontal for (int i = 0; i < ..

1.5 하나 빼기 문자열을 편집하는 방법에는 세 가지 종류가 있다. 문자 삽입, 문자 삭제, 문자 교체, 문자열 두 개가 주어졌을 때, 문자열을 같게 만들기 위한 편집 횟수가 1회 이내인지 확인하는 함수를 작성하라. unordered_set 을 사용하는 경우 - O(n) #include #include #include using namespace std; bool solution(string str1, string str2) { unordered_set s; size_t len1 = str1.length(); size_t len2 = str2.length(); if (len1 > len2) { for (char &c : str1) s.insert(c); for (char &c : str2) { if (s..

1.4 회문 순열 주어진 문자열이 회문(palindrome)의 순열인지 아닌지 확인하는 함수를 작성하라. 회문이란 앞으로 읽으나 뒤로 읽으나 같은 단어 혹은 구절을 의미하며, 순열이란 문자열을 재배치하는 것을 뜻한다. 회문이 꼭 사전에 등장하는 단어로 제한될 필요는 없다. unordered_map자료구조를 사용하는 경우 - O(n) #include #include #include #include using namespace std; bool solution(string input) { unordered_map umap; size_t len = input.length(); int odd_count = 0; transform(input.begin(), input.end(), input.begin(), tol..

1.3 URL화 문자열에 들어 있는 모든 공백을 '%20'으로 바꿔 주는 메서드를 작성하라. 최종적으로 모든 문자를 다 담을 수 있을 만큼 충분한 공간이 이미 확보되어 있으며 문자열의 최종 길이가 함께 주어진다고 가정해도 된다(자바로 구현한다면 배열 안에서 작업할 수 있도록 문자 배열(character array)을 이용하길 바란다). 예제 입력 : "Mr John Smith", 13 출력 : "Mr%20John%20Smith" + 연산을 사용하는 경우 - O(n) #include using namespace std; void replace_spaces(string str, int len) { string ret = ""; for (int i = 0; i < len; i++) { if (s..

1.2 순열확인 문자열 두 개가 주어졌을 때 이 둘이 서로 순열 관계에 있는지 확인하는 메서드를 작성하라. 두 문자열을 정렬한 뒤 비교하는 경우 - O(nlogn) #include #include #define N 128 using namespace std; int check_permutation(char *str1, char *str2) { sort(str1, str1 + N); sort(str2, str2 + N); for (int i = 0; i < N; i++) { if (str1[i] != str2[i]) return -1; } return 0; } int main() { char str1[N] = "baac"; char str2[N] = "abac"; int ret; if (check_perm..

1.1 중복이 없는가 문자열이 주어졌을 때, 이 문자열에 같은 문자가 중복되어 등장하는지 확인하는 알고리즘을 작성하라. 자료구조를 추가로 사용하지 않고 풀 수 있는 알고리즘 또한 고민하라. set 자료구조를 사용하는 경우 #include #include #include using namespace std; int main() { set s; pair pr; char *str = "combana"; size_t len = strlen(str); for (int i = 0; i < len; i++) { pr = s.insert(str[i]); if (!pr.second) cout

코드는 github에서 SoongsilMilhouse를 검색하시면 됩니다.(https://github.com/SoongsilMilhouse/BaekjoonOnlineJudge) * 큰 틀1) 입력을 받고 '\n'(개행문자)를 null(널문자)로 바꿔준다. (fgets를 쓰면 개행까지 들어가기 때문이다.)2) 문장의 끝 지점을 nullPoint라는 변수에 저장한다. 3) 반복문을 시작하기 전에 배열의 첫 문자가 공백인지 공백이 아닌지 검사한다.4) 반복문으로 원소 하나하나 접근하며 공백 개수(spaceCount)를 센다. * 세부사항('_'(언더바)문자는 공백입니다.)1) 첫문자가 공백이 아닌 경우 1-1) 'a' 입력한 경우 (배열엔 'a','\0'으로 저장되어 있다.)spaceCount = 0; 1-2..