자연수 뒤집기 알고리즘

문제 및 제한조건

이번주 내내 같은 방법을 계속 쓰게 되는  것 같다. 입력 받아서 한 글자씩 배열에 저장하는 거.. 

이 문제도 입력 받은 자연수를 String으로 변환한 다음 한 글자씩 저장부터 한 뒤에, 역순으로 재정렬 하는 방법만 구현하면 될 것 같았다.

sort라던가 다양한 방법이 있겠지만, 함수 호출해서 해결하는 건 너무 간단하다고 생각했다. 내가 직접 알고리즘을 구현하는 연습을 하고 싶어서 이중 반복문 사용해서 비교 후 정렬 시키기로 했다.

첫 반복문을 사용해 한 글자씩 저장했고, 그 다음 있는 이중 반복문이 정렬을 하는 부분이었다.

배열에서 하나의 요소를 두고, 나머지 요소를 순회하며 비교하는 방법을 생각했다. i번째 요소를 나머지 다른 요소들과 차례로 비교하여 작다면 교체하는 식으로 만들었는데, 이상하게 내림차순이 아니라 오름차순으로 정렬 되었다.

왜?????

i번째 값을 두고, 배열을 순회하며 더 큰 값이 있으면 그 값과 교체하도록 만들었는데 왜 작은 게 앞에 오는 거지..?? 혼자 생각만 해서는 틀린 게 없는 것 같아 해결이 안되니 print로 출력을 해보기로 했다.

아. . 반복문 범위의 문제였다.

첫번째 순회에서 큰 수와 작은 수가 잘 바뀌었는데, 두번째 순회에서 다시 처음부터 비교를 하니 앞에서 바꾼 숫자를 다시 바꾸고 넘어가는 것이다.

앞에서 바꾼 건 건드리지 않도록 j의 범위를 0번째부터가 아닌 i 번째 이후부터 출력되도록 바꾸면 해결 될 것이다.

j 인덱스 순회 범위를 i+1 로 하여 앞에서 바꾼 걸 다시 비교하지 않게 하여 제대로 역순으로 출력되게 되었다.

이제 제출만 하면 되는 줄 알았다..

띠용.. 한두번 실패하는 건 그럴 수 있는데 한두번만 성공하다니..? 이런 경우는 또 처음이다.

전부다 실패한 거면 아예 문제를 잘못 이해했구나 하겠는데 한두번 실패는 또 무엇인가..

뭔가 오해한 부분이 있나 문제를 다시 읽어 보았다. 

'자연수 n을 뒤집어 각 자리 숫자를 원소로 가지는 배열 형태로 리턴해주세요.'

내림차순으로 정렬시키라는 뜻이 아니라 말 그대로 뒤집으라는 말이었다. 예시가 12345이고 이걸 [5, 4, 3, 2 ,1]로 만들도록 하길래, 내림차순 정렬로 오해했다. 12045라면  [5, 4, 2, 1, 0]이 아니라, [5, 4, 0, 2, 1]으로 만들으라는 말이었다.

한 글자씩 배열에 저장하는 것까진 동일하게 하고, 역순으로 저장할 새 배열 하나를 만들어 역순으로 저장하도록 만들었다.

for i in arr {
	arr2.insert(i, at:0)
}

처음엔 위와 같이 작성해서 arr2 배열의 첫번째 요소에 arr 배열의 값을 계속 추가하도록 만들어 역순으로 정렬 되도록 했는데, arr.reversed() 라는 역순 반환 함수가 있었다.

함수를 최대한 쓰지 않고 구현한다고 했지만 따지고 보면 insert도 함수이기도 하고, reversed는 처음 보는 함수라 한 번 써보기로 한 것이다..

이젠 됐겠지 했는데 역시나.. 한 번의 테스트에서 또 실패하였다. 이번엔 시간초과다.

다른 테스트들은 0.07ms ~ 0.11ms에 끝나는데 왜 또 한번은 시간초과가 되는 걸까..

 

제한 사항에 입력 n은 10,000,000,000 이하의 자연수라고 했으니 xcode에서 테스트로 10,000,000,000을 넣고 얼마나 걸리나 확인해봤다.

약 0.0112초 정도로, ms로 계산하면 11.2ms나 걸린다. 확실히 오래 걸리긴 한다. 그래도 혹시 몰라서 변수명만 arr, arr2 이던걸 array1, array2로 바꿔서 다시 테스트 해봤는데

통과 되었다..

참,, 제출 할때마다 겪는 것 같은데 알고리즘을 더 신경쓰고, 나은 방법이 있나 생각해보게 돼서 좋다고 해야할지.. 아무튼 더 나은 방법이 있을 것 같아서 다른 방법을 테스트 해보기로 했다.

다른 방법 생각해보기

이번주 내내 문자열 String과 정수형 Int를 서로 형변환 해대고, 배열에 저장하고 하는 과정을 하다보니 새로 알게 된 것이 있었다.

String이 컬렉션 프로토콜을 따른다는 것이다. 그래서 배열이나 Set과 같이 .count 라든가, .isEmpty, .contains 같은 함수들도 쓸 수도 있고, 배열에서 한 글자씩 저장할 때 for char in 문자열 {} 같은 형식으로도 쓸 수 있는 것이었다.

그렇다면 .reversed()도 가능하지 않을까.

반복문을 두 개를 만들필요 없이 처음에 한 글자씩 저장할 때, 애초에 역순으로 저장하면 되는 거 아니었을까.

소요 시간이 0.011초 걸리던게 0.009초로 정도로 유의미 하다고 할 정도로 큰 차이로 줄진 않았다.

그래도 한 글자씩 저장할 때 reversed()를 써서 애초에 역순으로 저장하니 반복문이 하나로 줄었고 배열도 두 개이던게 하나로 줄어 코드가 훨씬 간결해졌다.

---

느낀점

문자열이 생각보다 많은 걸 할 수 있는 데이터 타입이 아닌가 하는 생각이 들었다.

숫자 타입들과 서로 형변환도 되고, 한글자씩 잘라서 character 타입으로 만들거나, character 타입을 이어 붙여 다시 문자열로 만들기도 하고, 배열이나 다른 컬렉션 타입들에 쓰던 함수도 쓸 수 있고..

컬렉션 프로토콜을 따른 다는 것도 흥미롭게 느껴진다. 컬렉션 프로토콜은 무엇인지, 왜 문자열은 그걸 따르고 있고, 그걸 따름으로써 무엇을 할 수 있는지도 한 번 찾아보면 재밌을 것 같다.