[BOJ] 백준 14428번 : 수열과 쿼리 16 (JAVA)

문제

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

 

• 1 i v : Ai를 v로 바꾼다.
• 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값의 인덱스를 출력한다. 그러한 값이 여러개인 경우에는 인덱스가 작은 것을 출력한다.

 

수열의 인덱스는 1부터 시작한다.

 

 

입력

첫째 줄에 수열의 크기 N이 주어진다. (1 ≤ N ≤ 100,000)

둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109)

셋째 줄에는 쿼리의 개수 M이 주어진다. (1 ≤ M ≤ 100,000)

넷째 줄부터 M개의 줄에는 쿼리가 주어진다.

 

 

출력

2번 쿼리에 대해서 정답을 한 줄에 하나씩 순서대로 출력한다.

 

 

풀이

세그먼트 트리를 이용하여 풀 수 있는 문제였습니다.

 

특히, '10868번 최솟값' 문제를 응용해야했습니다. 이 문제에 대해 아직 안 풀어보신 분은 아래 링크를 정독하시길 바랍니다.

 

 

[BOJ] 백준 10868번 : 최솟값 (JAVA)

 

 

위 로직을 사용하면, 각 구간 별로 최솟값을 저장하게 됩니다.

하지만, 이번 문제에서는 최솟값이 아닌, 최솟값의 '인덱스'를 저장해야하는 것이 큰 차이점이었습니다.

 

최솟값의 인덱스를 저장하는 방법은 그렇게 어렵지는 않습니다.

먼저, init 메소드에서 각 구간 별로 최솟값의 인덱스를 저장하도록 설계합니다.

이렇게 하기 위해서는 리프 노드에는 arr의 인덱스가 들어가야합니다.

 

리프 노드에 원래 arr의 인덱스가 순차적으로 들어갔으면, 그 위 노드부터는 아래 노드 2개 중의 더 작은 최솟값의 인덱스를 저장하게끔 만들어 주면 됩니다.

 

이를 코드로 표현하면 다음과 같습니다.

 

 

 

 

위 과정을 완료했다면, 각 구간 별로 최솟값의 인덱스가 잘 저장되어 있을 것입니다.

이제, query 메소드와 update 메소드를 정의해 봅시다.

 

1) query

query 메소드는 특정 구간 내의 최솟값의 인덱스를 반환하는 메소드입니다.

이렇게 하기 위해서는 메소드 안에 변수 2개를 정의하여, arr[tree[node * 2]] 와 arr[tree[node * 2 + 1]] 중에 무엇이 더 작은지 따져보아야 합니다.

 

위 내용은 말 보다는 코드로 보는 것이 이해가 더 빠를 것 같습니다.

 

 

 

 

2) update

arr[i] = v로 바꾸는 메소드입니다. i번째 인덱스에서 값의 변화가 일어나면, tree의 리프 노드 중 인덱스 i에 해당하는 부분을 찾고, 그 리프 노드와 관련된 가지 전체를 업데이트 해 주어야 합니다.

 

따라서, 리프노드를 찾아서 tree[node] = i, arr[i] = v로 바꿔준 뒤, 그 위의 노드에 대하여 새롭게 최솟값의 인덱스를 저장하게끔 만들면 됩니다.

 

 

 

 

 

아래는 위 과정을 정리한 전체 소스코드입니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.