-
728x90๋ฐ์ํ
์์ฒญ ๋ ์ง : 11/12/2021
์์ฒญ ๊ฐ์ : ๋ค์ํ ์ ๋ ฌ ์์ฉ๋ฒ - ์์ฉ ํธhttps://junebee.tistory.com/18 ์ ์ด์ด, ์ ๋ ฌ ์์ฉ๋ฌธ์ ๊ฐ์๋ฅผ ๋ค์๋ค.
์์ด ์ ๋ ฌ https://www.acmicpc.net/problem/1015 ์นด๋ https://www.acmicpc.net/problem/11652 ํ์ดํ ๊ทธ๋ฆฌ๊ธฐ https://www.acmicpc.net/problem/15970 ์ ๋ฌธ์ ๋ฅผ ํ์ดํด๋ดค๋ค. ํ์ดํ ๊ทธ๋ฆฌ๊ธฐ๋ ์๊ฐ์ด ์์ด์ ์์ง ํ์ง ๋ชปํ๋ค. ํ์ ์๊ฐ์ด ๋๋ฉด ์ถ๊ฐ์ ์ผ๋ก ์ ๋ก๋ํ๊ฒ ๋ค.
์์ด ์ ๋ ฌ
๋ฌธ์ ํด์
์ฃผ์ด์ง ๋ฐฐ์ด๊ณผ ํด๋น ์์์ ์ธ๋ฑ์ค๋ฅผ ๋ฐ๋ก ์ ์ฅํ๋ค.
[Original Array]
index 0 1 2 3 4 5 element 5 4 1 3 5 7 ์ ๋ฐฐ์ด์ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌํ๊ฒ ๋๋ฉด ์๋์ ๊ฐ๋ค,
[Sorted Array]
index 0 1 2 3 4 5 element 1 3 4 5 5 7 ์ด์ , ์๋ณธ ๋ฐฐ์ด์ element๊ฐ ์ ๋ ฌ๋ ๋ฐฐ์ด์์ ๋ช ๋ฒ์งธ์ธ์ง ์ถ๋ ฅํ๋ฉด ๋๋ค.
์์ ๋งค์นญ ํ๋ ๋ฐฉ๋ฒ์ ๊ทธ๋ ค๋ณด์๋ค. ์ ๋ฌธ์ ์ ๊ฒฝ์ฐ๋ 3 2 0 1 4 5๋ฅผ ์ถ๋ ฅํ๊ฒ ๋๋ค.
๋ฌธ์ ํ์ด
๋๋ ๋ฐฐ์ด์ ๋ ๊ฐ ์ด์ฉํ์ฌ ์ ๋ฌธ์ ๋ฅผ ํ์๋ค. ์๋ณธ ๋ฐฐ์ด๊ณผ ์ ๋ ฌํ ๋ฐฐ์ด์ ๋ฐ๋ก ๋ง๋ค์๋๋ฐ, ์์์ ๋ด๊ฐ ํด์ํ ๊ณผ์ ์ ๊ทธ๋๋ก ์ฝ๋๋ก ์ง ํ์ด๋ค.
์๊ณ ๋ฆฌ์ฆ
1. ์๋ณธ ๋ฐฐ์ด๊ณผ ์ ๋ ฌํ ๋ฐฐ์ด์ ์ ๋ ฅ๊ฐ์ ๋ฐ์
2. ์ ๋ ฌํ ๋ฐฐ์ด์ ์ ๋ ฌํจ
3. For loop๋ฅผ ์ฌ์ฉํ์ฌ, ์๋ณธ ๋ฐฐ์ด์ ์์๋ฅผ ์ ๋ ฌ๋ ๋ฐฐ์ด์์ ์ฐพ์ ํ์ ์ ๋ ฌ๋ index๋ฅผ ํ๋ฆฐํธํ๊ณ ๋ค์ ์์๋ฅผ ์ ๋ ฌ๋ ๋ฐฐ์ด์์ ์ฐพ์์ index๋ฅผ ํ๋ฆฐํธํ๋ค.
4. 3๋ฒ์ N๋ฒ๋งํผ ๋ฐ๋ณต
์ฃผ์์ฌํญ
- ๋ง์ฝ, ์ ๋ ฌ๋ ๋ฐฐ์ด์์ ํ์ฌ ์์์ ๊ฐ์ ๊ฐ์ ์ฐพ์๋ค๋ฉด, ๊ทธ ๊ฐ์ ์์๋ก ๋ณ๊ฒฝํด ์ฃผ์๋ค - ๋ง์ฝ, ๋ฐฐ์ด์ ๊ฐ์ ๊ฐ์ด ์์ ๊ฒฝ์ฐ ๊ณ์ ์์ ์ ๋ ฌ๋ ์์๋ฅผ ์ฐพ๋ ๊ฒ์ ๋ฐฉ์งํ๊ธฐ ์ํจ
- ์์๋ฅผ ์ฐพ์ ํ์๋ break ํด์ค์ผ ๋ค์ ์์๋ฅผ ์ฐพ๋๋ค.๊ตฌํ
1. ์ ๋ ฅ
for(int i = 0 ; i < N ; i++) { int num = Integer.parseInt(st.nextToken()); list[i] =compare[i] = num; }
- list : ์๋ณธ ๋ฐฐ์ด
- compare : ์ ๋ ฌํ ๋ฐฐ์ด
2. ์ ๋ ฌ
Arrays.sort(list);
3. ์๋ณธ ๋ฐฐ์ด์ ์ ๋ ฌ๋ ์ธ๋ฑ์ค ๊ฐ ์ฐพ๊ธฐ
for(int i = 0 ; i < N ; i++) { //์๋ณธ ๋ฐฐ์ด์ ๋๋ฆฐ๋ค for(int j =0 ; j<N ; j ++) { //์ ๋ ฌ๋ ๋ฐฐ์ด์ ๋๋ฆฐ๋ค if(compare[i]== list[j]) { //์๋ณธ๋ฐฐ์ด์ ์์๋ฅผ ์ ๋ ฌ๋ ๋ฐฐ์ด์์ ์ฐพ์ผ๋ฉด bw.write(j+" ");//์ ๋ ฌ๋ ์ธ๋ฑ์ค๋ฅผ ํ๋ฆฐํธ list[j] = -20;//์์๊ฐ์ ๋ฃ์ด์ฃผ์ด์ ๊ฐ์ ์์๊ฐ์ด ์์ ๋ ์ค๋ณต๋ ์ธ๋ฑ์ค๋ฅผ ์ฃผ๋ ๊ฒ์ ๋ฐฉ์ง break;//์ฐพ์ ํ ๋ค์ ์์๋ก } }
์ ์ฒด ์์ค ์ฝ๋
package com.fastcamp.sort; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.Arrays; import java.util.StringTokenizer; /** * @author June Park * @date 11/12/2021 * ์์ด ์ ๋ ฌ * input * line 1 - ๋ฐฐ์ด์ ํฌ๊ธฐ N * line 2 - ๋ฐฐ์ด์ ์์ * Problem * ๋น๋ด๋ฆผ์ฐจ์์ด๋๋ ์์ด์ ์ฐพ๋๋ค (์ค๋ฆ์ฐจ์, ascending) - print index not elements * */ public class BOJ_1015_์์ด์ ๋ ฌ { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int N = Integer.parseInt(br.readLine()); int[] compare = new int[N]; int[] list = new int[N]; StringTokenizer st = new StringTokenizer(br.readLine()); br.close(); for(int i = 0 ; i < N ; i++) { int num = Integer.parseInt(st.nextToken()); list[i] =compare[i] = num; } //sort list array and keep the input array as unsorted Arrays.sort(list); for(int i = 0 ; i < N ; i++) { for(int j =0 ; j<N ; j ++) { if(compare[i]== list[j]) { //if you find original element in sorted array bw.write(j+" "); //print out the index from sorted array list[j] = -20; //put negative number to sorted array to avoid searching for same index when there is same number break; //escape from the for loop and search for next element } } }//end of for bw.flush(); bw.close(); } }
์นด๋
๋ฐํ์ ์๋ฌ ๋๋ฌธ์ ์ ๋ง ๋ง์ ํ์ด๋ฅผ ์๋ํด๋ณด์๋ค.
๋ฆฌ์คํธ๋ ์จ๋ณด๊ณ , ๋ฐฐ์ด๋ ์จ๋ณด๊ณ ํธ๋ฆฌ ๋งต๋ ์จ๋ณด์๋๋ฐ ํด์ฌ ๋งต์ ์ฌ์ฉํ ์ฝ๋๊ฐ ๊ฐ์ฅ ์งง๊ณ ์ถ๊ฐ์ ์ผ๋ก ๊ตฌํํ ๋ถ๋ถ์ด ์์๋ค.
๋ฌธ์ ํด์
Mode๋ฅผ ๊ตฌํ๋ ๋ฌธ์ ๋ค.
HashMap
HashMap ๊ตฌ์กฐ๋ฅผ ์ฌ์ฉํ๋ฉด, ์ซ์๋ฅผ key๋ก ์ ์ฅํ๊ณ value์ ์ซ์๊ฐ ์ฌ์ฉ๋ ํ์๋ฅผ ์ ์ฅํ๋ค.
์ ๋ ฅ์ ๋ฐ์ ๋, ๋ง์ฝ ์ด๋ฏธ ์ด์ ์ ์ซ์๊ฐ ๋์๋ค๋ฉด value์ ์ด์ ๊ฐ์ 1์ ๋ํด์ฃผ๋ฉด count ํ ์ ์๋ค.
Map<Long,Integer> numbers = new HashMap<>(); //๋ฆฌ์คํธ ํํ๋ก ๊ฐ์ ธ์ค๊ธฐ ์ํด Map ์ฌ์ฉ for(int n = 0 ; n< N ; n++) { long num = Long.parseLong(br.readLine()); if(numbers.containsKey(num)) { numbers.put(num, numbers.get(num)+1);//override } else {numbers.put(num, 1);} }
๋ง์ฝ ํด์ฌ ๋งต์ ํ์ฌ ๋ฐ์ ์ซ์๊ฐ ์๋ค๋ฉด value์ 1์ ์ค๋ค(count ๊ฐ์ด๋ฏ๋ก)
[์ฃผ์] ์ซ์๋ intํ์ด ์๋ long ๊ฐ์ผ๋ก ๋ฐ์์ผ ํ๋ค! ๋ฐํ์ ์๋ฌ(Number format)์ ์ฃผ์ ๋ฒ์ธ์ด๋ค.. N (1 ≤ N ≤ 100,000)์ผ๋ก ์ฃผ์ด ์ ์๊ธฐ ๋๋ฌธ์ long์ผ๋ก ๋ฐ์์ผ ํ๋ค.
HashMap ์ ๋ ฌ
1. ์ ์ธ
HashMap์ ์ ๋ ฌํ๊ธฐ ์ํด ์จ๊ฐ ๊ตฌ๊ธ์ ๋ค ์ ๋ณด์๋ค. ์ ๋ฆฌํ์๋ฉด, HashMap์ ์ ๋ ฌํ๋ ค๋ฉด ๋จผ์
HashMap<์๋ฃ๊ตฌ์กฐ,์๋ฃ๊ตฌ์กฐ> map = new HashMap<์๋ฃ๊ตฌ์กฐ, ์๋ฃ๊ตฌ์กฐ>();
์ด ์๋
Map<์๋ฃ๊ตฌ์กฐ,์๋ฃ๊ตฌ์กฐ> map = new HashMap<์๋ฃ๊ตฌ์กฐ, ์๋ฃ๊ตฌ์กฐ>();
์ ์ฌ์ฉํด์ผ ํ๋ค
์ด์ ๋, ํด์ฌ ๋งต์ ์ ๋ ฌํ๊ธฐ ์ํด์๋ ๋ฆฌ์คํธ ํํ๋ก ๊ฐ์ ธ์์ผ ํ๊ธฐ ๋๋ฌธ์ด๋ค!
2. ๋ฆฌ์คํธ๋ก ์ ํ
ํด์ฌ๋งต์ ๋ฆฌ์คํธ๋ก ์ ์ฅํ๊ธฐ ์ํด์ EntrySet์ ์ฌ์ฉํ๋ค.
๋ฐฉ๋ฒ์ ์๋์ ๊ฐ๋ค. ํด์ฌ ๋งต์ key์ value๋ฅผ ๋ฆฌ์คํธ๋ก ์ ์ฅํ๋ ๊ฒ์ด๋ค.
List<Map.Entry<Long,Integer>>entry = new LinkedList<>(numbers.entrySet());
3. ์ ๋ ฌ
entry.sort(new Comparator< Map.Entry<Long, Integer>>(){ @Override public int compare(Entry<Long, Integer> o1, Entry<Long, Integer> o2) { if(o1.getValue().intValue()==o2.getValue().intValue()) return Long.compare(o1.getKey().longValue(), o2.getKey().longValue()); return o2.getValue()-o1.getValue(); } });
์ ๋ ฌ์ Comparator์ ์ฌ์ฉํ๋ค. count๊ฐ(value)์ด ๋ง์ด ์ฌ์ฉ๋ ํค๊ฐ์ ๊ตฌํด์ผ ํ๊ธฐ ๋๋ฌธ์ด๋ค.
๋, ํ์ฐธ์ ํค๋งค๋ค๊ฐ ์ฌ๋ฌ ์ฌ๋๋ค์ ํ์ด๋ฅผ ๋ดค๋๋ฐ, if ์กฐ๊ฑด์ ์ฃผ์ง ์์ผ๋ฉด ํ๋ฆฐ๋ค.
ํ ์คํธ ์ผ์ด์ค๋ก ์ํํด๋ดค์ ๋๋ if๋ฌธ์ด ์์ผ๋ ์์ผ๋ ๊ฒฐ๊ณผ๊ฐ ์๋ง๊ฒ ๋์์ ์๊ฐ์ ์ ํ๋๋ฐ ๊ฐ์ด ์์์ผ ๋๋ฅผ ๋ฐ๋ก๋ก ์ค๋ณด๋ฉด,
4 -5 -5 -2 -2
์ ํ ์คํธ ๊ฒฝ์ฐ, -5๊ฐ -2๋ณด๋ค ์๊ธฐ ๋๋ฌธ์ -5๊ฐ ๋์์ผ ํ์ง๋ง if ๋ฌธ์ด ์๋ค๋ฉด -2๊ฐ ์ถ๋ ฅ๋๋ ๊ฒ์ ํ์ธํด๋ณผ ์ ์๋ค.
๋ง์ง๋ง์ผ๋ก,
entry.get(0).getKey()
์ผ๋ก count ๊ฐ ๋ด๋ฆผ์ฐจ์์ผ๋ก ์ ๋ ฌ๋ entry๋ฆฌ์คํธ์ 0๋ฒ์งธ ์์์ ํค๊ฐ์ ๊ฐ์ ธ์ค๋ฉด ๊ฐ์ฅ ๋ง์ด ์ฌ์ฉ๋ ์ซ์๋ฅผ ๋ณผ ์ ์๋ค.
์ ์ฒด ์์ค ์ฝ๋
package com.fastcamp.sort; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Collections; import java.util.Comparator; import java.util.HashMap; import java.util.LinkedList; import java.util.List; import java.util.Map; import java.util.Map.Entry; public class BOJ_11652_์นด๋ { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); //BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int N = Integer.parseInt(br.readLine()); Map<Long,Integer> numbers = new HashMap<>(); //๋ฆฌ์คํธ ํํ๋ก ๊ฐ์ ธ์ค๊ธฐ ์ํด Map ์ฌ์ฉ for(int n = 0 ; n< N ; n++) { long num = Long.parseLong(br.readLine()); if(numbers.containsKey(num)) { numbers.put(num, numbers.get(num)+1);//override } else {numbers.put(num, 1);} } br.close(); //sort //๋ฆฌ์คํธ ํํ๋ก ๊ฐ์ ธ์ด List<Map.Entry<Long,Integer>>entry = new LinkedList<>(numbers.entrySet()); //sort entry.sort(new Comparator< Map.Entry<Long, Integer>>(){ @Override public int compare(Entry<Long, Integer> o1, Entry<Long, Integer> o2) { if(o1.getValue().intValue()==o2.getValue().intValue()) //๊ฐ์ ๋ return Long.compare(o1.getKey().longValue(), o2.getKey().longValue()); return o2.getValue()-o1.getValue(); } }); System.out.println(entry.get(0).getKey()); } }
ํจ์คํธ์บ ํผ์ค ํ๊ธ ์ฑ๋ฆฐ์ง ๋ฐ๋ก๊ฐ๊ธฐ๐ https://bit.ly/3FVdhDa
์๊ฐ๋ฃ 100% ํ๊ธ ์ฑ๋ฆฐ์ง | ํจ์คํธ์บ ํผ์ค
๋ฑ 5์ผ๊ฐ ์งํ๋๋ ํ๊ธ์ฑ๋ฆฐ์ง๋ก ์๊ฐ๋ฃ 100% ํ๊ธ๋ฐ์ผ์ธ์! ๋ ๋ฆ๊ธฐ์ ์ ์๊ธฐ๊ณ๋ฐ ๋ง์ฐจ ํ์น!
fastcampus.co.kr
๋ณธ ํฌ์คํ ์ ํจ์คํธ์บ ํผ์ค ํ๊ธ ์ฑ๋ฆฐ์ง ์ฐธ์ฌ๋ฅผ ์ํด ์์ฑ๋์์ต๋๋ค.
728x90๋ฐ์ํ'๐ STUDY > FASTCAMPUS' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
ํจ์คํธ์บ ํผ์ค ์ฑ๋ฆฐ์ง 14์ผ์ฐจ (0) 2021.11.14 ํจ์คํธ์บ ํผ์ค ์ฑ๋ฆฐ์ง 13์ผ์ฐจ (0) 2021.11.13 ํจ์คํธ์บ ํผ์ค ์ฑ๋ฆฐ์ง 11์ผ์ฐจ (0) 2021.11.11 ํจ์คํธ์บ ํผ์ค ์ฑ๋ฆฐ์ง 10์ผ์ฐจ (0) 2021.11.10 ํจ์คํธ์บ ํผ์ค ์ฑ๋ฆฐ์ง 9์ผ์ฐจ (0) 2021.11.09 ๋๊ธ