์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- ํญํด99
- ๋ฐ์ดํฐ ์ ์ก
- ์ฐ๋ถํฌdb
- well known ํฌํธ
- git merge
- ๊ฐ๋ฐ์์ทจ์
- ์ค๋ฅ๊ฒ์ถ
- 99ํด๋ฝ
- tcp ํ๋กํ ์ฝ
- ์ฃผ๊ธฐ์ ํธ
- leetcode
- til
- ์์๋ฒํธ
- i-type
- xv6
- ์๋น์ค ํ๋ฆฌ๋ฏธํฐ๋ธ
- mariadb
- ํ๋ ์ ๊ตฌ์กฐ
- ํ๋ก์ด๋์์
- ์ค๋ฅ์ ์ด
- tcp ์ธ๊ทธ๋จผํธ
- ํ ํฐ ๋ฒ์ค
- ์ฝ๋ฉํ ์คํธ์ค๋น
- reducible
- IEEE 802
- ์ค๋ธ์
- ๋น์ฃผ๊ธฐ์ ํธ
- ํฐ์คํ ๋ฆฌ์ฑ๋ฆฐ์ง
- ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ
- ์ค๋ ๋
Archives
- Today
- Total
Unfazedโ๏ธ๐ฏ
[Java] ์ ๋ ฌ, ๊ทธ๋ฆฌ๋ | ๋ฐฑ์ค 1083 ์ํธ ๋ณธ๋ฌธ
๋ฌธ์ ํด๊ฒฐ (PS)/์ฝํ
TIL
[Java] ์ ๋ ฌ, ๊ทธ๋ฆฌ๋ | ๋ฐฑ์ค 1083 ์ํธ
9taetae9 2024. 11. 17. 10:15728x90
https://www.acmicpc.net/problem/1083

์ ๊ทผ ๋ฐฉ๋ฒ :
๊ทธ๋ฆฌ๋ํ๊ฒ ๊ฐ ์์น์์ ํ์ฌ ๋ฒ์ ๋ด ๊ฐ์ฅ ํฐ ๊ฐ์ ์์ผ๋ก ์ด๋์ํจ๋ค.
- S์ ์ ํ ๋๋ฌธ์, ๊ฐ๋ฅํ ๊ตํ ํ์(j - i <= S)๋ฅผ ๊ณ ๋ คํด์ฃผ์ด์ผ ํ๋ค.
๋ ์์ ๊ตํ ๊ณผ์ :
- ํ์ฌ ์์น i ์์ i+1๋ถํฐ i+S๋ฒ์ ๋ด์์ ๊ฐ์ฅ ํฐ ๊ฐ์ ์ฐพ๋๋ค.
- ํด๋น ๊ฐ์ i๋ก ์ด๋์ํค๊ธฐ ์ํด ์ธ์ ์์ ๊ฐ ๊ตํ์ ๋ฐ๋ณตํ๋ค. (๋ฒ๋ธ ์ํธ์ ์ ์ฌ)
- ๊ฐ์ ์ด๋ ์ํค๋ ๋ฐ ์ฌ์ฉํ ๊ตํ ํ์๋งํผ S๋ฅผ ๊ฐ์์ํจ๋ค.
์ข ๋ฃ ์กฐ๊ฑด : S๊ฐ 0์ด ๋๊ฑฐ๋, ๋ฐฐ์ด์ ๋๊น์ง ํ์ํ์ ๊ฒฝ์ฐ ์ข ๋ฃ
ํต์ฌ ์ฝ๋
S ์ ํ ๋ด์์ ๊ฐ์ฅ ์ผ์ชฝ ์๋ฆฌ๋ถํฐ ์ต๋ ๊ฐ์ผ๋ก ์ฑ์์ฃผ๋ ๊ฒ์ ์ง์คํ๋ค.
๋งค ๋ฐ๋ณต ๋ง๋ค S-=(maxIndex - i); ๋ก ๊ตํํ ํ์๋งํผ S๋ฅผ ๊ฐ์์์ผ์ค๋ค.
private static void solve(){
for(int i=0; i<N; i++){
int maxIndex = i;
for(int j=i+1; j<N && j-i<=S; j++){
if(list.get(maxIndex) < list.get(j)){
maxIndex = j;
}
}
for(int j=maxIndex; j>i; j--){
Collections.swap(list, j, j-1);
}
S -= (maxIndex - i);
}
printList();
}
์ ์ฒด ์ฝ๋
public class BOJ1083 {
static List<Integer> list;
static int N,S;
public static void main(String[] args) throws Exception {
init();
solve();
}
private static void solve(){
for(int i=0; i<N; i++){
int maxIndex = i;
for(int j=i+1; j<N && j-i<=S; j++){
if(list.get(maxIndex) < list.get(j)){
maxIndex = j;
}
}
for(int j=maxIndex; j>i; j--){
Collections.swap(list, j, j-1);
}
S -= (maxIndex - i);
}
printList();
}
private static void printList(){
for(int e : list){
System.out.print(e+" ");
}
}
private static void init() throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
list = new ArrayList<>();
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=0; i<N; i++){
list.add(Integer.parseInt(st.nextToken()));
}
S = Integer.parseInt(br.readLine());
}
}
728x90
'๋ฌธ์ ํด๊ฒฐ (PS) > ์ฝํ TIL' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Java] ํธ๋ฆฌ, ์ฌ๊ท | LeetCode 226 Invert Binary Tree (๊ท๋ฉ์ ์ผ๋ก ์๊ฐํ๊ธฐ) (0) | 2025.02.12 |
---|---|
[Java] ๋ค์ต์คํธ๋ผ, BFS | ๋ฐฑ์ค 2665 ๋ฏธ๋ก๋ง๋ค๊ธฐ (0) | 2024.11.11 |
[Java] ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ, ์ ๋ ฌ | ๋ฐฑ์ค 1461 ๋์๊ด (0) | 2024.11.07 |
[Java] ํฌํฌ์ธํฐ | ๋ฐฑ์ค 1253 ์ข๋ค (0) | 2024.11.07 |
[Java] ํธ๋ฆฌ, ๊ตฌํ | ํ๋ก๊ทธ๋๋จธ์ค ๋ค๋จ๊ณ ์นซ์ ํ๋งค (0) | 2024.11.06 |