[Softeer] Java - 통근버스 출발 순서 검증하기

Softeer

너무 허탈하고 열 받아서 오랜만에 알고리즘 포스팅 한다...

문제

문제 설명은 위 링크에서 자세하게 확인할 수 있지만 간단하게 요약하면 "스택 정렬을 만들 수 없는 원인의 개수를 찾아라." 이다.

 

예를 들어서 6, 7, 5 과 같은 순서로 숫자가 있다.

이런 3개의 숫자가 쌍을 이뤘을 때, 가운데 수가 제일 크고 첫 번째 수가 두 번째로 크면 스택 정렬을 할 수 없다.

 

위와 같은 경우의 수의 개수를 찾는 문제다.

물론 각 숫자는 늘 연속적으로 존재하지는 않는다.

 

---

풀이

솔직히 보자마자 느낀거는 이런 문제를 브루트포싱으로 풀라고 내놓았을 것 같지는 않았다.

브루트포싱으로 이 문제를 해결하려면 아마 O(n^3)이 나와서 시간 초과가 뜰 것이 분명하다.

그래서 생각한 것은 투 포인터를 활용할 수 있을까 였다.

 

다음 TC로 풀이 설명하겠다.

# TC
## 입력
5
4 2 5 3 1

# 경우의 수
0 0 0 0 0 
1 1 1 1 0 
2 1 1 1 0 
3 2 2 1 0 
3 2 2 1 0

## 출력
4

위 입력을 보면 4, 2, 5, 3, 1의 수가 주어진다.

 

처음 예시처럼 6, 7, 5와 같은 쌍을 선택했을 때, 첫 번째 수가 세 번째 수보다 커야한다는 것을 알 수 있다.

그렇기에 다음과 같이 경우의 수를 확인할 수 있다.

 

1. 첫 번째 인덱스 부터 마지막 인덱스까지 돌면서 각 인덱스보다 작은 값의 개수를 찾는다.

• 이때, 각 쌍은 연속적으로 나오지 않으므로 반복문을 역으로 돌리면서 작은 값을 누적해간다.
• 이 결과로 첫 번째 수가 세 번째 수보다 큰 경우만을 정리했다.

 

2. 첫 번째 수보다 큰 수를 찾아 해당 경우의 수를 누적한다.

for(int i = 1 ; i <= n ; i++)
    for(int j = i + 1 ; j <= n - 1  ; j++)
        if(v[i] < v[j]) answer += stack[v[i]][j];

• 앞서 첫 번째 수가 세 번째 수보다 큰 경우를 찾았으니 첫 번째 수 보다 큰 두 번째 수의 경우 만을 찾으면 된다.
• 위 코드에서 i 는 첫 번째 숫자의 인덱스, j는 두번째 숫자의 인덱스다.
• 첫 번째 숫자는 처음 인덱스부터 존재할 수 있으니 1부터 찾는다.
• 두 번째 숫자는 첫 번째 인덱스와 마지막 인덱스에 존재할 수 없으니 해당 범위를 제외하고 찾는다.
• 이때 첫 번째 숫자보다 두 번째 숫자가 커야한다. 이 경우 만을 찾는다.
• 이 경우에 (1.)의 결과에서 누적해온 값을 더하면 끝.

---

열 받은 점

솔직히 이런 부분도 고려했어야 했는데...

파이썬으로 똑같이 코드를 짜면 분명 풀리는데 자바로 하면 이상하게 틀린다 싶었다.

코드 비교도 계속하고 조금씩 구조를 바꿔봐도 고정적으로 틀리더라.

 

그래서 혹시나 정수 오버플로우나서 그런가 싶었다. 

근데 long으로 누적 값을 저장하는 변수 바꿔주니까 풀리더라.

 

이런 경우도 있구나 싶었다.

나는 아직 멀었다.