[코딩테스트 34일차] BAEKJOON 11650번 : 좌표 정렬하기, 1193번 : 분수찾기

[BAEKJOON 11650번 : 좌표 정렬하기]

[문제]

---

[고찰]

처음에 이 문제를 보고 풀 때, vector<int[2]> coordinate(n); 으로 크기 2의 int형 배열로 좌표를 입력받을 벡터를 만들었습니다.

다만 컴파일을 시작한 뒤 오류가 발생하였고, 오류에서 말하는 핵심은, 정적 배열 타입을 vector에 직접 사용하여서 발생하는 컴파일 오류였습니다.

 

그래서 어떻게 풀어갈까 생각하다가, 답이 나오지 않아 두 쌍을 입력받을 수 있는 형식에 대해 검색하였고, pair를 택하게 되었습니다.

 

pair<int, int> p;로 pair를 선언한 뒤, cin >> p.first >> p.second;로 입력을 받았습니다.

그리고 boolean을 return으로 하는 compare 함수를 만들어, pair before과 pair after를 인자로 받아, 사용자 정의 정렬을 할 수 있게 구현하였습니다.

bool compare(pair<int, int> before, pair<int, int> after)
{
	if (before.first != after.first)
		return before.first < after.first;

	return before.second < after.second;
}

 

하지만 여기서 제가 간과한 것은, pair 타입은 sort를 사용했을 때, first를 기본으로 정렬하고 만약 first가 같다면 자동으로 second를 기준으로 정렬을 한다는 것이었습니다.

 

즉, 제가 구태여 compare 함수를 만들 필요가 없던 것이었습니다.

이는 제가 pair에 대해서 잘 몰랐기 때문이었고, 그래서 이를 정리하고자 합니다.

 

또한 struct를 썼을 때는 어떻게 구현을 해야할지도 같이 정리해보겠습니다.

 

아래는 제가 작성한 코드입니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool compare(pair<int, int> before, pair<int, int> after)
{
	if (before.first != after.first)
		return before.first < after.first;

	return before.second < after.second;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;

	vector<pair<int, int>> coordinate(n);

	for (int i = 0; i < n; i++)
	{
		pair<int, int> p;
		cin >> p.first >> p.second;
		
		coordinate[i] = p;
	}

	sort(coordinate.begin(), coordinate.end(), compare);

	for (int j = 0; j < n; j++)
	{
		cout << coordinate[j].first << " " << coordinate[j].second << '\n';
	}

	return 0;
}

---

[개념]

pair

#include <utility>

template <class T1, class T2> struct pair;

 

pair<T1, T2>는 서로 다른 타입 두 개를 묶는 STL 구조체입니다. 물론 같은 타입 두 개를 묶을 수도 있습니다.

주로 서로 연관된 2개의 데이터를 한 쌍으로 묶어서 다룰 때 사용됩니다.

• 헤더파일
  • #include <utility>
    • pair 클래스는 #include <utility>라는 헤더파일에 존재하는 STL입니다.
    • 그러나, <algorithm>과 <vector> 헤더파일에 이미 <utility> 헤더파일이 포함되어 있기 때문에, 앞의 두 헤더파일이 사용되었다면 굳이 <utility> 헤더파일을 주가해주지 않아도 됩니다.
• 요소 접근
  • T1과 T2는 각각 first와 second로 접근할 수 있습니다.
• pair 생성
  • 요소 직접 입력
    • pair<int, int> p;  p.first = 0; p.second = 1;
  • make_pair(value1, value2) 사용
    
    • value1, value2를 한 쌍으로 하는 pair를 만들어 반환합니다.
    • pair<int, int> p = make_pair(0, 1);
• pair의 sort( )
  
  • std::pair는 sort( )와 잘 호환되어 있습니다.
  • 정렬 기준은 아래의 기준대로 정렬되며, 오름차순으로 자동 적용이 됩니다.
    • first 값이 작은 순서
    • first가 같으면 second 값이 작은 순서

---

struct 사용

만약 해당 문제를 struct를 사용해서 풀었다면, 아래와 같이 구조체를 정의합니다.

struct Point
{
    int x, y;
};

 

구조체는 정렬함수 sort( )에 있어서, 사용자 정의 정렬을 적용해주어야 하기 때문에 compare 함수를 정의해야 합니다.

bool compare(const Point& a, const Point& b)
{
    if (a.x == b.x) 
        return a.y < b.y;
    
    return a.x < b.x;
}

---

 

auto 사용

아래의 Solution 코드를 살펴보면, 반복문에서 const auto& p를 사용합니다.

pair 클래스를 간편하게 반복하고자 사용하였습니다.

---

[정리]

이런 기본도 아직 잘 모른다는 것에 반성하며, 더욱 공부에 힘써야겠습니다.

또한 auto도 알고는 있었지만, 적용할 생각은 못했었습니다. 앞으로는 이런 것도 잘 생각하면서 문제 풀이를 할 것입니다.

---

[Solution : pair 사용]

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;

	vector<pair<int, int>> coordinate(n);

	for (int i = 0; i < n; i++)
	{
		cin >> coordinate[i].first >> coordinate[i].second;
	}

	sort(coordinate.begin(), coordinate.end());

	for (const auto& p : coordinate)
	{
		cout << p.first << " " << p.second << '\n';
	}

	return 0;
}

---

[Solution : struct 사용]

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Point
{
	int x, y;
};

bool compare(const Point& a, const Point& b)
{
	if (a.x == b.x)
		return a.y < b.y;

	return a.x < b.x;
}

int main()
{
	int n;
	cin >> n;

	vector<Point> coordinate(n);

	for (int i = 0; i < n; i++)
	{
		cin >> coordinate[i].x >> coordinate[i].y;
	}

	sort(coordinate.begin(), coordinate.end(), compare);

	for (const auto& p : coordinate)
	{
		cout << p.x << " " << p.y << '\n';
	}

	return 0;
}

---

[BAKEJOON 1193번 : 분수찾기]

[문제]

---

[고찰]

처음에 저는 위의 문제를 풀 때, 지그재그 순서로 분수가 변하는 것을 생각하지 못하고 문제를 풀었습니다.

그 결과 제 답변은 틀리게 되었습니다. 아래는 제가 처음에 작성한 코드입니다.

// ...

int main()
{
	// ...

	int x;
	cin >> x;

	if (x == 1)
	{
		cout << "1/1";
		return 0;
	}

	int i;

	for (i = 1; x - i > 0; i++)
	{
		isLineLeft = !isLineLeft;
		x -= i;
	}

	pair<int, int> fraction;

	for (int j = 1; j <= x; j++, i--)
	{
		fraction = make_pair(j, i);
	}

	cout << fraction.first << "/" << fraction.second;

	return 0;
}

 

 

그래서 이번에는 지그재그를 체크하기 위해, isLineLeft라는 boolean 변수를 만들어서 이에 따라 구현을 달리 해주었습니다.

아래는 제가 수정을 해서, 정답이 된 코드입니다.

#include <iostream>
#include <utility>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int x;
	cin >> x;

	if (x == 1)
	{
		cout << "1/1";
		return 0;
	}

	bool isLineLeft = false;

	int i;

	for (i = 1; x - i > 0; i++)
	{
		isLineLeft = !isLineLeft;
		x -= i;
	}

	pair<int, int> fraction;

	if (isLineLeft)
	{
		for (int j = 1; j <= x; j++, i--)
		{
			fraction = make_pair(j, i);
		}
	}
	else
	{
		int denominator = 1;

		for (int j = 0; j < x; j++, i--, denominator++)
		{
			fraction = make_pair(i, denominator);
		}
	}

	cout << fraction.first << "/" << fraction.second;

	return 0;
}

 

다만, 다른 분들의 풀이를 보니 저처럼 pair 클래스를 사용하지 않고, line을 int로 선언한 뒤, 분자와 분모를 line을 통해 직접 계산해주는 것을 보았습니다.

 

그래서 제 코드가 비효율적인 코드라는 것을 깨달았습니다.

제 코드에서 좀 더 효율적으로 수정하기 위해 고민한 결과, for문을 사용하여 불필요하게 fraction을 반복 갱신할 필요가 없다는 것이었습니다.

 

그래서 제 코드를 효율적으로 수정한 것과, int 타입의 line을 사용하는 코드, 두 가지 버전을 함께 정리하고자 합니다.

---

[개념]

코드 리팩토링

for문을 불필요하게 사용하여 fraction을 계속 갱신할 필요 없이, i 와 x를 통해 한줄로 계산하는 것이 가능하였습니다.

 

만약, isLineLeft가 True일 때는, 분자는 x, 분모는 i - x + 1로 계산이 가능하였고,

False일 때는, 분자는 i - x + 1, 분모는 x로 계산이 가능하였습니다.

 

즉, isLineLeft에 따라 분자와 분모의 순서만 바꿔주면 되었습니다.

 

x는 위쪽의 반복문에서 i를 빼는 연산을 통해, 대각선 내에서 몇 번째 수인지를 의미합니다.

i는 해당 대각선에서 분수의 개수입니다.

 

만약  isLineLeft가 True일 때, 분자는 대각선 내에서 몇 번째 수인지를 통해(x를 통해) 바로 알아낼 수 있고,

대각선에서 분수의 개수인 i에서 x를 뺀 뒤, 1을 더하면 분모가 되는 것입니다.

 

이를 코드에 적용하여 수정하게 된다면, fraction 선언 이후 코드를 아래와 같이 수정하면 됩니다.

if (isLineLeft)
    fraction = make_pair(x, i - x + 1);
else
    fraction = make_pair(i - x + 1, x);

 

이렇게 적용하면 x가 1일 때 예외처리를 해주지 않아도 됩니다.

---

int line 활용

int line을 활용한다면, x가 line보다 이상일 때 계속 반복해주면서, x에서 line을 빼준 값을 다시 x에 넣고, line을 1 증가시켜 줍니다.

이것은 제가 for 문에서 x에서 i를 뺀 후, i++을 통해 1 증가시켜준 것과 동일하며, 제 코드에서 i가 int line을 활용했을 때의 line과 동일한 것입니다.

 

그리고 int numerator, donomiantor라는 분자와 분모를 위한 두 int 형 변수를 선언합니다.

이 과정은 제가 fraction을 선언한 것과 동일합니다.

 

이후, line % 2가 0일 때는 짝수 번째 줄이라는 의미이기 때문에, 분자를 증가시켜야 하므로,

numerator = x;
denominator = line - x + 1;

 

line % 2가 0이 아닐 때는 홀수 번째 줄이라는 의미이기 때문에, 분자를 감소시켜야 하므로,

numerator = line - x + 1;
denominator = x;

를 해줍니다.

 

이 과정도 수정한 제 코드에서 isLineLeft에 따라 fraction의 값을 지정해주는 과정과 동일합니다.

 

이러한 연산을 마친 후, numerator와 denominator를 출력 양식에 맞게 출력해주면 됩니다.

---

[정리]

좀 더 생각했다면, 효율적으로 구현할 수 있을텐데 아쉽습니다.

항상 그 전에 생각이 그치는 것 같습니다.

앞으로는 좀 더 생각을 나아가게 하여 효율적으로 구현할 수 있도록 노력할 것입니다.

---

[Solution : 리팩토링된 코드]

#include <iostream>
#include <utility>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int x;
	cin >> x;

	bool isLineLeft = false;

	int i;

	for (i = 1; x - i > 0; i++)
	{
		isLineLeft = !isLineLeft;
		x -= i;
	}

	pair<int, int> fraction;

	if (isLineLeft)
		fraction = make_pair(x, i - x + 1);
	else
		fraction = make_pair(i - x + 1, x);

	cout << fraction.first << "/" << fraction.second;

	return 0;
}

---

[Solution : int line을 활용한 코드]

#include <iostream>
#include <utility>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int x;
	cin >> x;

	int line = 1;

	while (x > line)
	{
		x -= line;
		line++;
	}

	int numerator, denominator;

	if (line % 2 == 0)
	{
		numerator = x;
		denominator = line - x + 1;
	}
	else
	{
		numerator = line - x + 1;
		denominator = x;
	}

	cout << numerator << "/" << denominator;

	return 0;
}