๐ ํ๋ก๊ทธ๋๋จธ์ค / ์ฐ์ต๋ฌธ์ / Level 2 / ๋กค์ผ์ดํฌ ์๋ฅด๊ธฐ
๐ ๋ฌธ์
ํ๋ก๊ทธ๋๋จธ์ค
์ฝ๋ ์ค์ฌ์ ๊ฐ๋ฐ์ ์ฑ์ฉ. ์คํ ๊ธฐ๋ฐ์ ํฌ์ง์ ๋งค์นญ. ํ๋ก๊ทธ๋๋จธ์ค์ ๊ฐ๋ฐ์ ๋ง์ถคํ ํ๋กํ์ ๋ฑ๋กํ๊ณ , ๋์ ๊ธฐ์ ๊ถํฉ์ด ์ ๋ง๋ ๊ธฐ์ ๋ค์ ๋งค์นญ ๋ฐ์ผ์ธ์.
programmers.co.kr
๐ซ ์ ํ ์ฌํญ
- 1 ≤ topping์ ๊ธธ์ด ≤ 1,000,000
- 1 ≤ topping์ ์์ ≤ 10,000
๐ ์ ์ถ๋ ฅ ์
| topping | result |
| [1, 2, 1, 3, 1, 4, 1, 2] | 2 |
| [1, 2, 3, 1, 4] | 0 |
๐ค ํ์ด ๋ฐฉ๋ฒ
1๏ธโฃ ๋ฐฐ์ด
โ ๊ธฐ๋ณธ ์์ด๋์ด
(1) ๋ฐฐ์ด ์์ฑ
โก๏ธ ์ฃผ์ด์ง topping ๋ฐฐ์ด์ ์ข์์ ์ฐ๋ก ํ ๋ฒ & ์ฐ์์ ์ข๋ก ํ ๋ฒ ํ์ํ๋ฉฐ, ํ ํ์ ์ข ๋ฅ์ ๊ฐ์๋ฅผ ๊ธฐ๋กํ ๋ฐฐ์ด์ ๋ง๋ ๋ค.
ex) ์ ์ถ๋ ฅ ์ 1 ์ ๊ฒฝ์ฐ : [1, 2, 1, 3, 1, 4, 1, 2]
โ ์ข โก๏ธ ์ฐ [1, 2, 2, 3, 3, 4, 4, 4]
โก ์ฐ โก๏ธ ์ข [4, 4, 4, 4, 3, 3, 2, 1]
โก๏ธ ์ด ๋, ๊ฐ ๋ฐฉํฅ๋ง๋ค ์ด๋ฏธ ์๋ ํ ํ์ธ์ง ํ์ธํ๋ ๋ฐฐ์ด๊ณผ ํ ํ ์ข ๋ฅ์ ๊ฐ์๋ฅผ ์ ์ฅํ๋ ๋ฐฐ์ด์ด ํ์ํ๋ค. (์ด 4๊ฐ์ ๋ฐฐ์ด ์์ฑ)
// boolean ๋ฐฐ์ด ์์ฑ (ํ ํ ์กด์ฌ ํ์ธ)
boolean[] ltrCheck = new boolean[max];
boolean[] rtlCheck = new boolean[max];
// int ๋ฐฐ์ด ์์ฑ (ํ ํ ์ข
๋ฅ์ ๊ฐ์ ์ ์ฅ)
int[] ltrCnt = new int[len];
int[] rtlCnt = new int[len];
(2) ltrCnt ์ rtlCnt ๋ฐฐ์ด์ ์ฑ์ฐ๋ ๊ณผ์
โก๏ธ Check ๋ฐฐ์ด์ ํตํด ์ด์ ์ ์์๋ ํ ํ์ธ์ง๋ฅผ ํ์ธํ๋ค.
ex) ์ ์ถ๋ ฅ ์ 1 ์ ๊ฒฝ์ฐ : [1, 2, 1, 3, 1, 4, 1, 2] (์ข โก๏ธ ์ฐ ํ์)
โ index = 0 : ํ ํ 1
โก๏ธ (์ด๊ธฐํ) ์ฒซ๋ฒ์งธ ํ ํ์ ๋ฌด์กฐ๊ฑด ์ฒ์์ด๊ธฐ ๋๋ฌธ์ ltrCnt ๋ 1์ด ๋๊ณ ๋์์ ํ ํ 1 ๋ true ๊ฐ ๋๋ค.
ltrCheck [true, false, false, false] / ltrCnt [1, 0, 0, 0, 0, 0, 0, 0]
โก index = 1 : ํ ํ 2
โก๏ธ ํ ํ 2 ์ ๊ฒฝ์ฐ ltrCheck ๋ฅผ ํ์ธํด๋ณด๋ฉด false ๋ก ์๋ก์ด ํ ํ์ด๋ค. ๋ฐ๋ผ์ ltrCnt ๋ +1 ์ด ๋๋ฉด์ ํ ํ 2 ๋ true ๋ก ๋ฐ๊ฟ์ค๋ค.
ltrCheck [true, true, false, false] / ltrCnt [1, 2, 0, 0, 0, 0, 0, 0]
โข index = 3 : ํ ํ 1
โก๏ธ ltrCheck ๋ฅผ ํ์ธํด๋ณด๋ฉด ํ ํ 1 ์ ์ด๋ฏธ ์กด์ฌํ๋ ํ ํ์ด๋ค. ๋ฐ๋ผ์ ltrCnt ๊ณผ ltrCheck ์๋ ๋ณํ๊ฐ ์๋ค.
ltrCheck [true, true, false, false] / ltrCnt [1, 2, 2, 0, 0, 0, 0, 0]
(ํด๋น ๊ณผ์ ์ ๋๊น์ง ๋ฐ๋ณต)
// ์ข โก๏ธ ์ฐ ํ์
for (int i=1; i<len; i++) {
tmp = topping[i];
if (ltrCheck[tmp-1]) { // ํ ํ์ด ์กด์ฌํ๋ ๊ฒฝ์ฐ
ltrCnt[i] = ltrCnt[i-1];
continue;
}
// ์๋ก์ด ํ ํ์ธ ๊ฒฝ์ฐ
ltrCheck[tmp-1] = true;
ltrCnt[i] = ltrCnt[i-1]+1;
}
(3) ์ผ์ดํฌ ์๋ฅด๊ธฐ
โก๏ธ ์์ 1์ ์์ฒ๋ผ ์คํํ๋ฉด ์๋์ ๊ฐ์ด ๋๋ค.
โ ์ข โก๏ธ ์ฐ [1, 2, 2, 3, 3, 4, 4, 4]
โก ์ฐ โก๏ธ ์ข [4, 4, 4, 4, 3, 3, 2, 1]
โก๏ธ ์ด๋ ์์ชฝ์์ ์ขํ์ ๋ ๋ง๋๋ ์ง์ ์์ ์ข ๋ฅ์ ๊ฐ์๊ฐ ๊ฐ์ผ๋ฉด ๊ณตํํ ๋๋๊ธฐ๊ฐ ๋๋ค.

// ์ผ์ดํฌ ์๋ฅด๊ธฐ
for (int i=0; i<len-1; i++) {
if (ltrCnt[i] == rtlCnt[i+1]) {
answer++;
}
}
โก ๊ฒฐ๊ณผ

โก๏ธ ๋ฐ๋ณต๋ฌธ์ ์์ฃผ ๋๋ฉฐ ํ์ํ๋ค๋ณด๋, ๋ฐฐ์ด์ด ๊ธธ์ด์ง์๋ก ์๊ฐ๋ ์ฆ๊ฐํ๋ค. ๊ทธ๋๋ ์ด์ค์ผ๋ก๋ ๋์ง ์๊ธฐ ๋๋ฌธ์ ๋ณต์ก๋๋ O(n) ์ด๋ค.
๐ป ํ์ด ์ฝ๋
class Solution {
public int solution(int[] topping) {
int answer = 0;
int len = topping.length;
int max = 0;
for (int i=0; i<len; i++) {
if (max < topping[i]) {
max = topping[i];
}
}
// boolean ๋ฐฐ์ด ์์ฑ
boolean[] ltrCheck = new boolean[max];
boolean[] rtlCheck = new boolean[max];
// int ๋ฐฐ์ด ์์ฑ
int[] ltrCnt = new int[len];
int[] rtlCnt = new int[len];
// ์ด๊ธฐํ
ltrCnt[0] = 1;
ltrCheck[topping[0]-1] = true;
rtlCnt[len-1] = 1;
rtlCheck[topping[len-1]-1] = true;
int tmp = 0;
// ์ข โก๏ธ ์ฐ ํ์
for (int i=1; i<len; i++) {
tmp = topping[i];
if (ltrCheck[tmp-1]) {
ltrCnt[i] = ltrCnt[i-1];
continue;
}
ltrCheck[tmp-1] = true;
ltrCnt[i] = ltrCnt[i-1]+1;
}
// ์ฐ โก๏ธ ์ข ํ์
for (int i=len-2; i>-1; i--) {
tmp = topping[i];
if (rtlCheck[tmp-1]) {
rtlCnt[i] = rtlCnt[i+1];
continue;
}
rtlCheck[tmp-1] = true;
rtlCnt[i] = rtlCnt[i+1]+1;
}
// ์ผ์ดํฌ ์๋ฅด๊ธฐ
for (int i=0; i<len-1; i++) {
if (ltrCnt[i] == rtlCnt[i+1]) {
answer++;
}
}
return answer;
}
}
[unrated] Title: ๋กค์ผ์ดํฌ ์๋ฅด๊ธฐ, Time: 25.88 ms, Memory: 145 MB -BaekjoonHub · Young998904/Practice_Algorithm_Auto@03b2
Show file tree Showing 2 changed files with 163 additions and 0 deletions.
github.com