[hackerrank] Grid Challenge

문제 : https://www.hackerrank.com/challenges/grid-challenge/problem

---

NxM 배열이 주어지면 각 열이 사전 순 배열이 될 수 있는지 판단하는 문제.

같은 행에 있는 문자들은 순서를 변경할 수 있다.

---

각 열을 사전순으로 배열한 후 같은 행에 있는 문자들이 사전순으로 정렬되어 있는지 판단하면 된다.

각 열을 사전순으로 배열한다면

a1	a2	a3	a4
b1	b2	b3	b4
c1	c2	c3	c4
d1	d2	d3	d4

a1 < a2 < a3 < a4

b1 < b2 < b3 < b4

c1 < c2 < c3 < c4

d1 < d2 < d3 < d4

가 된다.

 

만약 a2 > b2여서 2번째 열이 사전순 배열이 안되어 a2보다 작은 a1을 a2대신 사용한다고 하더라도 

b1 < b2

a1 < a2

a2 > b2

이기 때문에 a2 > b1가 된다.

즉, 2번째 열을 사전순 배열을 맞추기 위해 1번째 열의 사전순 배열을 망칠수도 있다.

 

따라서 각 행들을 사전순배열을 한 뒤, 각 열들을 사전 순 배열을 확인했을 때 하나라도 사전순 배열이 되지 않는다면 "NO', 모두 사전순 배열이라면 "YES"를 출력한다.

 

시간복잡도는 N개의 M사이즈 배열을 오름차순 배열하기 때문에 O(N x MlogM).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/hackerrank/easy/Grid%20Challenge.cpp