๊ตญ๋ฏผ๋ํ๊ต์์๋ ๋งค ํ๊ธฐ ์์ ์ ์ข ํฉ์ ๋ณด์์คํ ์์ ์๊ฐ์ ์ฒญ์ ํ๋ค. ๋งค ์๊ฐ์ ์ฒญ๋ง๋ค ์์ฃผ ๋ง์ ํ์๋ค์ด ๋ชฐ๋ ค ์๋ฒ์ ๋ง์ ๋ถํ๊ฐ ๊ฐ๊ธฐ ๋๋ฌธ์, ๊ตญ๋ฏผ๋ํ๊ต์์๋ ์๊ฐ์ ์ฒญ ๋ถํ ๊ด๋ฆฌ ์์คํ ์ ๋์ ํ๊ธฐ๋ก ๊ฒฐ์ ํ์๋ค. ์๋ก์ด ๊ด๋ฆฌ ์์คํ ์ ๋ค์๊ณผ ๊ฐ์ ๋ฐฉ์์ผ๋ก ๋์ํ๋ค.
์๊ฐ์ ์ฒญ ๋ฒํผ์ด ํ์ฑํ ๋ ํ, ์๊ฐ์ ์ฒญ ๋ฒํผ์ ์กฐ๊ธ์ด๋ผ๋ ๋นจ๋ฆฌ ๋๋ฅธ ํ์์ด ๋๊ธฐ๋ชฉ๋ก์ ๋จผ์ ๋ค์ด๊ฐ๋ค.
์ด๋ฏธ ๋๊ธฐ์ด์ ๋ค์ด๊ฐ ์๋ ์ํ์์ ๋ค์ ์๊ฐ์ ์ฒญ ๋ฒํผ์ ๋๋ฅผ ๊ฒฝ์ฐ ๋๊ธฐ๋ชฉ๋ก์ ๋งจ ๋ค๋ก ๋ฐ๋ ค๋๋ค.
์ ์ ํ ์๊ฐ์ ์ฒญ ๋ฒํผ์ด ๋นํ์ฑํ ๋๋ฉด, ๋๊ธฐ๋ชฉ๋ก์์ ๊ฐ์ฅ ์์ ์๋ ํ์๋ถํฐ ์๋์ผ๋ก ์๊ฐ์ ์ฒญ์ด ์๋ฃ๋๋ฉฐ, ์๊ฐ ๊ฐ๋ฅ ์ธ์์ด ๊ฝ ์ฐฐ ๊ฒฝ์ฐ ๋๋จธ์ง ๋๊ธฐ๋ชฉ๋ก์ ๋ฌด์ํ๊ณ ์๊ฐ์ ์ฒญ์ ์ข ๋ฃํ๋ค.
์์ ํ๋ ์ต๋ ์๊ฐ ๊ฐ๋ฅ ์ธ์์ด 3๋ช ์ธ ์๊ณ ๋ฆฌ์ฆ ์์ ์ ๋ํด 6๋ช ์ ํ์์ด ์๊ฐ์ ์ฒญ์ ์งํํ ๋ชจ์ต์ด๋ค. ๋ฒํผ์ด ๋นํ์ฑํ ๋ ํ, ๋จผ์ ๊ท์น 1์ ์ ์ฉํ์ฌ ํด๋ฆญ์ 2๋ฒ ์ด์ ํ ํ์์ ์ค๋ณต๋ ๋๊ธฐ๋ชฉ๋ก์ ์ญ์ ํ๋ค. ์ค๋ณต๋ ๋ชฉ๋ก์ ์ ๊ฑฐํ ํ, ๋งจ ์์์๋ถํฐ ์ต๋ ์๊ฐ ๊ฐ๋ฅ ์ธ์์ธ 3๋ช ์ ์ ์ ํ๋ค. ํ์ ๋งจ ์ค๋ฅธ์ชฝ์๋ ๊ทธ ์ต์ข ๊ฒฐ๊ณผ๋ฅผ ๋ํ๋ธ ๋ชจ์ต์ด๋ค. ์ด์ ๊ฐ์ ๋ฐฉ๋ฒ์ ์ด์ฉํ์ฌ ์ต์ข ์ ์ผ๋ก ์๊ฐ์ ์ฒญ์ ์ฑ๊ณตํ ์ธ์์ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ ๋ ฅ ๋ฐ์ดํฐ๋ ํ์ค ์ ๋ ฅ์ ์ฌ์ฉํ๋ค. ์ ๋ ฅ์ 1๊ฐ์ ํ ์คํธ ๋ฐ์ดํฐ๋ก ๊ตฌ์ฑ๋๋ค. ์ ๋ ฅ์ ์ฒซ ๋ฒ์งธ ์ค์๋ ๊ณผ๋ชฉ์ ์๊ฐ ๊ฐ๋ฅ ์ธ์ K(1 โค K โค 100,000)์ ํ์๋ค์ด ๋ฒํผ์ ํด๋ฆญํ ์์๋ฅผ ๊ธฐ๋กํ ๋๊ธฐ๋ชฉ๋ก์ ๊ธธ์ด L(1 โค L โค 500,000)์ด ์ฃผ์ด์ง๋ค. ๋ ๋ฒ์งธ ์ค๋ถํฐ L๊ฐ์ ์ค์๋ ์๊ฐ์ ์ฒญ์ ๋ฒํผ์ ํด๋ฆญํ ํ์์ ํ๋ฒ์ด ํด๋ฆญ ์์๋๋ก ์ฃผ์ด์ง๋ค. ํ๋ฒ์ 8์๋ฆฌ์ ์ซ์๋ก ์ด๋ฃจ์ด์ ธ ์๋ค.
์ถ๋ ฅ
์ถ๋ ฅ์ ํ์ค ์ถ๋ ฅ์ ์ฌ์ฉํ๋ค. ์ ๋ ฅ๋ฐ์ ๋ฐ์ดํฐ์ ๋ํด, ์๊ฐ์ ์ฒญ ๊ด๋ฆฌ ์์คํ ์ ๊ท์น์ ์ ์ฉํ ํ ์๊ฐ์ ์ฒญ์ ์ฑ๊ณตํ ์ธ์์ ํ๋ฒ์ ํ ์ค์ 1๊ฐ์ฉ ์ถ๋ ฅํ๋ค.
๐ก LinkedHashSet ์ด์ฉ
๐ก ํ๋ฒ์ด ๊ธฐ์กด์ ์์ผ๋ฉด ๋บ ๋ค์์ ๋งจ ๋ค์๋ค๊ฐ ๋ค์ ๋ฃ์
1) LinkedHashSet ์ด์ฉ
LinkedHashSet<String> set = new LinkedHashSet<>();
2) ํ๋ฒ์ด ๊ธฐ์กด์ ์์ผ๋ฉด ๋บ ๋ค์์ ๋งจ ๋ค์๋ค๊ฐ ๋ค์ ๋ฃ์
if(set.contains(num))
set.remove(num);
set.add(num);
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedHashSet;
public class Hash_9 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] s = br.readLine().split(" ");
int k = Integer.parseInt(s[0]);
int l = Integer.parseInt(s[1]);
LinkedHashSet<String> set = new LinkedHashSet<>();
for(int i=0; i<l; i++) {
String num = br.readLine();
if(set.contains(num)) set.remove(num);
set.add(num);
}
for(String ret : set) {
if(k <= 0)
break;
bw.write(ret);
bw.write("\n");
k--;
}
bw.flush();
bw.close();
}
}
์ฑ๊ณตโจ