[Algorithm] ๐Ÿฌ๋ฐฑ์ค€ 1439 ๋’ค์ง‘๊ธฐ

HaJingJingยท2021๋…„ 5์›” 9์ผ
0

Algorithm

๋ชฉ๋ก ๋ณด๊ธฐ
35/119

0. ๋ฌธ์ œ

๋‹ค์†œ์ด๋Š” 0๊ณผ 1๋กœ๋งŒ ์ด๋ฃจ์–ด์ง„ ๋ฌธ์ž์—ด S๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๋‹ค. ๋‹ค์†œ์ด๋Š” ์ด ๋ฌธ์ž์—ด S์— ์žˆ๋Š” ๋ชจ๋“  ์ˆซ์ž๋ฅผ ์ „๋ถ€ ๊ฐ™๊ฒŒ ๋งŒ๋“ค๋ ค๊ณ  ํ•œ๋‹ค. ๋‹ค์†œ์ด๊ฐ€ ํ•  ์ˆ˜ ์žˆ๋Š” ํ–‰๋™์€ S์—์„œ ์—ฐ์†๋œ ํ•˜๋‚˜ ์ด์ƒ์˜ ์ˆซ์ž๋ฅผ ์žก๊ณ  ๋ชจ๋‘ ๋’ค์ง‘๋Š” ๊ฒƒ์ด๋‹ค. ๋’ค์ง‘๋Š” ๊ฒƒ์€ 1์„ 0์œผ๋กœ, 0์„ 1๋กœ ๋ฐ”๊พธ๋Š” ๊ฒƒ์„ ์˜๋ฏธํ•œ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด S=0001100 ์ผ ๋•Œ,

์ „์ฒด๋ฅผ ๋’ค์ง‘์œผ๋ฉด 1110011์ด ๋œ๋‹ค.
4๋ฒˆ์งธ ๋ฌธ์ž๋ถ€ํ„ฐ 5๋ฒˆ์งธ ๋ฌธ์ž๊นŒ์ง€ ๋’ค์ง‘์œผ๋ฉด 1111111์ด ๋˜์–ด์„œ 2๋ฒˆ ๋งŒ์— ๋ชจ๋‘ ๊ฐ™์€ ์ˆซ์ž๋กœ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋‹ค.
ํ•˜์ง€๋งŒ, ์ฒ˜์Œ๋ถ€ํ„ฐ 4๋ฒˆ์งธ ๋ฌธ์ž๋ถ€ํ„ฐ 5๋ฒˆ์งธ ๋ฌธ์ž๊นŒ์ง€ ๋ฌธ์ž๋ฅผ ๋’ค์ง‘์œผ๋ฉด ํ•œ ๋ฒˆ์— 0000000์ด ๋˜์–ด์„œ 1๋ฒˆ ๋งŒ์— ๋ชจ๋‘ ๊ฐ™์€ ์ˆซ์ž๋กœ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋‹ค.

๋ฌธ์ž์—ด S๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ๋‹ค์†œ์ด๊ฐ€ ํ•ด์•ผํ•˜๋Š” ํ–‰๋™์˜ ์ตœ์†Œ ํšŸ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•˜์‹œ์˜ค.

์ž…๋ ฅ
์ฒซ์งธ ์ค„์— ๋ฌธ์ž์—ด S๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. S์˜ ๊ธธ์ด๋Š” 100๋งŒ๋ณด๋‹ค ์ž‘๋‹ค.

์ถœ๋ ฅ
์ฒซ์งธ ์ค„์— ๋‹ค์†œ์ด๊ฐ€ ํ•ด์•ผํ•˜๋Š” ํ–‰๋™์˜ ์ตœ์†Œ ํšŸ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.

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

1) ์ œ์ผ ์•ž์ž๋ฆฌ์˜ ์ˆซ์ž ํŒŒ์•… ํ›„, count ์ฆ๊ฐ€
2) ์ˆซ์ž๊ฐ€ ์—ฐ์†ํ•˜์ง€ ์•Š๋Š” ๋ถ€๋ถ„์—์„œ, ๋’ค์— ์ˆซ์ž์— ํ•ด๋‹นํ•˜๋Š” count๋ฅผ ์ฆ๊ฐ€

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

1) ์ œ์ผ ์•ž์ž๋ฆฌ์˜ ์ˆซ์ž ํŒŒ์•… ํ›„, count ์ฆ๊ฐ€

count[s.charAt(0)-'0']++;

2) ์ˆซ์ž๊ฐ€ ์—ฐ์†ํ•˜์ง€ ์•Š๋Š” ๋ถ€๋ถ„์—์„œ, ๋’ค์— ์ˆซ์ž์— ํ•ด๋‹นํ•˜๋Š” count๋ฅผ ์ฆ๊ฐ€

if(a!=b) 
				count[a-'0']++;

3. ์ฝ”๋“œ

import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Greedy_7 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s = br.readLine();
		int count[] = new int[2];
		
		count[s.charAt(0)-'0']++;
		for(int i=1; i<s.length(); i++) {
			char a = s.charAt(i);
			char b = s.charAt(i-1);
			if(a!=b) 
				count[a-'0']++;
		}
		
		System.out.println(Math.min(count[0], count[1]));
		
	}

}

4. ๊ฒฐ๊ณผ

์„ฑ๊ณต~

profile
๐ŸŒฑ์ดˆ๋ณด ๊ฐœ๋ฐœ์ž๐ŸŒฑ

0๊ฐœ์˜ ๋Œ“๊ธ€