0618

백준: So☆Lucky

오늘은 기분이 조아서 골드 문제 풀겠슴다

맨 첨엔 그냥 단순한 구현 문제라고 생각하고
진짜 문제에 적혀있는 조건 그대로 while문으로 풀었다
하지만 당연히? 시간초과 발생

n이 20만까지 주어지는데 1초 안에 풀려야되니
그래프로 풀어야 될 것 같다는 생각이 들었다

리스트에서 인접한 인덱스끼리 교환하여 정렬하는건 버블 정렬인데
버블 정렬을 빠르게 하는 방법은 union find니까
union find 후에 sorted랑 비교해서 플래그로 출력하면 되지 않을까
했는데 10%대에서 넘어가지 못하고 계속 틀렸다

다시 돌아가서 어케 풀어야지..하다가
두 수를 더했을 때 합이 짝이 나오려면 무조건 홀/짝 아님 짝/홀 이어야 되고
홀이 나오려면 짝짝 아님 홀홀 이어야 하지 않는가

즉 홀수합을 스위칭할 땐 홀수합 짝수합을 미리 구해놓고
이 순서가 정렬 순서와 같다면 홀수합 스위칭 조건을 만족하는거고

짝수합은 그룹들을 각각 정렬한 후 전체를 합쳤을 때 결과와 같다면 만족한다는 식으로
풀었는데.... 그래프로 풀었을 땐 왜 틀린걸까 흠

RealWorld

• Form 라이브러리 관련 포스팅

음 useMemo 관련 글을 읽는데

콘서트 결제가 생각나네요
근데 메모이제이션 관련해서도 좀 다시 생각해봐야 될 것 같아요
뭔가 성능과 관련한 글들은 정확한 수치가 없으면 화다닥 하고 와닿는 기분이 안 든다 랄까..........