Baekjoon 1181. 단어 정렬

nang_nang·2022년 11월 25일
0

PS

목록 보기
10/18

📝 Baekjoon 1181 문제풀이


💡문제 정의


문자열 관련 문제가 나오면 문자열을 저장하는 것에서부터 막힌다...
malloc으로 문자열을 끄적끄적 하다가 실패.
여러 문자열을 저장할 때는 2차원 배열을 사용하는 것이 가장 간편한 것 같다!! 명심!!

그리고 이 문제를 통해 알게 된 것은 바로

qsort로 문자열을 정렬할 수 있다!

보통 qsort로 숫자를 정렬할 때에는 4번째 파라미터인 compare 함수를 아래와 같이 정의한다.
qsort 함수 관련 포스트

int compare(const void *first, const void *second) {
	if (*((int *)first) - *((int *)second) > 0) return 1;
    else if (*((int *)first) - *((int *)second) < 0) return -1;
    else return 0;
}

이 문제에서는
1. 문자열의 길이
2. 길이가 같다면, 알파벳순
이렇게 2가지 기준으로 문자열을 비교 및 정렬해야 하는데, compare 함수를 적절히 수정하여 문자열을 쉽게 정렬할 수 있다.

int strComp(const void *first, const void *second) {
	int a = strlen((char *)first);
    int b = strlen((char *)second);
    
    if (a > b) return 1;
    else if (a < b) return -1;
    else return strcmp((char *)first, (char *) second);
}

strcmp는
1. str1 < str2 라면, 음수 반환
2. str1 > str2 라면, 양수 반환
3. str1 == str2 라면, 0 반환
위와 같이 결과를 반환하기 때문에 만약 문자열의 길이가 같다면(else block) -> strcmp를 활용하여 각 문자열 character들의 아스키 코드 값을 비교해야 한다. 예를 들어 'a'와 'b'를 비교한다면 strcmp는 음수를 반환할 것이고, 'a'가 'b'보다 앞에 오도록 정렬(오름차순)될 것이다.

이를 이용하여 아래와 같이 소스코드를 작성했다.

1) C

# include <stdio.h>
# include <stdlib.h>
# include <string.h>

char words[20000][51];

int strComp(const void *first, const void *second) {
  int a = strlen((char *)first);
  int b = strlen((char *)second);

  if (a > b) return 1;
  else if (a < b) return -1;
  else return strcmp((char *)first, (char *)second);
}

int main(void) {
  int N;
  scanf("%d", &N);
  for (int i = 0;i < N;i++) scanf(" %s", words[i]);

  qsort(words, N, sizeof(char) * 51, strComp);
  
  printf("%s\n", words[0]);
  for (int i = 1;i < N;i++) {
    if (strcmp(words[i], words[i - 1]) != 0) printf("%s\n", words[i]);
  }

  return 0;
}

words는 2차원 배열이므로, 배열 요소 하나의 크기는 sizeof(char) column 길이 = sizeof(char) 51임을 명심!!


💡참고

https://velog.io/@honeyricecake/%EB%B0%B1%EC%A4%80-1181%EB%B2%88-%EB%8B%A8%EC%96%B4-%EC%A0%95%EB%A0%AC

https://kentakang.com/121

https://blockdmask.tistory.com/391

profile
조금씩 앞으로

0개의 댓글