코딩테스트 대비 스터디 문제 풀이 #1

이번 학기 우리학교에 코딩부트캠프라는 새로운 과목이 개설되었다.
강의계획서 상으로 보니 코딩테스트를 대비하는 과목이라고 한다.
일단 주전공 3학년을 대상으로 수강신청을 받았고, P/F 과목이라서 듣는 것이 좋을 것 같아 신청하게 되었다.
이 과목은 총 3번의 코딩 테스트를 실시하게 되는데 3번 중에 1번만 통과하면 Pass를 받을 수 있다고 한다.

 

하지만 대다수의 3학년 학생들은 코딩테스트나 대회 준비를 해보지 않은 사람들이 많기에 Pass를 걱정하는 사람이 많았고, 알고리즘 학회에서 코딩부트캠프 스터디를 열게 되었다.

그나마 내가 대회나 코딩테스트 경력이 어느 정도 있는 사람으로 스터디장을 맡게 되었다.

 

일단 주교재로 이것이 취업을 위한 코딩테스트다 (나동빈 저)를 주로 사용하고 있다.
출간된 지 얼마 안된 책이기도 하고 전반적인 내용이 좋아 선택하게 되었다.

 

그리고 나동빈님 책으로 진도를 맞춰가면서 적당히 연습 문제들을 매주 선별하여 출제하고 있다.

참고로 이번 연습 문제들은 나동빈님 책 기준으로 챕터 1 ~ 4까지 나간 뒤에 출제한 문제다.
따라서 해당 문제들의 간략한 풀이와 함께 소스코드를 제공하기 위해서 이 글을 작성한다.

 

A - 닉네임에 갓 붙이기
줄바꿈 문자를 제외하고 입력받은 뒤에 공백 문자가 나오기 전까지는 버리고 "god"을 출력한 뒤에 이후에는 원래 이름을 출력하면 된다.

#include <bits/stdc++.h>

int main()
{
  int n;
  char lf;
  scanf("%d",&n);
  scanf("%c",&lf);
  while(n--)
  {
    char ch[202];
    scanf("%[^\n]",ch);
    scanf("%c",&lf);

    bool flag=false;
    for(int i=0;i<strlen(ch);i++)
    {
      if(ch[i]==' ' && !flag) printf("god"),flag=true;
      else if(ch[i]!=' ' && flag) printf("%c",ch[i]);
    }
    printf("\n");
  }
  return 0;
}

 

B - 피보나치 수, C - 피보나치 수 2
결국 두 문제를 다 풀려면 다이나믹 프로그래밍을 써야된다.

#include <bits/stdc++.h>

int main()
{
  long long a[99];
  int n;
  scanf("%d",&n);
  a[0]=0,a[1]=1;
  for(int i=2;i<=n;i++) a[i]=a[i-1]+a[i-2];
  printf("%lld",a[n]);
  return 0;
}

 

D - 피카츄
문자열 상에서 index를 비교해가면서 pi, ka, chu 세개의 문자열이 계속 나오는 지를 비교하면 된다.

#include <bits/stdc++.h>
int main()
{
  std::string pika;
  bool flag = true;

  std::cin>>pika;
  for(int i=0;i<pika.size();)
  {
    if(i+2<=pika.size() && pika.substr(i, 2)=="pi") i+=2;
    else if(i+2<=pika.size() && pika.substr(i, 2)=="ka") i+=2;
    else if(i+3<=pika.size() && pika.substr(i, 3)=="chu") i+=3;
    else
    {
      flag=false;
      break;
    }
  }
  std::cout<<(flag?"YES":"NO");
}

 

E - 배열 합치기
투 포인터라는 개념을 묻는 문제. 두 배열의 각각의 index를 가지고 해결해 나아가면 된다.

#include <bits/stdc++.h>

std::vector<int> a,b;

int main()
{
  int n,m;
  scanf("%d %d",&n,&m);
  a.resize(n),b.resize(m);
  for(int i=0;i<n;i++) scanf("%d",&a[i]);
  for(int i=0;i<m;i++) scanf("%d",&b[i]);

  int pa=0,pb=0;
  while(pa<n || pb<m)
  {
    if(pa>=n) printf("%d ",b[pb++]);
    else if(pb>=m) printf("%d ",a[pa++]);
    else if(a[pa]>b[pb]) printf("%d ",b[pb++]);
    else printf("%d ",a[pa++]);
  }
  return 0;
}

 

F - 방번호
0부터 9까지 숫자별 갯수를 세준 뒤에 6과 9를 더한 뒤에 반으로 나누면 된다.

#include <bits/stdc++.h>

int main()
{
  char num[11];
  scanf("%s",num);

  int cnt[11]={0,};
  for(int i=0;i<strlen(num);i++) cnt[num[i]-'0']++;
  int hap=cnt[6]+cnt[9];
  cnt[6]=hap/2,cnt[9]=hap/2;
  if(hap%2) cnt[6]++;
  
  int res=0;
  for(int i=0;i<10;i++) res=std::max(res,cnt[i]);
  printf("%d",res);
  return 0;
}

 

G - 잃어버린 괄호
마이너스가 나오기 전까지 모든 수들은 더해주고, 마이너스가 나온 이후부터는 모든 수들을 빼주면 된다.

#include <bits/stdc++.h>

int main()
{
  char sik[55];
  int su=0,res=0;
  bool flag=false;
  scanf("%s",sik);

  for(int i=0;i<strlen(sik);i++)
  {
    if(sik[i]=='-' || sik[i]=='+')
    {
      res=(flag?res-su:res+su);
      if(sik[i]=='-' && !flag) flag=true;
      su=0;
    }
    else su=su*10+(sik[i]-'0');
  }

  if(flag) printf("%d",res-su);
  else printf("%d",res+su);
  return 0;
}

 

H - 회의실배정
가장 빨리 끝나는 회의부터 배정하면 된다.

#include <cstdio>
#include <vector>
#include <algorithm>

int main()
{
    int n;
    scanf("%d", &n);

    std::vector<std::pair<int, int>> meet(n);
    for (int i = 0; i < n; i++) scanf("%d %d", &meet[i].second, &meet[i].first);

    std::sort(meet.begin(), meet.end());

    int time = 0, cnt = 0;
    for (int i = 0; i < n; i++)
    {
        if (meet[i].second < time) continue;
        time = meet[i].first;
        cnt++;
    }

    printf("%d", cnt);
    return 0;
}

 

I - 회문
앞뒤가 같은 지 계속 체크하다가 문제가 되는 지점이 발생하면 앞쪽 것 하나빼고 비교, 뒤쪽 것 하나빼고 비교를 한 뒤에 둘 다 문제가 되는 경우면 2를 출력하고, 둘중 하나라도 되면 1을 출력한다. 만약 문제가 발생하지 않으면 0을 출력하면 된다.

#include <bits/stdc++.h>
char ch[101010];

std::pair<int,int> palindrome(int ps,int pe)
{
  while(ps<pe)
  {
    if(ch[ps]!=ch[pe]) return {ps,pe};
    ps++,pe--;
  }
  return {-1,-1};
}

bool isPalindrome(int ps,int pe)
{
  std::pair<int,int> res=palindrome(ps,pe);
  return (res.first==-1 && res.second==-1);
}

int main()
{
  int t;
  scanf("%d",&t);
  while(t--)
  {
    scanf("%s",ch); 
    std::pair<int,int> res=palindrome(0,strlen(ch)-1);
    
    if(res.first==-1 && res.second==-1) printf("0\n");
    else if(isPalindrome(res.first,res.second-1)
      || isPalindrome(res.first+1,res.second)) printf("1\n");
    else printf("2\n");
  }
  return 0;
}

 

J - 빗물
가장 왼쪽에 아주 높은 높이의 벽이 있다고 가정하고 한번 진행하고, 가장 오른쪽에 아주 높은 높이의 벽이 있다고 가정하고 한번 진행한 뒤에 두 경우 중 물의 높이의 최소값에서 해당 높이를 빼주면 답이 된다.

#include <bits/stdc++.h>

int block[505],right[505],left[505];

int main()
{
  int h,w;
  scanf("%d %d",&h,&w);
  for(int i=1;i<=w;i++) scanf("%d",&block[i]);

  for(int i=1;i<=w;i++) right[i]=std::max(right[i-1],block[i]);
  for(int i=w;i>=1;i--) left[i]=std::max(left[i+1],block[i]);

  int cnt=0;
  for(int i=0;i<w;i++) cnt+=(std::min(left[i],right[i])-block[i]);
  printf("%d",cnt);
  return 0;
}