📌 날짜 : 2023/10/21 2PM~5PM
코딩테스트를 준비하면서 알고리즘 문제를 해결하는 것에 막 재미를 붙일 시기였다.
올해 ICPC 프로그래밍 대회가 가을에 있다고 하였고, 재미있게 참여할 수 있을 것 같아서 한 번 도전해 보았다.
ICPC대회는 본선이 있기 전에, 예선을 치루고, 예선을 통과한 팀만 본선에 진출할 수 있다.
대학 동기들과 셋이서 as_PA라는 팀으로 출전했다.
예선 때 참고할 수 있는 팀노트를 25장까지 허용한다. 우리는 헷갈리거나, 자주 나올 것 같은 참고할 만한 알고리즘들을 정리해서 갔다. (사실 대회때는 오히려 문제에 집중하느라 팀노트를 거의 안보게 된다.)
셋 다 평소에 백준이나 프로그래머스 등의 프로그래밍 문제 플랫폼으로 열심히 준비해왔었기 때문에, 대회 또한 부담없이 즐기고 오기로 했다.
총 3시간 동안 9문제?10문제?를 해결하는데, 문제는 A부터 알파벳 순이다.
언어는 C, C++, JAVA 중에서 하나를 선택해 해결해야 하고, 우리는 C++을 선택했다.
참고로 시험 문제는 거의 영어로 출제된다.
문제를 풀 때 쓸 수 있는 여백의 종이를 하나씩 나눠 주신다.(우리는 팀 노트 뒷부분이 여백이라, 이것도 사용하긴 했다)
시험이 시작되고, 문제를 하나씩 살펴보았고, 간단히 해결할 수 있는 문제부터 접근했다.
D번 문제
D번을 먼저 풀어보았는데, 주어진 범위내의 펠린드롬 수의 개수를 구하는 문제였다.
1.무식하게 접근
일단은 무식하게 접근했다.
[무식하게 접근한 방법]
주어진 범위내의 모든 숫자를 for문으로 돌아가면서 모두 탐색하도록 하였고, 문자열의 맨 앞과 맨 뒤가 동일한지를 비교해가도록, string을 이용해 숫자를 문자열로 바꿔서 문자열 비교 방법으로 사용했다.
while문을 이용해서 문자열이 1보다 크면, 앞 뒤 쌍이 있는 것이기 때문에 비교하고, 동일하면 그 쌍을 문자열에서 자른다. 이를 while문 안에서 반복하고, 문자열이 다르면 bool 타입 변수를 false로 변경하고(=현재 수는 펠린드롬 수가 아니다) while문을 빠져나오도록 break처리하였다.
만약 while문을 끝까지 잘 돌았다면 bool 타입 변수가 true일 것이기 때문에 펠린드롬 수로 카운트한다.
[결과]
테스트 케이스는 모두 통과한다. 다른 값을 집어 넣어 봤을때에도 문제가 없다.
그런데, 자꾸 결과가 wrong이라고 떴다.
큰 수를 집어 넣어보니 실행 시간이 1초가 넘는다.
결국 제한시간 1초를 고려하지 못해 효율성 면에서 떨어지는 것을 확인하였다.
시간을 줄이기 위해서..
쓸데 없는 계산을 줄여야 했다.
현재 코드는 for과 while문의 2중 루프이기 때문에 n*(문자열 길이)의 복잡도를 가진다. n은 최대 10^10이었기 때문에 엄청난 시간복잡도를 가질 수 밖에 없다.
2. 규칙에 따른 접근
따라서 우리는 n의 범위에 따른 펠린드롬 수의 개수에 대한 규칙을 찾아냈다.
바로 n이 몇자리 수인지에 따른 규칙이다.
len=n의 자리수
1~n자리수의 제일 큰수 중 펠린드롬 수의 개수 = 9*10^(len/2)
이렇게 되면, 굳이 1부터 다 순회하면서 비교할 필요없이, n의 자리수보다 1작은 자리수까지의 펠린드롬 수는 위의 규칙을 통해 미리 카운트 함으로써 계산 횟수를 확실히 줄이고자 하였다.
그리고 나머지 n자리수의 시작~n까지의 수는 앞에서 했던 방식으로 문자열을 비교하도록 하였다.
테스트 케이스를 모두 만족하였으나, 이상하게 예선 때 컴퓨터에서는 다른 결과를 보였다.
아무리 생각해도 맞는 것 같아서 집에와서 돌려보니 내 노트북에서는 정확히 돌아간다.. 무슨 오류가 있는지 모르겠다.
그러나 시간 초과는 여전할 것 같다. 생각해보니 위의 알고리즘 역시 O(n)일 텐데, n이 9999999999라면, 1억이 넘는 것이기 때문에 1초가 초과될 것 같긴 하다.(컴퓨터 성능에 따라 다르겠지만..)
3. (번외) 만약 자바로 풀었다면?
이 문제를 만약 java로 풀었다면?
굳이 문자열을 하나하나 비교할 것없이, String의 reverse 메서드를 이용해서 true이면 count하도록 했어도 훨씬 빠를 것 같긴하다.
[소감]
아무튼 이 문제를 풀면서 여러가지 생각이 들었는데, 역시 간단한 문제일수록 최적화에서 빛을 발해야 한다는 점이다.
그리고 거듭제곱 메서드를 쓰는데 우리 모두 sqrt를 pow로 착각해서 pow를 써야 할 것을 sqrt로 적고는 이상하다~?하고 있던게 너무 어이없었다..ㅋㅋ 기본기를 잘 하자!!
여러가지 접근법을 고민해보고 하는 과정에서, 서로의 코드를 리뷰하고 최적화를 위해 여러 지식도 공유할 수 있어서 많이 배우고 왔다.
D의 최적화를 해결 할 동안 간단하게 C를 풀었다.
C번 문제
주어진 문자열에서 HAPPY, SAD에 포함되어 있는 문자가 등장하면 카운트하고, 그 합산에 따라 이 문자열을 보낸 사람의 행복지수를 측정하는 문제이다.
P_h = H,A,P,Y의 등장 횟수 합산
P_g = S,A,D의 등장 횟수 합산
행복지수 = P_h/(P_h+P_g)
행복지수를 퍼센티지로 나타내야하기 때문에 식에 100을 곱하고, 소수점 둘째자리까지라서, 출력할 때 .2f로 출력하였다.
이 문제는 그냥 문자열을 for문으로 순회하면서 한 글자씩 H,A,P,Y에 해당하면 P_h를 카운트, S,A,D에 해당하면 P_g를 카운트하도록 하였다. (즉 A이면 둘다 카운트한다)
그렇게 해서 행복 지수 식에 대입해 행복지수를 출력하였다.
예외로, P_h와 P_g가 같으면 행복지수가 0임이 조건으로 있어서 이에 대한 처리도 해주었다.
이 문제의 난이도는 비교적 매우 쉬운 편이었다.
그리고 풀다가 시간이 끝나 구현해 보지 못한 문제..
G번? F번?
몇번이었는지 기억은 안나는데, n개의 별의 좌표를 x,y 평면에 주어졌을 때 어떤 한 점에 대칭인 별의 최대 개수를 구하는 문제였다. 이때 어떤 한 점은 주어지지 않기 때문에, 더 어려웠던 것 같다.
수학적으로 창의성을 요구하는 문제이기도 했고, 끝까지 팀원들과 여러 방법을 갈구해보았으나, 정답으로 가는 식을 찾지는 못한 것 같다.
<총평>
생각보다 시간이 널널한 것 같아도, 9-10문제이기도 하고, 수학적 창의성을 요하는 문제가 너무 많아서, 다 풀기에는 무리였지만, 쉬운 문제는 또 풀기 쉬웠던 것 같다.
문제가 영어로 되어 있어서 해석하는데에도 오래걸린 것도 있다..
실시간으로 문제를 여러 사람과 풀어보는 게 처음이기도 했지만, 확실히 내가 주춤거렸던 부분에 대해서 옆에 팀원이 척척 해결해주니 그 시너지가 정말 크게 느껴졌다.
서로의 부족한 점을 채우면서 하나의 문제를 해결해 갔을 때 그 희열은 아직 잊을 수가 없다.
결과가 어떻든, 함께 해결해 나가는 것의 즐거움을 느꼈고, 비슷한 기회가 있다면 다음에는 더 성장해서 한 번 더 시도해보고 싶다!!