배열을 이용한 코딩 스킬(중요)

이 글은 학회 회원 랑이집사님의 허락을 받아 에브리타임 게시글을 그대로 가져왔습니다.

 

문제에 주어진 정보가 많을 경우 구현 시간을 많이 줄일 수 있는 방식이라 코딩테스트, 특히 삼성을 준비하신다면 꼭 알아야 할 방법이라고 생각해서 코딩테스트가 몇개라도 남아있을 때 얼른 올리려고 지금 적습니다.

우선 문제부터 보여드리겠습니다.

http://boj.kr/2948

월, 일을 입력받아서 무슨 요일인지 출력하는 문제입니다. 월, 일 순서가 아닌 일, 월 순서로 입력받는다는 함정이 있어요.
이 문제의 해법은 간단한데, 1월 1일이 목요일이니 1월 8, 15, 22, 29일은 모두 목요일입니다. 마찬가지로 1월 2, 9, 16, 23, 30일은 모두 금요일입니다.
그럼 2월 1일은 무슨 요일일까요? 2월 1일은 1월 31일의 다음날이니 1월 32일이라고 생각할 수 있습니다. 즉, 2월 n일은 1월 31+n일로 표현 가능하고, 31+n일을 7로 나눈 나머지를 이용해 요일을 알아낼 수 있습니다.
3월은 어떨까요? 3월 n일은 월 31+28+n일이라고 볼 수 있습니다.
4월은 31+28+31+n일, 5월은 31+28+31+30+n일이 됩니다. 그럼 이걸 아래처럼 코딩할 수도 있습니다.

if(m == 2) d += 31;
else if(m == 3) d += 31+28;
else if(m == 4) d += 31+28+31;
...
//12까지

보기만 해도 별로 좋은 코드는 아니라는 느낌이 들죠. 코드는 반복되는 느낌인데 반복문을 쓰면 참 좋겠습니다.

int days[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};

for(i = 1; i < m; i++)
{
d += day[i];
}

이런식으로요.

11개의 if가 하나의 배열과 하나의 반복문으로 줄어들었습니다. 훨씬 편하기도 하고 가독성도 좋아진것 같아요.

그럼 이제 정답을 구해보겠습니다. 1일이 목요일이었으니 7로 나눈 나머지가 1이면 목요일, 2면 금요일...이겠네요.
그럼 다시 아래처럼 코딩이 가능합니다.

d %= 7;

if(d == 0) 수요일
else if(d == 1) 목요일
else if(d == 2) 금요일
...

이 코드 모양 아까 봤었죠? 배열로 바꿔봅시다.

string answer = {"Wednesday", "Thursday",...}

cout << answer[d];

마찬가지로 if문 7개를 배열 하나와 출력문 하나로 줄일 수 있습니다.


정답 코드

#include<iostream>
#include<string>
using namespace std;

int days[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
string ans[7] = { "Wednesday", "Thursday", "Friday", "Saturday", "Sunday","Monday", "Tuesday" };

int main()
{
int a, b;
int i;

cin >> a >> b;

for (i = 1; i < b; i++)
{
a += days[i];
}

cout << ans[a % 7];
}







다른 문제도 보겠습니다.

http://boj.kr/2037

이 문제에서 처리할게 많은건 아래 두가지입니다.
1. 이전에 누른 것과 같은 숫자를 눌러야 하는지 확인하기.
2. 이 문자를 입력하기 위해 해당 숫자를 몇 번 눌러야 하는지 구하기.

이 둘을 처리하다 보면 if문이 상당히 많이 나오게 되는데, 사실 그럴 필요 없습니다.


int num[26] = { 2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,7,8,8,8,9,9,9,9 };
int push[26] = { 1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,4,1,2,3,1,2,3,4};

num은 각 알파벳이 어떤 번호를 눌러야 하는지, push는 각 알파벳이 해당 숫자를 몇 번 눌러야 하는지 저장한 배열입니다. 예를들어 E는 5번째 알파벳이니 5번째 값(4번 인덱스)을 보면 3을 2번 눌러야 한다는 것을 알 수 있습니다.

이것만 있으면 아래처럼 간단하게 풀 수 있습니다.

for(i = 0; i < str.length(); i++)
{
//공백이라면 1을 한번 누르는 시간만 더합니다.
if(str[i] == ' ') ans += p;
//앞과 같다면 push번 누르는 시간 + 대시시간을 더합니다.
else if(i != 0 && num[str[i]-'A'] == num[str[i-1]-'A']) ans += push[str[i]-'A'] + w;
//앞과 다르다면 push번 누르는 시간만 더합니다.
else ans += push[str[i]-'A'];
}


이렇게 배열을 잘 이용할 경우 if문을 불필요하게 많이 사용하는 것을 어느정도 방지할 수 있습니다.



정답 코드

#include<iostream>
#include<string>
using namespace std;

int arr[26] = { 2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,7,8,8,8,9,9,9,9 };
int push[26] = { 1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,4,1,2,3,1,2,3,4 };

int main()
{
int a, b;
string str;
int i;
int ans = 0;

cin >> a >> b;
cin.ignore();
getline(cin, str);

for (i = 0; i < str.length(); i++)
{
if (str[i] == ' ') ans += a;
else if (i != 0 && (arr[str[i] - 'A'] == arr[str[i - 1] - 'A'])) ans += a * push[str[i] - 'A'] + b;
else ans += a * push[str[i] - 'A'];
}

cout << ans;
}





실제로 구현 몇번 해보면 금방 감이 오실테니 연습해볼만한 문제들도 올려드리겠습니다.


http://boj.kr/3003

http://boj.kr/1284

http://boj.kr/17362

http://boj.kr/1864

http://boj.kr/2490

http://boj.kr/1264

http://boj.kr/2037

http://boj.kr/2520

http://boj.kr/2789

http://boj.kr/2948

http://boj.kr/2966

http://boj.kr/3154

http://boj.kr/4435

http://boj.kr/4606

http://boj.kr/5585

http://boj.kr/5622

http://boj.kr/6368

http://boj.kr/6750

http://boj.kr/6765

http://boj.kr/11800