[TIL]20210715

알고리즘

1157

1. 리스트에 다 저장하고 마지막에 max를 저장.
2. 전체 스캔 개수 세리고 max 저장하고 마지막에 출력 (메모리가 적게 사용되는 장점. 리스트를 안쓰니까.)

1.번으로 풀었을 때

#include <stdio.h>
#include <string.h>
int main()
{ 
  int max=0,quest=0,maxe=0;
  char abc[1000011];
  int count[26]={0};
  scanf("%s",abc);
  if(strlen(abc)!=1){
    for (int i=0;abc[i]!='\0';i++){
      if (64<abc[i] && abc[i]<91){
        count[abc[i]-65]++;
      }
      else if(96<abc[i] && abc[i]<123)
        count[abc[i]-97]++;
    }
    for (int i=0; i<26;i++){
      if (max<count[i]){
        quest=0;
        max=count[i];
        maxe=i;
      }
      else if (max==count[i]){
        quest=1;
      }
    }
    if (quest==1){
      printf("?\n");
    }
    else{
      printf("%c\n",maxe+65);
    }
}
  else{
      if(96<abc[0] && abc[0]<123){
        printf("%c\n",abc[0]-32);

      }
      else{
    printf("%c\n",abc[0]);
      }
  }
}

여기서의 교훈. 리스트를 만들때 int char 선언 확인하고, 초기화 잘해주기...

2번풀이: null

1152

#include <stdio.h>
#include <string.h>
int main()
{ 
  char a[1000001];
  int count=0,len;
  scanf("%[^\n]",a);
  len=strlen(a);
  if (len==1){
    if(a[0]==' '){
    printf("0\n");
    return 0;
    }
  }
  for (int i=1;i<len-1;i++){
    if(a[i]==' '){
      count++;
    }
  }
  printf("%d\n",count+1);
  return 0;
}

이 문제에서는 scanf("%[^\n]",a);와 for (int i=1;i<len-1;i++) 이 두개때문에 힘들었다.

scanf의 경우 띄어쓰기된 문장을 scan하는 방법을 몰라 인터넷을 찾아봤는데 예전 리눅스 배울때 봤던 [] 과 ^를 사용하는 방식이란 것을 알게됬다.
[]을 이용하면 대괄호 안에 포함된 문자들만을 스캔한다는 의미이고, 사이에 ^를 넣으면 니게이션되는 부분을 스캔한다는 의미를 가진다.

그리고 for 문의 경우도 해결할 방법을 떠올리지 못해 인터넷을 참고했다. i=0;i<len을 조건잡게되면 앞이나 뒤의 공백에 의해서 count가 되기때문에 각각 한자리씩 빼는 방법이 필요하다는 걸 배웠다. 그리고 공백+1이 단어 갯수임으로 출력할 때 1씩 더하는 원리로 이 문제를 해결했다.

2908

#include <stdio.h>
#include <string.h>
int main()
{
  int a,b;
  int ac,bc;
  scanf ("%d %d",&a,&b);
    ac=a/100+((a/10)%10)*10+a%10*100;
    bc=b/100+((b/10)%10)*10+b%10*100;
    if(ac<bc){
      printf("%d",bc);
    }
    else{
      printf("%d",ac);
    }
  }

5622

#include <stdio.h>
#include <string.h>
int main()
{
  int a,b,ran[15]={0},len=0,time=0,total=0;
  char inp[15];
  scanf("%s",inp);
  len=strlen(inp);
  for (int i=0;i<len;i++){
    if ('A'<=inp[i] &&inp[i]<='C'){
      ran[i]=1;
    }    
    else if ('D'<=inp[i] &&inp[i]<='F'){
      ran[i]=2;
    }
    else if ('G'<=inp[i] &&inp[i]<='I'){
      ran[i]=3;
    }
    else if ('J'<=inp[i] &&inp[i]<='L'){
      ran[i]=4;
    }
    else if ('M'<=inp[i] &&inp[i]<='O'){
      ran[i]=5;
    }
    else if ('P'<=inp[i] &&inp[i]<='S'){
      ran[i]=6;
    }
    else if ('T'<=inp[i] &&inp[i]<='V'){
      ran[i]=7;
    }
    else if ('W'<=inp[i] &&inp[i]<='Z'){
      ran[i]=8;
    }

  }

  for(int j=0;j<len;j++){
    total+=ran[j]+2;
  }
  printf("%d",total);
  return 0;
}

자료구조 - 트라이

‘트라이’는 각 노드가 ‘배열’로 이루어져있는 ‘트리’ 형태의 자료 구조이다.
그리고 배열의 각 요소는 다음 층의 노드를 가리킨다.

시간복잡도는 O(1) 정도이지만 메모리를 많이 사용한다.