Don't die there

문제 한 단어가 다른 단어에 포함된 문자열인지 판별하는 isSubstring이라는 메서드가 있다고 하자. s1과 s2의 두 문자열이 주어졌을 때, s2가 s1을 회전시킨 결과인지 판별하는 코드를 isSubstring을 한 번만 호출하도록 하여 작성하라(가령 'waterbottle'은 'erbottlewat'을 회전시켜 얻을 수 있는 문자열이다). 풀이 두 문자열에서 s2가 s1을 회전시킨 경우인지를 확인하려면 s1 두 개를 이어붙이고 s2가 이어붙인 s1의 부분 문자열인지를 확인하면 됩니다. 이 문제는 알고스팟의 Jaeha's Safe와 비슷한 문제로 한 문자열을 이어붙이고 다른 문자열이 부분 문자열인지를 kmp 알고리즘으로 확인하면 됩니다. 구현 코드

문제 M x N 행렬을 순회하면서 0인 원소를 발견하면, 해당 원소가 속한 행과 열의 모든 원소를 0으로 설정하는 알고리즘을 작성하라. 풀이 1. 비트 벡터 사용 배열을 순회하면서 0이 들어간 행과 열을 각각 정수형 변수에 비트로 위치를 기록해두고 이를 바탕으로 배열의 값을 바꿔주면 됩니다. 2. 배열의 첫 번째 행과 첫 번째 열을 기록용 배열로 사용 첫 번째 행과 첫 번째 열에 0이 포함되어있는지를 기록하는 boolean형 변수 두 개에 각각 기록해두고 첫 번째 행과 열을 제외한 나머지 위치를 순회하면서 0의 위치를 첫 번째 행과 첫 번째 열에 기록해둡니다. 기록해둔 첫 번째 행과 열을 참고하여 나머지 배열의 0이 들어가는 위치를 모두 바꿔주고 앞에서 기록해둔 boolean형 변수를 참고하여 첫 번째 ..

문제 이미지를 표현하는 N x N 행렬이 있다. 이미지의 각 픽셀은 4바이트로 표현된다. 이때 이미지를 90도 회전시키는 메서드를 작성하라. 부가적인 행렬을 사용하지 않고서도 할 수 있겠는가? 풀이 배열의 가장 바깥쪽 레이어 부터 값을 90도 이동시키고 안쪽 레이어까지 반복해주면 됩니다. 구현 코드

문제 같은 문자가 연속으로 반복될 경우, 그 횟수를 사용해 문자열을 압축하는 메서드를 구현하라. 가령 압축해야 할 문자열이 aabccccccccaaa라면 a2b1c8a3과 같이 압축되어야 한다. 압축 결과로 만들어지는 문자열이 원래 문자열보다 짧아지지 않는 경우, 이 메서드는 원래 문자열을 그대로 반환해야 한다. 풀이 문자열의 앞에서부터 같은 문자의 개수를 세고 다른 문자가 나오면 문자와 문자의 개수를 압축형태로 만들어나가면 됩니다. 이때 자바에서는 문자열을 + 연산으로 합치는 경우 새로운 문자열 객체를 생성하고 붙이는 작업을 수행할 때 O(n²)이 소요되어 문자배열을 사용해야 시간복잡도 O(n)으로 줄일 수 있습니다. c++에서는 + 연산에서 새로운 문자열 객체를 생성하지 않는다고 하고 명확하진 않지만..

문제 주어진 문자열 내의 모든 공백을 '%20'으로 바꾸는 메서드를 작성하라. 풀이 문자열을 사용하면 쉽게 구현가능 하지만 문자 배열만 사용한다는 제한이 있는 경우에는 먼저 문자열의 모든 공백을 카운트하여 %20 세 글자가 전부 들어갈 수 있는 크기만큼 배열의 크기를 새로 할당해주고 문자열의 뒤에서부터 공백인 자리에 %20을 채워나가면 됩니다. 구현 코드

문제 문자열 두 개를 입력으로 받아 그중 하나가 다른 하나의 순열인지 판별하는 메서드를 작성하라 풀이 두 문자열의 모든 문자 개수가 같으면 순열이 됩니다. 먼저 두 문자열의 길이가 다르면 순열이 될 수 없으므로 길이가 같은지를 확인합니다. 이후에는 두 문자열을 정렬하거나 문자열에 포함된 문자의 출현 횟수가 같은지 확인해서 순열인지 확인해줍니다. 구현 코드

문제 널 문자로 끝나는 문자열을 뒤집는 reverse(char* str) 함수를 C나 C++로 구현하라. 풀이 문자열의 가장 왼쪽과 오른쪽을 서로 바꾸고 한칸씩 안쪽으로 이동하여 문자열의 중간까지 반복시키면 됩니다. 문제에서는 char 포인터를 매개변수로 받아야하므로 char 배열의 시작위치를 매개변수로 넘겨주어 left 인덱스로 사용하고 마지막 문자의 위치의 포인터를 right 인덱스로 사용하여 left와 right의 값을 서로 바꿔주고 left는 1을 증가시키고 right는 1을 감소시키며 반복해나가면 됩니다. 구현 코드

문제 문자열에 포함된 문자들이 전부 유일한지를 검사하는 알고리즘을 구현하라. 다른 자료구조를 사용할 수 없는 상황이라면 어떻게 하겠는가? 풀이 배열을 제외한 모든 다른 자료구조를 사용하지 않고 문자들이 전부 유일한지를 검사해야합니다. 우선 스탠다드 아스키코드를 기준으로 문자는 총 128가지가 있기 때문에 문자열의 길이가 128이 넘으면 중복이 존재하는 경우이므로 이 경우를 먼저 확인합니다. 이후에는 총 4가지 방법으로 검사할 수 있습니다. 1. 128크기의 boolean형 배열에 각 문자가 존재하는지를 표시하고 동일한 문자가 다시 접근하는지 확인 시간 복잡도 : O(n) 공간 복잡도 : O(1) 2. 문자가 알파벳 소문자로만 이루어졌다는 가정하에 26자리를 정수형 변수에 비트로 표시하고 동일한 문자가 다..