Skip to content

invidam.go.md

Latest commit

Β 

History

History
70 lines (62 loc) Β· 1.82 KB

invidam.go.md

File metadata and controls

70 lines (62 loc) Β· 1.82 KB

Intuition

κ΅¬λΆ„μžλ₯Ό λ„£μ–΄ 였λ₯˜λ₯Ό λ°©μ§€ν•œλ‹€.

Approach

  1. UTF-8에 λ²—μ–΄λ‚˜λŠ” κ΅¬λΆ„μž ㄱ을 λ„£μ–΄ κ΅¬λΆ„ν–ˆλ‹€.

Complexity

  • Time complexity: $$O(n)$$

    • λ¬Έμžμ—΄μ˜ 길이 n에 λŒ€ν•˜μ—¬, 이λ₯Ό μˆœνšŒν•˜λŠ” λΉ„μš©μ΄ λ°œμƒν•œλ‹€.

  • Space complexity: $$O(n)$$

    • λ¬Έμžμ—΄μ˜ 길이 n에 λŒ€ν•˜μ—¬, encodedλ₯Ό λ§Œλ“œλŠ” 곡간이 λ°œμƒν•œλ‹€.

Code

const DIVIDE_CHAR_V1 = 'γ„±'
func encodeV1(strs []string) string {
	ret := strings.Join(strs, string(DIVIDE_CHAR_V1))
	return ret
}

func decodeV1(encoded string) []string {
	sep := string(DIVIDE_CHAR_V1)
	return strings.Split(encoded, sep)
}

Intuition

μ†”λ£¨μ…˜μ—μ„œ λ„€νŠΈμ›Œν¬ 톡신을 μœ„ν•œλ‹€λŠ” λͺ©μ μ„ λ“£κ³  μˆ˜μ •ν•΄λ³΄μ•˜λ‹€. (μœ λ‹ˆμ½”λ“œλ₯Ό λ„£λŠ” 게 μ˜λ„λŠ” μ•„λ‹Œ λ“―ν–ˆλ‹€.)

Approach

  1. κ΅¬λΆ„μž (-)와 이전 문자의 길이λ₯Ό ν•¨κ»˜ μ €μž₯ν•œλ‹€.
  2. κ΅¬λΆ„μžκ°€ λ‚˜μ˜¨λ‹€λ©΄, λ¬Έμžμ—΄μ˜ 길이λ₯Ό μΆ”μΆœν•˜μ—¬ λ¬Έμžμ—΄μ„ λ””μ½”λ”©ν•œλ‹€.
  3. μœ„ 과정을 배열을 μˆœνšŒν•˜λ©° λ°˜λ³΅ν•œλ‹€.

Complexity

  • Time complexity: $$O(n)$$

    • λ¬Έμžμ—΄μ˜ 길이 n에 λŒ€ν•˜μ—¬, 이λ₯Ό μˆœνšŒν•˜λŠ” λΉ„μš©μ΄ λ°œμƒν•œλ‹€.

  • Space complexity: $$O(n)$$

    • λ¬Έμžμ—΄μ˜ 길이 n에 λŒ€ν•˜μ—¬, encodedλ₯Ό λ§Œλ“œλŠ” 곡간이 λ°œμƒν•œλ‹€.

Code

const DIVIDE_CHAR = '-'
func encode(strs []string) string {
	ret := ""
	for _, str := range strs {
		ret += str
		ret += fmt.Sprintf("%c%04d", DIVIDE_CHAR, len(str))
		// a-1bcd-3
	}
	return ret
}

func decode(encoded string) []string {
	ret := make([]string, 0)
	for i := 0; i < len(encoded); {
		if encoded[i] == DIVIDE_CHAR {
			lenStr := encoded[i+1 : i+5]
			len, _ := strconv.Atoi(lenStr)

			decodeStr := encoded[i-len : i]
			ret = append(ret, decodeStr)
			i += 5
		} else {
			i += 1
		}
	}

	return ret
}