[Algorithm] ๐Ÿ•น๏ธํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ์กฐ์ด์Šคํ‹ฑ

0. ๋ฌธ์ œ

์กฐ์ด์Šคํ‹ฑ์œผ๋กœ ์•ŒํŒŒ๋ฒณ ์ด๋ฆ„์„ ์™„์„ฑํ•˜์„ธ์š”. ๋งจ ์ฒ˜์Œ์—” A๋กœ๋งŒ ์ด๋ฃจ์–ด์ ธ ์žˆ์Šต๋‹ˆ๋‹ค.
ex) ์™„์„ฑํ•ด์•ผ ํ•˜๋Š” ์ด๋ฆ„์ด ์„ธ ๊ธ€์ž๋ฉด AAA, ๋„ค ๊ธ€์ž๋ฉด AAAA

์กฐ์ด์Šคํ‹ฑ์„ ๊ฐ ๋ฐฉํ–ฅ์œผ๋กœ ์›€์ง์ด๋ฉด ์•„๋ž˜์™€ ๊ฐ™์Šต๋‹ˆ๋‹ค.

โ–ฒ - ๋‹ค์Œ ์•ŒํŒŒ๋ฒณ
โ–ผ - ์ด์ „ ์•ŒํŒŒ๋ฒณ (A์—์„œ ์•„๋ž˜์ชฝ์œผ๋กœ ์ด๋™ํ•˜๋ฉด Z๋กœ)
โ—€ - ์ปค์„œ๋ฅผ ์™ผ์ชฝ์œผ๋กœ ์ด๋™ (์ฒซ ๋ฒˆ์งธ ์œ„์น˜์—์„œ ์™ผ์ชฝ์œผ๋กœ ์ด๋™ํ•˜๋ฉด ๋งˆ์ง€๋ง‰ ๋ฌธ์ž์— ์ปค์„œ)
โ–ถ - ์ปค์„œ๋ฅผ ์˜ค๋ฅธ์ชฝ์œผ๋กœ ์ด๋™

์˜ˆ๋ฅผ ๋“ค์–ด ์•„๋ž˜์˜ ๋ฐฉ๋ฒ•์œผ๋กœ "JAZ"๋ฅผ ๋งŒ๋“ค ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

  • ์ฒซ ๋ฒˆ์งธ ์œ„์น˜์—์„œ ์กฐ์ด์Šคํ‹ฑ์„ ์œ„๋กœ 9๋ฒˆ ์กฐ์ž‘ํ•˜์—ฌ J๋ฅผ ์™„์„ฑํ•ฉ๋‹ˆ๋‹ค.
  • ์กฐ์ด์Šคํ‹ฑ์„ ์™ผ์ชฝ์œผ๋กœ 1๋ฒˆ ์กฐ์ž‘ํ•˜์—ฌ ์ปค์„œ๋ฅผ ๋งˆ์ง€๋ง‰ ๋ฌธ์ž ์œ„์น˜๋กœ ์ด๋™์‹œํ‚ต๋‹ˆ๋‹ค.
  • ๋งˆ์ง€๋ง‰ ์œ„์น˜์—์„œ ์กฐ์ด์Šคํ‹ฑ์„ ์•„๋ž˜๋กœ 1๋ฒˆ ์กฐ์ž‘ํ•˜์—ฌ Z๋ฅผ ์™„์„ฑํ•ฉ๋‹ˆ๋‹ค.
    ๋”ฐ๋ผ์„œ 11๋ฒˆ ์ด๋™์‹œ์ผœ "JAZ"๋ฅผ ๋งŒ๋“ค ์ˆ˜ ์žˆ๊ณ , ์ด๋•Œ๊ฐ€ ์ตœ์†Œ ์ด๋™์ž…๋‹ˆ๋‹ค.

    ๋งŒ๋“ค๊ณ ์ž ํ•˜๋Š” ์ด๋ฆ„ name์ด ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, ์ด๋ฆ„์— ๋Œ€ํ•ด ์กฐ์ด์Šคํ‹ฑ ์กฐ์ž‘ ํšŸ์ˆ˜์˜ ์ตœ์†Ÿ๊ฐ’์„ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ๋งŒ๋“œ์„ธ์š”.

์ œํ•œ์‚ฌํ•ญ

  • name์€ ์•ŒํŒŒ๋ฒณ ๋Œ€๋ฌธ์ž๋กœ๋งŒ ์ด๋ฃจ์–ด์ ธ ์žˆ์Šต๋‹ˆ๋‹ค.
  • name์˜ ๊ธธ์ด๋Š” 1 ์ด์ƒ 20 ์ดํ•˜์ž…๋‹ˆ๋‹ค.

์ž…๋ ฅ ์˜ˆ์‹œ
"JEROEN"
"JAN"

์ถœ๋ ฅ ์˜ˆ์‹œ
56
23

1. ์•„์ด๋””์–ด

๐Ÿ’ก A์™€ ์•ŒํŒŒ๋ฒณ์˜ ์ฐจ์™€ Z์™€ ์•ŒํŒŒ๋ฒณ์˜ ์ฐจ ์ค‘ ๋” ์ž‘์€ ๊ฐ’์„ ๊ณ ๋ฆ„
๐Ÿ’ก ์œ„์น˜ ์ด๋™์€ A๋ฅผ ๊ณ ๋ คํ•ด์ค˜์•ผํ•จ

i) ์•ž์—์„œ ์ด๋™ํ•˜๋Š” ๊ฒฝ์šฐ
ii) ๋’ค์—์„œ ์ด๋™ํ•˜๋Š” ๊ฒฝ์šฐ
iii) ์•ž์—์„œ ๊ฐ€๋‹ค๊ฐ€ ๋˜๋Œ์•„๊ฐ€๋Š” ๊ฒฝ์šฐ

2. ํ•ต์‹ฌ ํ’€์ด

1) A์™€ ์•ŒํŒŒ๋ฒณ์˜ ์ฐจ์™€ Z์™€ ์•ŒํŒŒ๋ฒณ์˜ ์ฐจ ์ค‘ ๋” ์ž‘์€ ๊ฐ’์„ ๊ณ ๋ฆ„

answer+= Math.min(alpha-'A', 'Z'-alpha+1);

2-1) ์•ž์—์„œ ์ด๋™ํ•˜๋Š” ๊ฒฝ์šฐ

for(int i=1; i<length; i++) {
			if(name.charAt(i) == 'A')
				left++;
			else
				break;
		}

2-2) ๋’ค์—์„œ ์ด๋™ํ•˜๋Š” ๊ฒฝ์šฐ

for(int i=length-1; i>=0; i--) {
			if(name.charAt(i) == 'A')
				right++;
			else
				break;
		}

2-3) ์•ž์—์„œ ๊ฐ€๋‹ค๊ฐ€ ๋˜๋Œ์•„๊ฐ€๋Š” ๊ฒฝ์šฐ

int next = i+1;
while(next<length && name.charAt(next) == 'A')
				next++;
			
min = Math.min(min, length-next+i*2);

3. ์ฝ”๋“œ

class Greedy_14 {
	public int solution(String name) {
		int answer = 0;
		int length = name.length();
		int min = length - 1;

		for (int i = 0; i < length; i++) {
			char alpha = name.charAt(i);
			answer += Math.min(alpha - 'A', 'Z' - alpha + 1);

			int next = i + 1;
			while (next < length && name.charAt(next) == 'A')
				next++;

			min = Math.min(min, length - next + i * 2);
		}

		int left = 0, right = 0;
		for (int i = 1; i < length; i++) {
			if (name.charAt(i) == 'A')
				left++;
			else
				break;
		}

		for (int i = length - 1; i >= 0; i--) {
			if (name.charAt(i) == 'A')
				right++;
			else
				break;
		}

		int max = Math.max(right, left);

		min = Math.min(min, length - 1 - Math.max(right, left));

		answer += min;
		return answer;
	}
}

4. ๊ฒฐ๊ณผ

์„ฑ๊ณตโœจ
๊ฐ”๋‹ค๊ฐ€ ๋‹ค์‹œ ๋Œ์•„์˜ค๋Š” ๊ฒฝ์šฐ๋ฅผ ์ƒ๊ฐ ๋ชปํ•ด์„œ ์ฒ˜์Œ์— ํ‹€๋ ธ์—ˆ๋‹ค..๐Ÿ˜ญ

์ข‹์€ ์›นํŽ˜์ด์ง€ ์ฆ๊ฒจ์ฐพ๊ธฐ