[백준] 11650번 좌표 정렬하기 ( 파이썬 / c언어)

│문제

11650번: 좌표 정렬하기

 

│풀이 (Python)

N=int(input())

arr = [[0 for j in range(2)] for i in range(N)]

for i in range(N):

    arr[i][0],arr[i][1]=map(int,input().split())

arr.sort()

for i in range(N):print(arr[i][0],arr[i][1])

│설명  (Python)

keypoint 1- 파이썬 리스트 기본 메서드인 sort() 함수를 활용

 

tips)한 줄 for문 작성 방법

for i in range(n):

    print("hello")

 단순한 for문이 있을때에는 두줄로 나눠져 있기보다 한 줄로 작성하였을 때 가독성도 좋고 더 깔끔해 보인다.

[print("hello") for i in range(n)]

또한 한 줄 for문 작성을 사용하기에 유용한 예로는 이중배열 선언이 있다.

arr=[[]]

for i in range(row):

    for j in range(col):

        arr.append(0)

위와 같은코드를 한 줄로 작성 시 매우 깔끔하게 가독성이 좋게 작성할 수 있다.

arr=[[0 for i in range(col)] for j in range(row)]

 

 

│풀이 (C언어)

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

#include <stdlib.h>

typedef struct {

    int x;

    int y;

}coordinate;

int compare(const void* a, const void* b)

{

    coordinate A = *(coordinate*)a;

    coordinate B = *(coordinate*)b;

    if (A.x > B.x) return 1;

    else if (A.x == B.x)

    {

        if (A.y > B.y) return 1;

        else return -1;

    }

    return -1;

}

int main(void) {

    int n;

    scanf("%d", &n);

    coordinate* arr = (coordinate*)malloc(sizeof(coordinate) * n);

    for (int i = 0; i < n; i++) scanf("%d %d", &arr[i].x, &arr[i].y);

    qsort(arr, n, sizeof(coordinate), compare);

    for (int i = 0; i < n; i++) printf("%d %d\n", arr[i].x, arr[i].y);

    free(arr);

}

 

│설명  (C언어)

 

keypoint 1- 구조체 활용 

이중배열을 활용하기에 qsort함수를 사용 시 불편함이 있다. 이를 해결하기 위해 구조체를 활용하여서 이중배열과 같이 int x, int y를 선언하여 좌표를 구성한다.

 

keypoint 2- 동적할당

구조체에 할당할 크기가 사용자에게 입력받은 후 정해지기 때문에 동적할당을 활용하여 풀이하여야 한다.

 

c언어에서는 기본적으로 malloc()을 이용하여 동적할당을 한고, 동적할당을 사용 후 프로그램 종료 전에 free()로 메모리 해제를 한다. 함수의 원형은 다음과 같다.

void * malloc ( size_t size );

void free ( void * ptr );

문제에 상황인 경우 아래와 같이 작성할 수 있다.

 coordinate* arr = (coordinate*)malloc(sizeof(coordinate) * n);

free(arr);  

 

ps) 대부분의 Os에서는 free()처리를free() 처리를 해주지만 free() 처리를 해주지 않는 환경에서 작업 시 습관이 안 들여져 있다면 매우 찾기 어려울 수 있다. 절대 free()를 까먹지 마!

keypoint 3- qsort 정렬 / qsort 라이브러리 활용

c언어에서 <stdlib.h> 라이브러리에서 아래와 같이 qsort함수가 정의되어 있다.

void qsort (void *base, size_t nel, size_t width, int (*compare)(const void *, const void *));

void *base: 정렬하고자 하는 배열

size_t nel:배열의 사이즈

size_t width : 배열에서 원소의 사이즈   ex) sizeof(int), sizeof(float)

 int (*compare)(const void *, const void *): 비교함수    /    비교함수는 아래와 같이 작성할 수 있다.

int compare(const void* a, const void* b)    

{

    int num1 = *(int*)a;    

    int num2 = *(int*)b;  

    if (num1 < num2)    

        return -1;    

    if (num1 > num2)  

        return 1;      

   

    return 0;  

}

각 if문 아래의 숫자인 -1과 1을 바꿔보면 오름차순과 내림차순을 조절할 수 있다.

정리하면 void qsort(정렬하고자 하는 배열, 사이즈, 배열에서 원소의 사이즈, 비교함수)라 할 수 있다.

 

keypoint 4 - compare함수 변형

compare( (void *) & elem1, (void *) & elem2 );

 

c언어의 qsort라이브러리를 활용할 때 작성하는 compare함수는 개인의 필요에 따라 변형하여 사용할 수 있다.

qsort에서 compare의 리턴값의 원리는 compare의 리턴값이 1보다 큰 경우 elem1과 elem2를 교환하고, 0보다 같거나 작은 경우 elem1과 elem2를 교환하지 않는다.

해당 특징을 활용하여 아래와 같이 작성하였다. 

    if (A.x > B.x) return 1;

    else if (A.x == B.x)

    {

        if (A.y > B.y) return 1;

        else return -1;

    }

    return -1;

A.x와 B.x의 좌표가 같다면 조건문 if (A.y > B.y)을 실행하여 return값 1 또는 -1을 출력하도록 구현하였다.

 

 

qsort함수와 compare함수에 대해 더 알아보고 싶다면, 아래의 사이트를 참고하는 것을 추천한다.

qsort

 

 

 

 

 

 

( 연결된 게시글 )

 

※ 동적할당, qsort라이브러리

[백준] 2751번 수 정렬하기 2 ( 파이썬/ c언어 )

※ 한 줄 for문

[백준] 1874번 스택 수열 (파이썬)